Lower bounds in communication complexity based on factorization norms
- 10 September 2008
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 34 (3) , 368-394
Abstract
We introduce a new method to derive lower bounds on randomized and quantum communication complexity. Our method is based on factorization norms, a notion from Banach Space theory. This approach gives us access to several powerful tools from this area such as normed spaces duality and Grothendiek's inequality. This extends the arsenal of methods for deriving lower bounds in communication complexity.As we show, our method subsumes most of the previously known general approaches to lower bounds on communication complexity. Moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement.Our results also shed some light on the question how much communication can be saved by using entanglement. It is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. It follows from our results that this bound on the saving in communication is tight almost always. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009Keywords
This publication has 16 references indexed in Scilit:
- Complexity measures of sign matricesCombinatorica, 2007
- Quantum communication complexity of symmetric predicatesIzvestiya: Mathematics, 2003
- On rank vs. communication complexity2002
- On quantum and probabilistic communication2000
- Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean FunctionsAlgorithmica, 1999
- Communication Complexity1997
- Fourier analysis for probabilistic communication complexitycomputational complexity, 1995
- On randomized one-round communication complexity1995
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen statesPhysical Review Letters, 1992
- On “bent” functionsJournal of Combinatorial Theory, Series A, 1976