Communication Complexity Lower Bounds by Polynomials

Details Communication Complexity Lower Bounds by Polynomials Communication Complexity Lower Bounds by Polynomials

1999-10-12

arxiv.org/abs/cs/9910010v2

Computer Science

Computational Complexity

16 pages LaTeX, no figures. 2nd version: rewritten and some results added

Scientific paper

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the log-rank lower bound extends to the strongest model (qubit communication + unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log-rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

Affiliated with

Also associated with

No associations

Rating

Communication Complexity Lower Bounds by Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Communication Complexity Lower Bounds by Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication Complexity Lower Bounds by Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-446263