|
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 3, Article 10 (pages 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri and Martin Pál |
■
|
|
Volume 3, Article 9 (pages 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing by Maria-Florina Balcan and Avrim Blum |
|
Volume 3, Article 8 (pages 159-177)
Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek and Petr Škovroň |
|
Volume 3, Article 7 (pages 129-157)
Quantum Versus Classical Proofs and Advice by Scott Aaronson and Greg Kuperberg |
|
Volume 3, Article 6 (pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |
|
Volume 3, Article 5 (pages 81-102)
An Exponential Separation between Regular and General Resolution by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart |
|
Volume 3, Article 4 (pages 61-79)
A Simple PromiseBQP-complete Matrix Problem by Dominik Janzing and Pavel Wocjan |
|
Volume 3, Article 3 (pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma |
|
Volume 3, Article 2 (pages 25-43)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek |
|
Volume 3, Article 1 (pages 1-23)
Censorship Resistant Peer-to-Peer Networks by Amos Fiat and Jared Saia |