Lower bounds in communication complexity
By: Lee, Troy
Contributor(s): Shraibman, Adi
Language: English Publisher: United States of America -- Now Publishers -- 2009Description: x, 141pISBN: 9781601982582Subject(s): Computer science | Computing and ProcessingDDC classification: 004.6 LEE/L Summary: 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.
| Item type | Current location | Collection | Call number | Status | Date due | Barcode |
|---|---|---|---|---|---|---|
Book
|
Central Library General Stack (Nila Campus) | 004.6 LEE/L07978 | Available | 07979 | ||
Reference
|
Central Library Reference (Sahyadri Campus) | Reference | 004.6 LEE/L07978 | Not for loan | 07978 |
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.
Acknowledgements.
References
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.