# Expanders, Property Testing and the PCP theorem

## Hardness of approximation — Lecture 2

Posted in lectures by HQN on March 27, 2009

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$(1,\rho)$ 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 $\tau > 0$, there exists an alphabet $\Sigma$ with size $|\Sigma| = poly(1/\tau)$ for which Gap-LabelCover$(1,\tau)$ is NP-hard. Moreover, bipartite graph instances of this Gap-LabelCover problem can be assumed to be $d_1$-regular on the left and $d_2$-regular on the right where $d_1,d_2$ are constants. Furthermore, the constraint $h_{u,v}$ for every edge $(u,v)$ of the graph satisfies the projection property, i.e. it checks if $L(u) = h_{u,v}(L(v))$, where $L(u), L(v)$ are the labels for $u, v$ respectively.