Foundations and Trends® in Theoretical Computer Science > Vol 3 > Issue 4

Lower Bounds in Communication Complexity

By Troy Lee, Columbia University, USA, | Adi Shraibman, Department of Mathematics, Weizmann Institute, Israel,

Suggested Citation
Troy Lee and Adi Shraibman (2009), "Lower Bounds in Communication Complexity", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399.

Publication Date: 15 Oct 2009
© 2009 T. Lee and A. Shraibman
Computational aspects of communication

Free Preview:

Download extract


Download article
In this article:
1 Introduction 
2 Deterministic Communication Complexity 
3 Nondeterministic Communication Complexity 
4 Randomized Communication Complexity 
5 Quantum Communication Complexity 
6 The Role of Duality in Proving Lower Bounds 
7 Choosing a Witness 
8 Multiparty Communication Complexity 
9 Upper Bounds on Multiparty Communication Complexity 


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.

ISBN: 978-1-60198-258-2
148 pp. $99.00
Buy book (pb)
ISBN: 978-1-60198-259-9
148 pp. $125.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Deterministic communication complexity
3: Nondeterministic communication complexity
4: Randomized communication complexity
5: Quantum communication complexity
6: The role of duality in proving lower bounds
7: Choosing a witness
8: Multiparty communication complexity
9: Upper bounds on multiparty communication

Lower Bounds in Communication Complexity

In the thirty years since its inception, communication complexity has become a vital area of theoretical computer science. The applicability of communication complexity to other areas, including circuit and formula complexity, VLSI design, proof complexity, and streaming algorithms, has meant it has attracted a lot of interest. Lower Bounds in Communication Complexity focuses on showing lower bounds on the communication complexity of explicit functions. It treats different variants of communication complexity, including randomized, quantum, and multiparty models. Many tools have been developed for this purpose from a diverse set of fields including linear algebra, Fourier analysis, and information theory. As is often the case in complexity theory, demonstrating a lower bound is usually the more difficult task. Lower Bounds in Communication Complexity describes a three-step approach for the development and application of these techniques. This approach can be applied in much the same way for different models, be they randomized, quantum, or multiparty. Lower Bounds in Communication Complexity is an ideal primer for anyone with an interest in this current and popular topic.