DIMACS Tutorial on Limits of Approximation Algorithms: PCPs and Unique Games

July 20 - 21, 2009
DIMACS Center, CoRE Building, Rutgers University

Organizers:
Prahladh Harsha, University of Texas, Austin
Moses Charikar, Princeton University
This tutorial is jointly sponsored by the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus on Algorithmic Foundations of the Internet, and the Center for Computational Intractability with support from the National Security Agency and the National Science Foundation.

Workshop Program:

Monday, July 20, 2009

 8:30 -  9:20  Continental breakfast and registration

 9:20 -  9:30  Welcome 
               Tami Carpenter, DIMACS Associate Director

 9:30 - 10:50  Approximation algorithms for NP-hard optimization
               problems: An introduction
               Sanjeev Arora, Princeton University

10:50 - 11:10  Break

11:10 - 12:30  Limits of approximability and the PCP Theorem: 
               An Introduction
               Dana Moshkovitz, Princeton University

12:30 -  2:00  Lunch

 2:00 -  3:00  Approximation algorithms for network/flow problems
               Matthew Andrews, Bell Labs

 3:00 -  3:15  Break

 3:15 -  4:15  Hardness results for approximating network/flow problems 
               Lisa Zhang, Bell Labs

 4:15 -  4:45  Break

 4:45 -  6:15  Proof of the PCP Theorem (part 1) 
               Prahladh Harsha, University of Texas, Austin

 6:30 -  8:00  Dinner

 8:00 -  9:30  Informal post-dinner session including
               Primer on Fourier Analysis
               Dana Moshkovitz

Tuesday, July 21, 2009

 8:30 -  9:00  Continental Breakfast

 9:00 - 10:20  Proof of the PCP Theorem (part 2) 
               Prahladh Harsha

10:20 - 10:40  Break

10:40 - 12:00  Hastad's 3-Bit PCP
               Subhash Khot, New York Univresity

12:00 -  1:20  Lunch

 1:20 -  2:40  Semidefinite Programming and Unique Games 
               Moses Charikar, Princeton University

 2:40 -  3:00  Break

 3:00 -  4:30  Unique Games Hardness for MAX-CUT
               Subhash Khot
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on July 20, 2009.