Read more
Presents basic theory for graduate students and researchers with applications in circuit and proof complexity, streaming algorithms and distributed computing.
List of contents
Preface; Conventions and preliminaries; Introduction; Part I. Communication: 1. Deterministic protocols; 2. Rank; 3. Randomized protocols; 4. Numbers on foreheads; 5. Discrepancy; 6. Information; 7. Compressing communication; 8. Lifting; Part II. Applications: 9. Circuits and proofs; 10. Memory size; 11. Data structures; 12. Extension Complexity of Polytopes; 13. Distributed computing.
About the author
Anup Rao is an Associate Professor at the School of Computer Science, University of Washington. He received his Ph.D. in Computer Science from the University of Texas, Austin, and was a researcher at the Institute for Advanced Study, Princeton. His research interests are primarily in theoretical computer science.Amir Yehudayoff is Associate Professor of Mathematics at Technion – Israel Institute of Technology, Haifa. He is interested in mathematical questions that are motivated by theoretical computer science and machine learning. He was a member of the Institute for Advanced Study in Princeton, and served as the secretary of the Israel Mathematical Union. He has won several prizes, including the Cooper Prize and the Krill Prize for excellence in scientific research, and the Kurt Mahler Prize for excellence in mathematics.
Summary
Communication complexity is the mathematical study of scenarios where several parties need to communicate to achieve a common goal. This tutorial text explains fundamentals and recent developments in an accessible and illustrated form, including applications in circuit complexity, proof complexity, streaming algorithms and distributed computing.
Additional text
'This book is a much-needed introductory text on communication complexity. It will bring the reader up to speed on both classical and more recent lower bound techniques, and on key application areas. An invaluable resource for anyone interested in complexity theory.' Mark Braverman, Princeton University, New Jersey
