The 2011 School on Approximability

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)  


Click here to download the complete program

Wednesday, January 5, 2011


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


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


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


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



Support from IISc and MSR India 

  • G. Rangarajan (Convener, IISc Mathematics Initiative) 
  • Vidya Natampally (Microsoft Research India, Director of Strategy)
  • Ashwani Sharma (Microsoft Research India, Program Manager, External Research)