Articles under category:
Communication Complexity
Communication Complexity
ToC Library Graduate Surveys 4 (2011) 27 pages
Variations on the Sensitivity Conjecture
by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov
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
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
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
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
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
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
Optimality of Correlated Sampling Strategies
by Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, and Madhu Sudan
Vol 14, Article 22 (pp 1-17)
On Multiparty Communication with Large versus Unbounded Error
by Alexander A. Sherstov
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
The Randomized Communication Complexity of Set Disjointness
by Johan Håstad and Avi Wigderson
Vol 1, Article 1 (pp 1-28)
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson