Corelab Seminar

Xaris Angelidakis (NTUA)
Some Techniques in Hardness of Approximation

In this talk, we will present some techniques about getting inapproximability results. Such a result is a statement that a specific NP-hard problem is NP-hard to approximate within a certain factor. We will show the connection between inapproximability and multi-prover interactive proofs, which first appeared in a seminal paper in 1991 by Feige, Goldwasser, Lovasz, Safra, and Szegedy, where they showed that results on interactive proofs could be used to indicate the hardness of approximation of the MAX-CLIQUE in a graph. We will then make a brief introduction to the PCP theorem, and we will conclude our talk by giving some optimal PCP constructions due to Hastad that yield tight inapproximability results for MAX-Ek-SAT and MAX-Ek-LIN-p (for both, k \geq 3), and improved inapproximability results for MAX-E2-SAT, MAX-CUT and MAX-DI-CUT.