Materials Research Center (MRC) Auditorium,
Indian Institute of Science, Bangalore, India
January 5–9, 2011
The focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.
The school will bring together key contributors in this area to discuss these modern methods to a large research audience. In addition, the school will also have talks and open sessions for sharing new research and directions in approximability.
Confirmed Speakers
|
Sanjeev Arora (Princeton) |
Amit Kumar (IIT Delhi) |
| Sunil Chandran (Indian Institute of Science) | Lorenzo Orecchia (Berkeley) |
| Amit Deshpande (Microsoft Research) | Vinayaka Pandit (IBM IRL) |
| Nikhil Devanur (Microsoft Research) | Prasad Raghavendra (Georgia Tech) |
|
Naveen Garg (IIT Delhi) |
R. Ravi (Carnegie Mellon) |
| Prahladh Harsha (TIFR) | Sambuddha Roy (IBM IRL) |
|
Kamal Jain (Microsoft Research) |
Saket Saurabh (IMSc, Chennai) |
|
Ravi Kannan (Microsoft Research) |
Mohit Singh (McGill University) |
| Richard Karp (Berkeley) | David Steurer (Microsoft Research) |
|
Subhash Khot (New York University) |
Madhur Tulsiani (Princeton/IAS) |
Schedule
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 | ||||
Admission |
| Admission to the school is by application or invitation only. There is no fee required to be paid to attend the school. |
|
Note The selection process for admission is complete, and all selected applicants have been notified by email. |
Organization |
|
Co-Chairs |
|
|
Support from IISc and MSR India |
|
Event Sponsors
- Microsoft Research India (MSR India)
- Indo-German Max-Planck Center for Computer Science (IMPECS)
Related Links
Contact Us
If you have questions about this event, please send email to Microsoft External Research - India
