Communication Complexity: And Applications

ISBN-13: 9781108497985 / Angielski / Twarda / 2020 / 266 str.

Anup Rao; Amir Yehudayoff

Opis

Presents basic theory for graduate students and researchers with applications in circuit and proof complexity, streaming algorithms and distributed computing.

Recenzje

'… must-have reference for students but will be welcomed by researchers as well because it is so well-written and aptly organized … Highly recommended.' A. Misseldine, CHOICE

Spis treści

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.