Theory of Computing, Volume 2

Volume 2, Number 1, 2006

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