|
Volume 4, Article 7 (pages 137-168) Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols by Emanuele Viola and Avi Wigderson |
|
Volume 4, Article 6 (pages 129-135) The One-Way Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar |
|
Volume 3, Article 12 (pages 221-238) An Ω(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval by Alexander Razborov and Sergey Yekhanin |
|
Volume 3, Article 11 (pages 211-219) The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson |
|
Volume 1, Article 1 (pages 1-28) Limitations of Quantum Advice and One-Way Communication by Scott Aaronson |