Complexity Reading Group - Spring 2008

This semester we plan to discuss papers related to the themes listed below. The list of papers may keep growing as the semester progresses. We will meet at 3:30 pm on Thursdays in 606 Soda Hall.

Schedule

• Feb 7: Local Global Tradeoffs in Mertic Embeddings (Madhur)
  If you want to read the paper, note that we will focus more on the lower bound part (Section 3).


• Feb 14: No meeting


• Feb 21: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1 (Per)


• Feb 28: Per will continue on the Khot-Vishnoi paper


• Mar 6: Completeness Classes in Algebra (Salil)


• Mar 13: Elusive Functions and Lower Bounds for Arithmetic Circuits (Omid)
  


• Mar 20: Omid will continue on elusive functions and circuit lower bounds
  


• Mar 27: No reading group (spring break)
  


• Apr 3: No reading group


• Apr 10:  Algebrization: A New Barrier in Complexity Theory (James)


• Apr 17:  James will continue on Algebrization


• Apr 24:  Approximating the Cut-Norm via Grothendieck's inequality (Albert)


• May 8:  Linear Equations Modulo 2 and the L_1 Diameter of Convex Bodies (Thomas)


• May 15:  Separation of Multilinear Circuit and Formula Size (Kai-Min)

Coming attractions

• Connections between metric embeddings and integrality gaps
• Local Global Tradeoffs in Mertic Embeddings
  (Moses Charikar, Konstantin Makarychev and Yury Makarychev)
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into L1
  (Subhash Khot and Nisheeth Vishnoi)

• Lower bounds for arithmetic circuits
• Elusive Functions and Lower Bounds for Arithmetic Circuits
  (Ran Raz)
• Completeness Classes in Algebra
  (Leslie Valiant)
• Separation of Multilinear Circuit and Formula Size
  (Ran Raz)


• Optimization of quadratic and cubic forms
• Approximating the Cut-Norm via Grothendieck's inequality
  (Noga Alon and Asaf Naor)
• Quadratic forms on Graphs
  (Noga Alon, Konstantin Makarychev, Yury Makarychev and Asaf Naor)
• Linear Equations Modulo 2 and the L_1 Diameter of Convex Bodies (Subhash Khot and Asaf Naor)