## Hardness of approximation — Lecture 2

Actually part of the blog post on Lecture 1 was presented in Lecture 2. The main theme of lecture 2 was the following:

- We showed that the PCP theorem is equivalent to the NP-hardness of several gap problems, Gap-Max-E3SAT and Gap-LabelCover in particular. The last post has shown that Gap-Max-E3SAT is NP-hard. To show that Gap-Max-LabelCover is NP-hard for some constant $\rho$ is not difficult: put all variables on the left, clauses on the right, connect a variable and a clause if the variable belongs to the clause, labels for clauses are 001,010, …, 111 corresponding to combinations of literals which satisfies the clause; labels for variables are 001 or 010 which “stand for” TRUE or FALSE; finally, the constraint on an edge “projects” the clause’s label to the literal’s truth assignment.
- The above reduction yields bipartite graphs which are 7-regular on the right, but may not be regular on the left, since each variable can appear in an arbitrary number of clauses. For our purposes, we also want left-regular bipartite instances, which can easily be done by reducing from Gap-Max-E3SAT(d). Check Luca Trevisan’s survey for a proof that Gap-Max-E3SAT(d) is NP-hard for some constant d. (Vazirani’s book also contains a proof with d=29, I think.) The proof involves a very nice (but standard) application of expanders.
- A natural PCP verifier for the Gap-LabelCover problem can be viewed as a verifier of a 2-player 1-round game (2P1R)
- Then, Raz’s Parallel Repetition theorem can be applied to exponentially reduce the soundness of the PCP verifier for Gap-LabelCover. Since this result will be used to construct Hastad’s 3-bit PCP, we formally state it here.

Theorem (Raz’s Gap-LabelCover):Given any , there exists an alphabet with size for which Gap-LabelCover is NP-hard. Moreover, bipartite graph instances of this Gap-LabelCover problem can be assumed to be -regular on the left and -regular on the right where are constants. Furthermore, the constraint for every edge of the graph satisfies the projection property, i.e. it checks if , where are the labels for respectively.

leave a comment