### 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.

The theory of NP-completeness is one of the cornerstones of
complexity theory in theoretical computer science. Approximation
algorithms offer an important strategy for attacking computationally
intractable problems, and approximation algorithms with performance
guarantees have been designed for a host of important problems such as
balanced cut, network design, Euclidean TSP, facility location, and
machine scheduling. Many simple and broadly-applicable approximation
techniques have emerged for some provably hard problems, while in
other cases, inapproximability results demonstrate that achieving a
suitably good approximate solution is no easier than finding an
optimal one. The celebrated PCP theorem established that several
fundamental optimization problems are not only hard to solve exactly
but also hard to approximate. This work shows that a broad class of
problems is very unlikely to have constant factor approximations, and
in effect, establishes a threshold for such problems such that
approximation beyond this threshold would imply P= NP. More recently,
the unique games conjecture of Khot has emerged as a powerful
hypothesis that has served as the basis for a variety of optimal
inapproximability results.

This tutorial targets graduate students and others who are new to
the field. It will aim to give participants a general overview of
approximability, introduce them to important results in
inapproximability, such as the PCP theorem and the unique games
conjecture, and illustrate connections with mathematical programming
techniques.

List of speakers:

- Matthew Andrews (Alcatel-Lucent Bell Laboratories)
- Sanjeev Arora (Princeton University)
- Moses Charikar (Princeton University)
- Prahladh Harsha (University of Texas, Austin)
- Subhash Khot (New York University)
- Dana Moshkovitz (Princeton University)
- Lisa Zhang (Alcatel-Lucent Bell Laboratories)

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on July 13, 2009.