New Directions in Approximation Algorithms (2013)

Symposia

When

January 27, 2013
All Day
January 28, 2013
All Day
January 29, 2013
All Day
January 30, 2013
All Day
January 31, 2013
All Day
February 1, 2013
All Day
February 2, 2013
All Day

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

Centers

Collaborative Projects

New Directions in Approximation Algorithms (2013)

When

More Events

DMFT-QE Symposium: November 2, 2026

DMFT-QE Symposium: December 7, 2026

DMFT-QE Symposium: January 11, 2027

Research We Fund

Resources

Shared Programs

Resources for Applying

More Events