Expanders, Property Testing and the PCP theorem

Hardness of approximation — Lecture 3 & 4

Posted in lectures by HQN on March 27, 2009

We proved

Theorem (Hastad 1997)

NP = PCP_{1-\epsilon, 1/2+\delta}[O(\log n), 3] for any given \epsilon, \delta > 0.

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.)

  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.
  3. The completeness of the verifier is straightforward.
  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.

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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: