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.

## Participants

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 |