Click here to download the complete program
| Wednesday, January 5, 2011 | ||||||
| 0900 | 0930 | Registration | ||||
| 0915 | 0945 | Tea/Coffee | ||||
| 1000 | 1100 | Richard M. Karp [Keynote Talk] (slides) | ||||
| Effective Heuristics for NP-Hard Problems Arising in Molecular Biology | ||||||
| 1100 | 1130 | Tea/Coffee | ||||
| 1130 | 1230 | Sanjeev Arora [Keynote Talk] (slides) | ||||
| Semidefinite Programming and Approximation Algorithms: A Survey | ||||||
| 1230 | 1400 | Lunch | ||||
| 1400 | 1500 | David Steurer (slides) | ||||
| Algorithms for Unique Games and Related Problems | ||||||
| 1500 | 1505 | Break | ||||
| 1505 | 1605 | Mohit Singh (slides) | ||||
| A Randomized Rounding Approach to the Traveling Salesman Problem | ||||||
| 1605 | 1630 | Tea/Coffee | ||||
| 1630 | 1730 | Ravi Kannan (slides) | ||||
| Questions and Algorithms for Tensors | ||||||
| 1730 | 1800 | Amit Deshpande (slides) | ||||
| Approximability of Subspace Approximation | ||||||
| Thursday, January 6, 2011 | ||||||
| 0930 | 1000 | Tea/Coffee | ||||
| 1000 | 1100 | R. Ravi (slides) | ||||
| Matching Based Augmentations for Approximating Connectivity Problems | ||||||
| 1100 | 1130 | Tea/Coffee | ||||
| 1130 | 1230 | Sanjeev Arora (slides) | ||||
| Algorithms for Approximating Graph Expansion and Connections to Geometry | ||||||
| 1230 | 1400 | Lunch | ||||
| 1400 | 1500 | David Steurer (slides) | ||||
| Graph Expansion and the Unique Games Conjecture | ||||||
| 1500 | 1505 | Break | ||||
| 1505 | 1605 | Lorenzo Orecchia (slides) | ||||
| Fast Spectral Algorithms for Graph Partitioning and Graph Decomposition | ||||||
| 1605 | 1630 | Tea/Coffee | ||||
| 1630 | 1730 | Subhash Khot (slides) | ||||
| Introduction to Hardness of Approximation and Probabilistically Checkable Proofs | ||||||
| 1730 | 1800 | Saket Saurabh (slides) | ||||
| Slightly Superexponential Parameterized Problems | ||||||
| Friday, January 7, 2011 | ||||||
| 0930 | 1000 | Tea/Coffee | ||||
| 1000 | 1100 | Subhash Khot (slides) | ||||
| Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry | ||||||
| 1100 | 1130 | Tea/Coffee | ||||
| 1130 | 1230 | Prasad Raghavendra (slides) | ||||
| How to Round Any CSP? | ||||||
| 1230 | 1400 | Lunch | ||||
| 1400 | 1500 | Nikhil Devanur (slides) | ||||
| The Steiner Tree Problem | ||||||
| 1500 | 1505 | Break | ||||
| 1505 | 1605 | Sambuddha Roy (slides) | ||||
| Primal Dual Approximation Algorithms | ||||||
| 1605 | 1630 | Tea/Coffee | ||||
| 1630 | 1730 | Kamal Jain (slides) | ||||
| Online Bipartite Matching via a Primal-Dual Technique for Convex Programs | ||||||
| 1730 | 1800 | Vinayaka Pandit (slides) | ||||
| Local Search Based Approximation Algorithms for Facility Location Problems | ||||||
| Saturday, January 8, 2011 | ||||||
| 0930 | 1000 | Tea/Coffee | ||||
| 1000 | 1100 | R. Ravi (slides) | ||||
| Iterative Methods in Combinatorial Optimization | ||||||
| 1100 | 1130 | Tea/Coffee | ||||
| 1130 | 1230 | Subhash Khot (slides) | ||||
| On the Unique Games Conjecture | ||||||
| 1230 | 1400 | Lunch | ||||
| 1400 | 1500 | Prasad Raghavendra (slides) | ||||
| Complexity of Constraint Satisfaction Problems: Exact and Approximate | ||||||
| 1500 | 1505 | Break | ||||
| 1505 | 1605 | Prahladh Harsha (slides) | ||||
| Inapproximability Results from Label-Cover Variants and Other Hardness Assumptions | ||||||
| 1605 | 1630 | Tea/Coffee | ||||
| 1630 | 1730 | Madhur Tulsiani (slides) | ||||
| Introduction to LP and SDP Hierarchies | ||||||
| 1730 | 1800 | L. Sunil Chandran (slides) | ||||
| Rainbow Colouring of Graphs | ||||||
| Sunday, January 9, 2011 | ||||||
| 0930 | 1000 | Tea/Coffee | ||||
| 1000 | 1100 | Amit Kumar (slides) | ||||
| Scheduling to Minimize Weighted Flow-Time | ||||||
| 1100 | 1130 | Tea/Coffee | ||||
| 1130 | 1230 | Naveen Garg (slides) | ||||
| Fast Combinatorial Algorithms for Solving Positive Linear Programs | ||||||
| 1230 | 1400 | Lunch | ||||