Lemma about low-degree influences

On Monday we didn't quite have enough time to show that for any f : {-1,1}^m -> [-1,1], the number of coordinates with C-degree influence on f at least tau is at most C/tau.

The proof is quite literally one line, so I'll post it here.

The Unique Games Conjecture

At the recent FOCS conference, Subhash Khot gave a tutorial on the Unique Games Conjecture. You can see the slides of his talk here.

Homework back

Hi all -- just wanted to let you know that we hope to have graded homework returned and solutions posted by Wednesday.

Proof of the PCP Theorem

We concatenated the notes for Lectures 1 through 9 into one giant Proof of the PCP Theorem. Thanks very much to all the scribes involved. Note that although the we did the "easy" new Irit Dinur proof, the PDF file still runs to 64 pages!

Questions / discussion about the homework

The comments section of this post is for discussion of the homework problems.

A hint for questions homework #6 and #7

If you need some hints for problems 6b), 6d), and 7c), you can look at this sample calculation in which I work through a similar problem in explicit detail.

PCPs, gaps, and hardness factors

I just wanted to go over one more time the connection between PCPs, gaps, and hardness factors. It took a while for me to "get" this myself when I learned it, so I think it bears repeating. Also I hope it will help with understanding questions #1 and #4 on the homework.

1. Let Phi be a class of predicates; e.g., Phi = 3-variable-linear-equations-mod-2, or Phi = Majorities-of-3-literals, or Phi = ORs-of-3-literals. Then the following statements are exactly equivalent:

(a) "Every problem in NP has a PCP with completeness c, soundness s, and a verifier using predicates from Phi."
(b) "3-Colorability has a PCP with completeness c, soundness s, and a verifier using predicates from Phi."
(c) "Gap-Max-Phi_{c, s} is NP-hard."
(d) "There is a polynomial time reduction which, given a graph G, spits out M many tests from Phi over a bunch of "variables", such that (i) if G is 3-colorable, then there is an assignment to the variables satisfying at least cM of the tests; (ii) if G is not 3-colorable, then every assignment to the variables satisfies fewer than sM of the tests."

(a) <=> (b) is just because 3-Colorability is NP-complete, and polynomial-time reductions can be "built into" PCP systems.

(c) <=> (d) is just because (d) is really the definition of (c).

(b) <=> (d) involves some thought about what the definitions mean. "Indices of proof positions" in (b) correspond to "variables" in (d); "proofs" in (b) correspond to "assignments" in (d); and "picking a random test and understand the probability that it passes" in (b) corresponds to "writing down all the tests and counting how many of them are satisfied" in (d).

------------------------------

2. Further, the statement (c) "Gap-Max-Phi_{c,s} is NP-hard" implies (but is *not* equivalent to) the statement
(e) "There is no poly-time (s/c)-approximation algorithm for the Max-Phi problem unless P = NP."

Proof of (c) => (e): Suppose (c) is true, and further suppose that there *is* a polynomial-time algorithm A which, when given as input M tests from Phi over variables, always outputs an assignment satisfying at least an s/c fraction of whatever the optimum assignment satisfies. We will show that the existence of this algorithm A means that 3-Colorability is solvable in polynomial time, and hence P = NP.

So why is 3-Colorability in polynomial time in this case? Here is the polynomial time algorithm B which solves 3-Colorability:

• Given a graph G, run the reduction guaranteed by statement (c); this spits out a list of M many tests from Phi.
• Run algorithm A on this list of tests, producing some assignment alpha to the variables.
• Check if alpha satsifies at least sM of the tests. If so, output "YES, G is 3-colorable." If not, output "NO, G is not 3-colorable."

Since the reduction guaranteed by (c) is polynomial time, and A is polynomial time, the overall algorithm B is polynomial time. Why is it correct? If the input graph G is 3-colorable, then the reduction guaranteed by (c) spits out a list of M tests with the guarantee that there is an assignment satisfying at least cM of them. I.e., the optimal assignment gives at least cM. Thus by the guarantee of the supposed approximation algorithm A, it will return an assignment alpha satisfying at least (s/c) * (cM) = sM tests. Thus B will correctly say "YES". On the other hand, if G was not 3-colorable, then the reduction guaranteed by (c) will spit out a list where *every* assignment to the variables satisfies fewer than sM of the tests. In this case, no matter what assignment A outputs, there's no way it will satisfy as many as sM tests; hence B will correctly output "NO".

Not all hardness of approximation needs the PCP Theorem

Almost all the best hardness-of-approximation results we know require at least the PCP Theorem. But not all do... Here are three examples:

1. Minimum Metric k-Center: In this problem you are given an undirected graph with distances satisfying the triangle inequality. You are also given an integer k. Your task is to pick k "centers" (vertices in the graph) with the goal of minimizing the maximum distance of any vertex to a center.

As early as 1979, Hsu & Nemhauser showed by a simple NP-completeness reduction that it's hard to tell the difference between instances with value 1 and instances with value 2 (even in graphs where all edges have distances 1 and 2). This was also shown by Plesník in 1980. This immediately implies there is no (2-eps)-approximation algorithm. On the other hand, there is also an easy 2-approximation, first given by Gonzalez in 1985. This gives a sharp hardness-of-approximation result, as noted in 1985 (seven years before the PCP Theorem!) by Hochbaum & Shmoys.

2. In 1993, right after the PCP Theorem had come out, Håstad, Philips, and Safra considered the problem of satisfiability of multilinear degree two equations over GF[p]. (We tangentially touched on his problem, with p = 2, in the construction of Assignment Testers.) In the paper the authors give an easy (1/p - 1/p^2)-approximation algorithm. They also use a cute argument based on epsilon-biased spaces (which we will see on Monday for SET-COVER; I think the argument can also be based on error-correcting codes) to show that it is NP-hard to give a (1/p + eps)-approximation for any eps > 0 (even polynomially small). The main reason why HPS are able to give this essentially-sharp result is that the quadratic equations don't have to be "local", as they do in PCP-type constructions; they many depend on many variables.

3. Since 3-colorability is NP-hard, we know that it is hard to distinguish graphs with chromatic number 3 from graphs with chromatic number 4. Khanna, Linial, and Safra improved on this in 1993, giving an intricate PCP-based proof that it is hard to distinguish chromatic number 3 from chromatic number 5. This is the strongest result we know about coloring 3-colorable graphs. However, it turns out that KLS's use of the PCP Theorem was unnecessary; in 2000, Khanna and Guruswami gave a new proof of the same result using nothing but a classical NP-completeness reduction from Independent-Set.