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 |
|
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 V. 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 |