1. Reductions among CSPs
Let me repeat what a -CSP is. It is a constraint satisfaction problem, i.e. there are boolean variables . An instance is a collection of -ary constraints, i.e. boolean functions of subsets of variables each. Notation: for an instance , is the maximum fraction of constraints that can be simultaneously sarisfied by an assignment of variables.
Example 1 3SAT is a -CSP. MAX CUT is a -CSP. -COLORING is a -CSP provided one accepts -valued variables.
PCP theorem says that for all these CSPs, there is an inapproximability ratio. Indeed, these problems reduce to each others.
Example 2 Reducing -COLORING to 3SAT.
This uses a tiny gadget: coding -valued variables by sets (of size ) of boolean variables, and cooking up a set of -ary constraints translating the -ary constraint on -valued variables expressing .
Example 3 Reducing -COLORING to LABEL COVER.
An instance of LABEL COVER is a bipartite graph, two sets of labels and and a constraint for each edge telling which pairs of colors at its endpoints are allowed.
If is -colorable, then .
If is at most -colorable, then .
So reduction apriori induces a loss on inapproximability ratios. We want to avoid that, i.e. amplify gaps instead.
Sequential repetition, i.e. launching the PCP verifier independantly times improves the soundness (probability of false acceptance) to . On the CSP side, the corresponding operation amounts to replacing a set of constraints by
If , then . However, the arity has been multiplied by . The cost of reducing back to -arity kills the benefit of sequential repetition. So this trivial gadget does not help.
One possible way out of this vicious circle is the use of samplers, i.e. selecting only randomly chosen -tuples of constraints. We can even derandomize sequential repetition, using expanders…
An other, more efficient, way is parallel repetition.
Example 4 Parallel repetition of LABEL COVER.
Let be a bipartite graph, part of a LABEL COVER instance. Then is a bipartite graph as follows. Put an edge between and iff there are edges between for all . A labelling is consistent if it is consistent coordinatewise.
Ran Raz’s theorem will be stated precisely on wednesday afternoon.
Theorem 1 If an instance is satisfiable, so is . If is -satisfiable, is -satisfiable.
Note that this theorem cannot be derandomised (Feige and Kilian).
3. Proof of PCP theorem
3.1. Scheme of proof
We want to reduce -COLORING to GAP--COLORING.
Start with a graph . If is not -coloring, . That’s a small gap, we want to amplify it until it gets independant on . We do this recursively: at each round, we want to double the gap. After rounds, we shall be done. Each doubling round will have 3 steps.
- Regularisation (some innocuous preprocessing).
- Amplification by parallel repetition.
- Alphabet reduction.
3.2. Amplification step
Keep the same set of vertices, take as new edges walks of length . Get a multi-graph. Thus the adjacency matrix is taken to its -th power. -colorings are taken to -colourings, wher as follows: the new colour of a vertex encodes all the colors of its neighbours of radius in original graph . Constraints
Proposition 2 Unsatisfaction gap increases by a definite factor, that gets for large enough.
This looks a bit like parallel repetition, but it differs in that the size of the instance is merely multiplied by a constant, whereas parallel repetition would change into .
You may think of it as as a derandomized form of parallel repetition.
3.3. Alphabet reduction
To iterate the procedure, one needs to convert back the multigraph with a -coloring into a graph with a -coloring.
This is more complicated. It involves composition, an idea that has not been exploited enough so far.