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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Deterministic Communication Complexity
Nondeterministic Communication Complexity
Randomized Communication Complexity
Quantum Communication Complexity
The Role of Duality in Proving Lower Bounds
Choosing a Witness
Multiparty Communication Complexity
Upper Bounds on Multiparty Communication
Alice and Bob approximate degree approximate norm approximate rank approximate trace norm bits Boolean matrix Buhrman coin protocol combinatorial rectangles communication matrix communication protocol complexity measure compute convex corruption bound deﬁned deﬁnition denoted deterministic communication complexity deterministic protocol diﬀerent diﬃcult dual norm dual polynomial dual space duality eﬃcient example ﬁnd ﬁrst function f gives Hadamard Hadamard matrix IEEE inequality inner function inner product input x,y Lemma Let f linear log-rank conjecture logn lower bound lower bound techniques matrix rank monochromatic multiparty communication complexity nondeterministic nondeterministic communication complexity NP-hard number-on-the-forehead model optimal output partition bound pattern tensor players plexity polynomial private coin probability distribution problem proof public coin quantum communication complexity query complexity randomized communication complexity randomized complexity randomized protocol rank-one rank(A real matrix Section semideﬁnite Sherstov Shraibman sign matrix simply size(A spectral norm streaming algorithm strongly balanced Theorem 6.1 three-step approach upper bound