|
Article 12
(pages 221-238)
An Ω(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval by Alexander Razborov, Sergey Yekhanin |
|
Article 11
(pages 211-219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad, Avi Wigderson |
|
Article 10
(pages 197-209)
An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem by Chandra Chekuri, Martin Pál |
|
Article 9
(pages 179-195)
Approximation Algorithms and Online Mechanisms for Item Pricing by Maria-Florina Balcan, Avrim Blum |
|
Article 8
(pages 159-177)
Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek, Petr Škovroň |
|
Article 7
(pages 129-157)
Quantum Versus Classical Proofs and Advice by Scott Aaronson, Greg Kuperberg |
|
Article 6
(pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |
|
Article 5
(pages 81-102)
An Exponential Separation between Regular and General Resolution by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart |
|
Article 4
(pages 61-79)
A Simple PromiseBQP-complete Matrix Problem by Dominik Janzing, Pawel Wocjan |
|
Article 3
(pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, Amnon Ta-Shma |
|
Article 2
(pages 25-43)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige, Eran Ofek |
|
Article 1
(pages 1-23)
Censorship Resistant Peer-to-Peer Networks by Amos Fiat, Jared Saia |