New Directions in Approximation Algorithms: January 27-February 2, 2013

Organizers: Sanjeev Arora, Uriel Feige, Michel Goemans & David Shmoys

Many of the striking advances in theoretical computer science over the past two decades concern
 approximation algorithms, which compute provably near-optimal solutions to NP-hard optimization problems.
 Yet the approximability of several fundamental problems such as TSP, Graph Coloring, Graph Partitioning etc.
remains an open question. For other problems the so-called PCP Theorems and more recently, the Unique Games
Conjecture (UGC), provide a complexity-theoretic explanation for the failure to design better algorithms.

A quick succession of papers in the past 5 years or so has yielded new ideas for algorithmic approaches that show
promise of leading to a resolution of the classic open problems, as well as possibly a refutation of the UGC itself.
 These new approaches use structural insights gained from mathematical programming relaxations, either linear
programming (LP) or semidefinite programming (SDP). They draw upon a more complete arsenal of techniques
than had been seen earlier in math programming: Markov Chain Monte Carlo sampling, spectral techniques
(focusing especially on higher eigenvalues of the graph spectrum), high dimensional geometry, local vs global
geometric theorems, etc. Within the past year, approximation techniques have also been used to make progress on
semirandom complexity, which is an important — and largely nonunderstood — notion between worst-case and
average-case complexity.


Sanjeev Arora Princeton University
Boaz Barak Microsoft Research, New England
Julia Chuzhoy Toyota Technological Institute at Chicago
Uriel Feige Weizmann Institute
Michel X. Goemans MIT
Venkatesan Guruswami Carnegie Mellon University
Johan Hastad KTH
Sampath Kannan Simons Foundation
Jonathan Kelner MIT
Subhash Khot NYU/Chicago
Monique Laurent Centrum Wiskunde & Informatica
James Lee Washington University
Laszlo Lovasz Eötvös Loránd University
Yury Makarychev Toyota Technological Institute at Chicago
Claire Matthieu ENS/Brown
Assaf Naor NYU
Shayan Oveis-Gharan Stanford University
Prasad Raghavendra Georgia Tech
David B. Shmoys Cornell University
Mohit Singh MSR-Redmond
David Steurer MSR-NERD/Cornell
Ola Svensson EPFL
Luca Trevisan Stanford University
Anke Van Zuijlen MPI/William & Mary