Time: Fridays, 1pm

Venue: CCB 101

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) |

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.

- Aggregating Inconsistent Information: Ranking and Clustering,STOC 2005. (pdf)

- Fitting Tree Metrics: Hierarchial Clustering and Phylogeny, FOCS 2005 (pdf)

- 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)

Theory Reading Group Coordinator for 2006 - Deeparnab Chakrabarty