Time: Thurs 14:00-16:30
Location: A-212 (STCS, TIFR)
Instructor:
Homepage:
http://tifr.res.in/~prahladh/teaching/2009-10/limits
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:
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:
| Prahladh Harsha |
|