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 S. 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 |