Communication complexity (for algorithm designers)

DOI10.1561/0400000076MaRDI QIDQ3178295zbMATH OpenOpenAlexFDO

Authors Tim Roughgarden

Publication date 11 July 2016

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.06257

zbMATH Keywords

communication complexity

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Communication complexity, information complexity (68Q11) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: This document collects the lecture notes from my course "Communication Complexity (for Algorithm Designers), taught at Stanford in the winter quarter of 2015. The two primary goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds. Along the way, we'll also: 3. Get exposure to lots of cool computational models and some famous results about them --- data streams and linear sketches, compressive sensing, space-query time trade-offs in data structures, sublinear-time algorithms, and the extension complexity of linear programs. 4. Scratch the surface of techniques for proving communication complexity lower bounds (fooling sets, corruption bounds, etc.).

Recommendations

• Communication Complexity
• An introductory course on communication complexity
• Lower bounds in communication complexity
• Communication Complexity
• scientific article; zbMATH DE number 1011685

Cited in

(16)

• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Extension complexity of the correlation polytope
• Nondeterministic communication complexity of random Boolean functions (extended abstract)
• Lower bounds in communication complexity
• An introductory course on communication complexity
• Extension complexity of independent set polytopes
• Communication Complexity
• Communication complexity of correlated equilibrium with small support
• Communication complexity
• The communication complexity of set intersection and multiple equality testing
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Space limited linear-time graph algorithms on big data
• Streaming and query once space complexity of longest increasing subsequence
• Universal matrix sparsifiers and fast deterministic algorithms for linear algebra
• Regular languages in the sliding window model

This page was built for publication: Communication complexity (for algorithm designers)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178295)