Articles under category:
Communication Complexity
ToC Library Graduate Surveys 4 (2011) 27 pages
Variations on the Sensitivity Conjecture
by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov
Vol 19, Article 10 (pp 1-44)
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams
by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang
Vol 18, Article 19 (pp 1-22) [CCC20 Spec Issue]
Sign-Rank vs. Discrepancy
by Kaave Hosseini, Hamed Hatami, and Shachar Lovett
Vol 18, Article 15 (pp 1-33) [CCC20 Spec Issue]
Multiparty Karchmer-Wigderson Games and Threshold Circuits
by Alexander Kozachinskiy and Vladimir Podolskii
Vol 17, Article 8 (pp 1-28)
The Layer Complexity of Arthur-Merlin-like Communication
by Dmitry Gavinsky
Vol 16, Article 13 (pp 1-30)
Monotone Circuit Lower Bounds from Resolution
by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov
Vol 16, Article 12 (pp 1-18)
Optimality of Correlated Sampling Strategies
by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Vol 15, Article 11 (pp 1-13)
Fourier Sparsity and Dimension
by Swagato Sanyal
Vol 14, Article 22 (pp 1-17)
On Multiparty Communication with Large versus Unbounded Error
by Alexander A. Sherstov
Vol 14, Article 21 (pp 1-23)
Separation of Unbounded-Error Models in Multi-Party Communication Complexity
by Arkadev Chattopadhyay and Nikhil S. Mande
Vol 14, Article 20 (pp 1-29)
Simplified Separation of Information and Communication
by Anup Rao and Makrand Sinha
Vol 14, Article 14 (pp 1-29)
Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
by Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
Vol 14, Article 6 (pp 1-73) [CCC17 Spec Issue]
Trading Information Complexity for Error
by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
Vol 13, Article 7 (pp 1-18)
A Communication Game Related to the Sensitivity Conjecture
by Justin Gilmer, Michal Koucký, and Michael Saks
Vol 12, Article 10 (pp 1-35)
Robust Lower Bounds for Communication and Stream Computation
by Amit Chakrabarti, Graham Cormode, and Andrew McGregor
Vol 12, Article 9 (pp 1-23) [APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities
by Mika Göös and Thomas Watson
Vol 11, Article 19 (pp 471-489)
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
by Joshua Brody and Kasper Green Larsen
Vol 10, Article 5 (pp 107-131)
Competing-Provers Protocols for Circuit Evaluation
by Gillat Kol and Ran Raz
Vol 8, Article 16 (pp 369-374) [NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
Vol 8, Article 8 (pp 197-208)
The Communication Complexity of Gap Hamming Distance
by Alexander A. Sherstov
Vol 6, Article 10 (pp 227-245)
A Separation of NP and coNP in Multiparty Communication Complexity
by Dmitry Gavinsky and Alexander A. Sherstov
Vol 6, Article 9 (pp 201-225)
Separating Deterministic from Randomized Multiparty Communication Complexity
by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel
Vol 4, Article 7 (pp 137-168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols
by Emanuele Viola and Avi Wigderson
Vol 4, Article 6 (pp 129-135)
The One-Way Communication Complexity of Hamming Distance
by T. S. Jayram, Ravi Kumar, and D. Sivakumar
Vol 3, Article 12 (pp 221-238)
An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval
by Alexander Razborov and Sergey Yekhanin
Vol 3, Article 11 (pp 211-219)
The Randomized Communication Complexity of Set Disjointness
by Johan Håstad and Avi Wigderson
Vol 1, Article 4 (pp 47-79)
Quantum Search of Spatial Regions
by Scott Aaronson and Andris Ambainis
Vol 1, Article 1 (pp 1-28)
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson