Communication Complexity: and Applications

Description

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 Conventions and Preliminaries Introduction Part I Communication 1 Deterministic Protocols Rectangles Balancing Protocols From Rectangles to Protocols Lower Bounds Rectangle Covers Direct-Sums in Communication Complexity 2 Rank Communication Complexity and Rank Properties of Rank Lower Bounds Based on Rank Nonnegative Rank Better Upper Bounds Using Rank 3 Randomized Protocols Some Protocols Randomized Communication Complexity Public Coins versus Private Coins Nearly Monochromatic Rectangles 4 Numbers on Foreheads Some Protocols Defining Protocols in the Number-on-Forehead Model Cylinder Intersections Lower Bounds from Ramsey Theory 5 Discrepancy Definitions Discrepancy and Communication Convexity in Combinatorics Lower Bounds for Inner-Product Disjointness and Discrepancy Concentration of Measure 6 Information Entropy Chain Rule and Conditional Entropy Divergence and Mutual Information Lower Bound for Indexing The Power of Interaction Randomized Complexity of Disjointness 7 Compressing Communication Simulations Compressing Protocols with No Private Randomness Correlated Sampling Compressing a Single Round Internal Compression of Protocols Direct Sums in Randomized Communication Complexity Other Methods to Compress Protocols 8 Lifting Decision Trees The Lifting Theorem Separating Rank and Communication Part II Applications 9 Circuits and Proofs Boolean Circuits Karchmer-Wigderson Games Monotone Circuit-Depth Lower Bounds Monotone Circuit-Depth Hierarchy Boolean Formulas Boolean Depth Conjecture Proof Systems Resolution Refutations Cutting Planes 10 Memory Size Lower Bounds for Streaming Algorithms Lower Bounds for Branching Programs 11 Data Structures Dictionaries Ordered Sets Lower Bounds on Static Data Structures Lower Bounds on Dynamic Data Structures Graph Connectivity 12 Extension Complexity of Polytopes Transformations of Polytopes Algorithms from Polytopes Extension Complexity Slack Matrices Lower Bounds on Extension Complexity 13 Distributed Computing Some Protocols Lower Bounds Computing the Girth Bibliography Index