Communication Complexity

• Papers
  • Probabilistic Communication Complexity of Boolean Relations (R. Raz, A. Wigderson, FOCS 1989)
  • Monotone Circuits for Matching Require Linear Depth (R.Raz, A.Wigderson, STOC 1990)
  • Rounds in Communication Complexity Revisited (N. Nisan, A. Wigderson, STOC 1991)
  • Rounds in Communication Complexity Revisited (N. Nisan, A. Wigderson, SIAM JComp 1993)
  • On the 'Log-Rank' Conjecture in Communication Complexity (R.Raz, B.Spieker, FOCS 1993)
  • On Rank vs. Communication Complexity (Noam Nisan and Avi Wigderson, ECCC TR04-001)
  • The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem (Christoph Meinel, Stephan Waack, ECCC TR94-022)
  • On One-Round Randomized Communication Complexity (I. Kremer, N. Nisan and D. Ron, 1994)
  • The Communication Complexity of Threshold Gates (N. Nisan, 1994)
  • Non-deterministic Communication Complexity with Few Witnesses ( M. Karchmer, I. Newman, M. Saks, A. Wigderson, JCSS 1994)
  • A note on Rank vs. Communication Complexity (N. Nisan, A. Wigderson, Combinatorica 1995)
  • Super-Logarithmic Depth Lower Bounds via Direct Sum in Communication Complexity (M. Karchmer, R. Raz, A. Wigderson, CC 1995)
  • Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems (Christoph Meinel, Stephan Waack, ECCC TR95-034)
  • Some Bounds on Multiparty Communication Complexity of Pointer Jumping (Carsten Damm, Stasys Jukna, and Jiri Sgall, ECCC TR95-044)
  • Amortized Communication Complexity (T. Feder, E. Kushilevitz, M. Naor, and N. Nisan, SICOMP 1995)
  • [ww.cs.technion.ac.il/~eyalk/KKN.ps.Z:Fractional Covers and Communication Complexity:M. Karchmer, E. Kushilevitz, and N. Nisan, SIDMA 1995:04.06.05] (M. Karchmer, E. Kushilevitz, and N. Nisan, SIDMA 1995)
  • Fourier Analysis for Probabilistic Communication Complexity (R.Raz, CC 1995)
  • The `Log Rank'' Conjecture for Modular Communication Complexity (Christoph Meinel, Stephan Waack, ECCC TR96-017)
  • The Linear-Array Conjecture of Communication Complexity is False (E. Kushilevitz, N. Linial, and R. Ostrovsky, STOC 1996)
  • The Linear-Array Problem in Communication Complexity Resolved (Martin Dietzfelbinger, ECCC TR96-063)
  • On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations (Pavol Duris, Juraj Hromkovic, Jose D. P. Rolim, Georg Schnitger, ECCC TR97-029)
  • Direct Product Results and the GCD Problem, in Old and New Communication Models (I.Parnafes, R.Raz, A.Wigderson, STOC 1997)
  • Separation of the Monotone NC Hierarchy (R.Raz, P.McKenzie, FOCS 1997)
  • A Discrete Approximation and Communication Complexity Approach to the Superposition Problem (Farid Ablayev and Svetlana Ablayeva, ECCC TR98-050)
  • The Quantum Communication Complexity of Sampling (A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson, FOCS 1998)
  • Quantum vs. Classical Communication and Computation, H. Buhrman, R. CLeve, A. Wigderson, STOC 98 (04.06.05)
  • On Data Structures and Asymmetric Communication Complexity ( P. Miltersen, N. Nisan, S. Safra, A. Wigderson, JCSS 1998)
  • Exponential Separation of Quantum and Classical Communication Complexity (R.Raz, STOC 1999)
  • The BNS-Chung Criterion for Multi-Party Communication Complexity (R.Raz, CC 2000)
  • The Communication Complexity of Enumeration, Elimination, and Selection (Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet, TR01-019)
  • On Multi-Partition Communication Complexity of Triangle-Freeness (Stasys Jukna, Georg Schnitger, ECCC TR01-049)
  • Communication Complexity and Secure Function Evaluation (Moni Naor, Kobbi Nissim, ECCC TR01-062)
  • On Multipartition Communication Complexity (Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger, ECCC TR01-066)
  • The Communication Complexity of Approximate Set Packing and Covering (N.Nisan, ICALP 2002)
  • A tutorial on the Deterministic two-party Communication Complexity (Agostino Capponi, ECCC TR03-075)
  • Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information (Andris Ambainis, Ke Yang, ECCC TR03-082)
  • One-Way Communication Complexity of Symmetric Boolean Functions (Jan Arpe, Andreas Jakoby, Maciej Liskiewicz, ECCC TR03-083)
  • Quantum Communication Complexity of Symmetric Predicates (Alexander Razborov, in Izvestiya%3a Mathematics, Vol. 67, No 1, 2003, pages 145-159)
  • The Quantum Communication Complexity of Sampling (A. Ambainis, L. Schulman, A. Ta-Shma, Vazirani, A. Wigderson, SIAM JComp 2003)
  • Exponential Separation of Quantum and Classical One-Way Communication Complexity (Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis, ECCC TR04-036)
  • A note on the P versus NP intersected with co-NP question in communication complexity (Stasys Jukna, ECCC TR04-062)
  • Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a (Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis, ECCC TR04-120)
  • On the power of Quantum Proofs (R.Raz, A.Shpilka, CC 2004)
  • Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity (Paul Beame, Toniann Pitassi, Nathan Segerlind, ECCC TR05-053)
  • A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness (P. Beame, T. Pitassi, N. Segerlind, A. Wigderson, CCC05)
• Collections
  • Ran Raz's papers on communication complexity
• Books
  • Communication Complexity (Eyal Kushilevitz, Noam Nisan)
• Lecture notes
  • Circuit Complexity and Communication Complexity (Ran Raz,, IAS summer school 2004)
• Courses
  • Communication Complexity (236518) (Technion, Eyal Kushilevitz)

---

Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to <helger.lipmaa>gmail.com
NB! If you find any broken links, please be kind and report them to me together with their current location!

(C) Helger Lipmaa 1997-2009.