Reading Group, Fall 2006

Time: Fridays, 1pm
Venue: CCB 101
Schedule of Talks
Date Speaker Paper
8th September Deeparnab Chakrabarty Minimum Bounded Degree Spanning Trees (pdf)
15th September Nayantara Bhatnagar Approximate Counting by Dynamic Programming (pdf)
22nd September Rishi Saket Algorithms for Unique Games (pdf)
29th September Gagan Goel Algebraic Structures and Algorithms for Matching and Matroid Problems. (pdf)
6th October Ashok Ponnuswami Local versus Global properties of Metric Spaces (pdf)
13th October Amit  Improved Approximation Algorithms for Large Matrices via Random Projections (pdf)
3rd November Tejas Iyer Error Correction over Real Vectors (pdf)
17th November Shiva Kintali TSP and a recent result on the integrality gap of the Held-Karp relaxation. (pdf)
21st November Nisheeth Vishnoi The Lovasz-Schrijver lift and project method for linear and semi-definite programming (pdf)
1st December Subruk Kalyanasundaram Graph Limits and Parameter Testing (pdf)

Suggested Papers
The following are meant to be only suggestions. Please feel free to present and suggest any paper which you think are interesting. Papers which raise questions are highly encouraged :) I am also including names of people who are willing to present the paper.

  • On the Capacity of Information Networks, SODA 2006 (pdf)
  • Papers on Correlation Clustering and Rank Aggregation:
                - Aggregating Inconsistent Information: Ranking and Clustering,STOC 2005. (pdf)
                - Fitting Tree Metrics: Hierarchial Clustering and Phylogeny, FOCS 2005 (pdf)
  • A local switch Markov chain on given degree graphs with application in connectivity of Peer-to-Peer networks, FOCS 2006 (pdf)
  • Complexity of Nash Equilibria in Non Zero Sum Games:
                - Settling the complexity of 2-player Nash Equilibrium, FOCS 2006 (pdf)
                - Computing Nash Equilibria: Approximation and Smoothed Complexity, FOCS 2006 (pdf)
                - Playing Large Games using Simple Strategies, EC 2003 (pdf)
  • The Effectiveness of Lloyd-type Methods for the k-Means Problem, FOCS 2006 (pdf)
  • Spectral Clustering with Limited Dependence (pdf)

    • Theory Reading Group Coordinator for 2006 - Deeparnab Chakrabarty