Lower Bounds in Communication Complexity
- 15 October 2009
- journal article
- Published by Emerald Publishing in Foundations and Trends® in Theoretical Computer Science
- Vol. 3 (4) , 263-399
Abstract
The communication complexity of a function f(x,y) measures the number of bits that two players, one who knows x and the other who knows y, must exchange to determine the value f(x,y). Communication complexity is a fundamental measure of complexity of functions. Lower bounds on this measure lead to lower bounds on many other measures of computational complexity. This monograph surveys lower bounds in the field of communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure, such as rank or trace norm, that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools.Keywords
This publication has 76 references indexed in Scilit:
- Composition Theorems in Communication ComplexityLecture Notes in Computer Science, 2010
- The Communication Complexity of Non-signaling Distributions2009
- Lower bounds in communication complexity based on factorization normsRandom Structures & Algorithms, 2008
- A Lower Bound for Agnostically Learning Disjunctions2007
- Hadamard Tensors and Lower Bounds on Multiparty Communication ComplexityLecture Notes in Computer Science, 2005
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- On rank vs. communication complexityCombinatorica, 1995
- The Bns Lower-Bound for Multiparty Protocols Is Nearly OptimalInformation and Computation, 1994
- Quasi‐random classes of hypergraphsRandom Structures & Algorithms, 1990
- A counterexample to the rank‐coloring conjectureJournal of Graph Theory, 1989