Time: Tues, Fri 14:00-15:30
Location: TBD
Instructor:
Homepage:
http://tifr.res.in/~prahladh/teaching/2014-15/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 two module course, we will see some of the recent developments in the area of probabilistically checkable proofs and their application towards inapproximability results.
The two-module course, as the name suggests will consist of two half-courses. The two half courses will be on related topics, but will be independent and self-contained. Students can credit one or both half-courses. Each module will comprise 12-15 lectures of 1.5 hrs each.
The first module will be devoted to the PCP Theorem, its proof and variants. Topics covered will include a mixture of earlier and very recent work, such as:
The second module will be devoted to applications of the PCP theorem towards hardness of approximation. 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 the previous avatar of this course at TIFR/IMSc (Limits of Approximation Algorithms (TIFR/IMSc course, 2010 Winter/Summer semester) and a 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 |
|