Luca Trevisan, UC Berkeley, USA

Hard Combinatorial Problems: Theory
A typical way to "cope" with the intractability of NP-hard optimization problems is to design algorithms that find solutions whose cost or value is close to the optimum. In several interesting cases, it is possible to prove that even finding good approximate solutions is as hard as finding optimal solutions, and hence unlikely to be doable via efficient algorithms. Such "inapproximability" results are the topic of this course.

Almost all such results are proved using the PCP Theorem (and its several variants), one of the deepest theorems in computational complexity. We will see the statement of the PCP Theorem, briefly sketch Irit Dinur's recent new proof of it, and how to use the PCP Theorem to derive inapproximability results for problems such as Max Cut, Max Clique, and the Traveling Salesman Problem.

We will then state stronger variants of the PCP Theorem, and see how to use them to prove tight or nearly tight inapproximability results for a number of problems.

References
Sanjeev Arora, How NP Got a New Definition: A Survey of Probabilistically Checkable Proofs, Proceedings of the International Congress of Mathematicians, Beijing , 2002. Available online http://arxiv.org/abs/cs.CC/0304038

Irit Dinur, The PCP theorem by gap amplification, J. ACM 54(3), 2007. Available online http://eccc.hpi-web.de/eccc-reports/2005/TR05-046/index.html

Luca Trevisan, Inapproximability of Combinatorial Optimization Problems, Chapter in "Optimisation Combinatiore 2," (Vangelis Paschos, Editor), Hermes, 2005. Available online http://front.math.ucdavis.edu/0409.6043