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.
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.
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.
Inhaltsangabe
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.
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.
Es gelten unsere Allgemeinen Geschäftsbedingungen: www.buecher.de/agb
Impressum
www.buecher.de ist ein Internetauftritt der buecher.de internetstores GmbH
Geschäftsführung: Monica Sawhney | Roland Kölbl | Günter Hilger
Sitz der Gesellschaft: Batheyer Straße 115 - 117, 58099 Hagen
Postanschrift: Bürgermeister-Wegele-Str. 12, 86167 Augsburg
Amtsgericht Hagen HRB 13257
Steuernummer: 321/5800/1497
USt-IdNr: DE450055826