Expanders, Property Testing and the PCP theorem

Hardness of approximation — Lecture 3 & 4

Posted in lectures by HQN on March 27, 2009

We proved

NP = PCP$_{1-\epsilon, 1/2+\delta}[O(\log n), 3]$ for any given $\epsilon, \delta > 0$.
1. We start from the NP-hard problem Gap-Max-LabelCover$_\Sigma(1,\tau)$, and design a 3-bit PCP verifier for it (with logarithmic randomness).
2. The verifier expects labels to be encoded with the (binary) long code, which is a map LC$: \Sigma \to \{0,1\}^{2^m}$, where $|\Sigma|=m$. Each $01$-vector of length $2^m$ can be viewed as the truth table of a function $f: \{0,1\}^m \to \{0,1\}$. Thus, the long code LC$(a)$ of a symbol $a$ is also one such function. In particular, it is the dictator function LC$(a)(x_1,\dots,x_m) = x_a$. Then, the verifier chooses an edge of the graph at random, pick 3 bits from the (supposed) long codes of the two labels and perform a simple linear test on those bits.
4. For soundness, we prove the contra-positive, meaning if the test passes with high probability, then there’s a labelling satisfying $> \tau$-fraction of the edges of the LabelCover instance. To show that such a labelling exists, we use the probabilistic method to choose a random labelling based on the Fourier coefficients of the functions representing (and perhaps pretending to be) long codes.