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