Volume 2 (2006)
Vol 2, Article 1 (pp 1-18)
All Quantum Adversary Methods are Equivalent
by Robert Špalek and Mario Szegedy
Vol 2, Article 2 (pp 19-51)
Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Vol 2, Article 3 (pp 53-64)
An Improved Approximation Ratio for the Covering Steiner Problem
by Anupam Gupta and Aravind Srinivasan
Vol 2, Article 4 (pp 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Vol 2, Article 5 (pp 91-120)
Iterative Construction of Cayley Expander Graphs
by Eyal Rozenman, Aner Shalev, and Avi Wigderson
Vol 2, Article 6 (pp 121-135)
Separation of Multilinear Circuit and Formula Size
by Ran Raz
Vol 2, Article 7 (pp 137-146)
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
Vol 2, Article 8 (pp 147-172)
On Learning Random DNF Formulas Under the Uniform Distribution
by Jeffrey C. Jackson and Rocco A. Servedio
Vol 2, Article 9 (pp 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties
by Eldar Fischer and Lance Fortnow
Vol 2, Article 10 (pp 185-206)
Learning Restricted Models of Arithmetic Circuits
by Adam Klivans and Amir Shpilka
Vol 2, Article 11 (pp 207-224)
Embedding the Ulam metric into 1
by Moses Charikar and Robert Krauthgamer
Vol 2, Article 12 (pp 225-247)
Matrix Approximation and Projective Clustering via Volume Sampling
by Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang
Vol 2, Article 13 (pp 249-266)
Correlation Clustering with a Fixed Number of Clusters
by Ioannis Giotis and Venkatesan Guruswami
List of Editors