## Course Announcement: Limits of approximation algorithms : PCPs and Unique Games
- Spring Semester (2009-10)

Time: Thurs 14:00-16:30

Location: A-212 (STCS, TIFR)

Instructor:

Homepage:
http://tifr.res.in/~prahladh/teaching/2009-10/limits

# Limits of approximation algorithms : PCPs and Unique Games

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.

In this course, we will see some of the recent developments in the
area of probabilistically checkable proofs and unique games with
emphasis on their application towards inapproximability results. In
particular, Topics covered will include a mixture of earlier and very
recent work, such as:

- Proof of PCP Theorem
- Linearity testing, low degree testing
- Raz's Parallel Repetition Theorem
- Inapproximability results: linear equations, lattice problems
- Hardness of network/flow problems
- Unique Games hardness of MAX-CUT

For a flavor of the topics that will be covered, see a recent 2-day
workshop on the same topic organized at DIMACS (http://dimacs.rutgers.edu/Workshops/Limits/).
The course will be a more detailed version of this workshop.

Instructor: