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 co...

(展开全部)

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.

Contents
Preface 9
Conventions and Preliminaries Introduction 17
I Communication 23
1 Deterministic Protocols Rectangles 27
Balancing Protocols 29
· · · · · · (更多)

Contents
Preface 9
Conventions and Preliminaries Introduction 17
I Communication 23
1 Deterministic Protocols Rectangles 27
Balancing Protocols 29
From Rectangles to Protocols
Lower Bounds 32
Rectangle Covers
Direct-sums in Communication Complexity 44
Rank 51
Communication Complexity and Rank 52
Properties of Rank 53
Lower bounds based on rank 54 Non-Negative Rank 56
Better Upper Bounds using Rank 58
42
30
6
3 Randomized Protocols 65 Some Protocols 65
Randomized Communication Complexity 69 Public Coins vs Private Coins 72
Nearly Monochromatic Rectangles
4 Numbers On Foreheads 77 Some Protocols 77
73
Defining Protocols in the Number-on-Forehead model 81 Cylinder Intersections 81
Lower Bounds from Ramsey Theory
5 Discrepancy 89 Definitions 89
Discrepancy and Communication Convexity in Combinatorics 91 Lower Bounds for Inner-Product Disjointness and Discrepancy 96 Concentration of Measure 103
6 Information 117 Entropy 117
83
90
93
Chain Rule and Conditional Entropy Divergence and Mutual Information
Lower Bound for Indexing 131
The Power of Interaction 136
Randomized Complexity of Disjointness 140
7 Compressing Communication 147 Simulations 149
121 129
Compressing Protocols with No Private Randomness Correlated Sampling 152
Compressing a Single Round 154
Internal Compression of Protocols
Direct Sums in Randomized Communication Complexity Other Methods to Compress Protocols 168
8 Lifting 171 Decision Trees 171
The Lifting Theorem 172
Separating Rank and Communication 178
II Applications 183
9 Circuits and Proofs 185 Boolean Circuits 185
Karchmer-Wigderson Games 186 Monotone Circuit-Depth Lower Bounds Monotone Circuit-Depth Hierarchy 190 Boolean Formulas 191
Boolean Depth Conjecture 194 Proof Systems 195
Resolution Refutations 195 Cutting Planes 199
10 Memory Size 207
Lower Bounds for Streaming Algorithms 210
Lower Bounds for Branching Programs 215
11 Data Structures 221 Dictionaries 221
Ordered Sets 222
Lower Bounds on Static Data Structures 228
Lower bounds on Dynamic Data Structures Graph Connectivity 239
12 Extension Complexity of Polytopes 247 Transformations of Polytopes 249
234
Algorithms from Polytopes 253
Extension Complexity 256
Slack Matrices 262
Lower Bounds on Extension Complexity 266
13 Distributed Computing 277 Some Protocols 277
Lower Bounds 279 Computing the Girth 281
List of Figures 283 Bibliography 289 Index 299
· · · · · · (收起)