**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 13SAT 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 2Reducing -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 3Reducing -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.

**2. Repetition **

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 4Parallel 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 1If 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 2Unsatisfaction 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.