Communication Complexity (for Algorithm Designers)

DOI10.1561/0400000076zbMath1470.68007arXiv1509.06257OpenAlexW2963904743MaRDI QIDQ3178295

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication complexity, information complexity (68Q11)

Related Items (9)

Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ Space limited linear-time graph algorithms on big data ⋮ Unnamed Item ⋮ Extension Complexity of Independent Set Polytopes ⋮ Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract) ⋮ Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond ⋮ Extension complexity of the correlation polytope ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing

This page was built for publication: Communication Complexity (for Algorithm Designers)