Communication Complexity: And Applications

Communication complexity is the mathematical study of scenarios where several parties need to communicate to achieve a common goal, a situation that naturally appears during computation. This introduction presents the most recent developments in an accessible form, providing the language to unify several disjoint research subareas. Written as a guide for a graduate course on communication complexity, it will interest a broad audience in computer science, from advanced undergraduates to researchers in areas ranging from theory to algorithm design to distributed computing. The first part presents basic theory in a clear and illustrative way, offering beginners an entry into the field. The second part describes applications including circuit complexity, proof complexity, streaming algorithms, extension complexity of polytopes, and distributed computing. Proofs throughout the text use ideas from a wide range of mathematics, including geometry, algebra, and probability. Each chapter contains numerous examples, figures, and exercises to aid understanding.

•  
• Offers a modern guide to a growing, interdisciplinary field
• Includes numerous illustrations, examples, and end-of-chapter exercises
• Comments and notes provide context and pointers to further reading

通信複雜度是數學研究的範疇，其中多個方需要進行通信以達到共同目標，這種情況在計算過程中自然出現。本書以易於理解的形式介紹了最新的發展，提供了統一多個不同研究子領域的語言。作為一本關於通信複雜度的研究生課程指南，它將對計算機科學的廣泛讀者感興趣，從高年級本科生到從理論到算法設計到分布式計算等領域的研究人員。第一部分以清晰且具有說明性的方式介紹了基本理論，為初學者提供了進入該領域的入門知識。第二部分描述了應用，包括電路複雜度、證明複雜度、流算法、多面體擴展複雜度和分布式計算。全書的證明使用了廣泛的數學思想，包括幾何、代數和概率。每章都包含了大量的例子、圖表和練習，以幫助理解。

- 提供了一個現代化的指南，涵蓋了一個不斷發展的跨學科領域
- 包含了大量的插圖、例子和章末練習
- 註解和筆記提供了背景和進一步閱讀的指引

Anup Rao, University of Washington
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, Technion - Israel Institute of Technology, Haifa
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.

Anup Rao 是華盛頓大學計算機科學學院的副教授。他在德克薩斯大學奧斯汀分校獲得計算機科學博士學位，並曾在普林斯頓高等研究院擔任研究員。他的研究興趣主要集中在理論計算機科學領域。

Amir Yehudayoff 是以色列理工學院（Technion）數學系的副教授，位於海法。他對於理論計算機科學和機器學習所引發的數學問題感興趣。他曾是普林斯頓高等研究院的成員，並擔任以色列數學聯盟的秘書。他曾獲得多個獎項，包括庫珀獎和克里爾獎（Cooper Prize and Krill Prize）以表彰其在科學研究方面的卓越成就，以及庫爾特·馬勒獎（Kurt Mahler Prize）以表彰其在數學領域的卓越成就。

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.

前言
慣例和前提
介紹
第一部分. 通訊:
1. 確定性協議
2. 等級
3. 隨機協議
4. 額頭上的數字
5. 差異
6. 資訊
7. 壓縮通訊
8. 提升
第二部分. 應用:
9. 電路和證明
10. 記憶體大小
11. 資料結構
12. 多面體的擴展複雜度
13. 分散式計算。