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