## Hardness of approximation — Lecture 3 & 4

We proved

Theorem (Hastad 1997)NP = PCP for any given .

The outline of the proof is as follows. (This exact outline will be used at least one more time, starting from a slightly different version of LabelCover.)

- We start from the NP-hard problem Gap-Max-LabelCover, and design a 3-bit PCP verifier for it (with logarithmic randomness).
- The verifier expects labels to be encoded with the (binary) long code, which is a map LC, where . Each -vector of length can be viewed as the truth table of a function . Thus, the long code LC of a symbol is also one such function. In particular, it is the
*dictator function*LC. 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. - The completeness of the verifier is straightforward.
- For soundness, we prove the contra-positive, meaning if the test passes with high probability, then there’s a labelling satisfying -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.

Bellare-Goldreich-Sudan introduced the long code. This is an excellent expository paper on many ideas we have and will discuss. For Fourier analysis of boolean functions, O’Donnell’s tutorial at STOC is a good starting point.

leave a comment