Quantum communication complexity of symmetric predicates

We completely (that is, up to a logarithmic factor) characterize the bounded-error quantum communication complexity of every predicate ) depending only on . More precisely, given a predicate on , we put Then the bounded-error quantum communication complexity of is equal to (up to a logarithmic factor). In particular, the complexity of the set disjointness predicate is equal to . This result holds both in the model with prior entanglement and in the model without it.