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