Notes of Irit Dinur’s lecture nr 3

Today, we complete the proof of the PCP theorem. Recall we show a reduction from {3}-COLORING to GAP{(1,1-\epsilon)}{3}-COLORING. We do it recursively, in {O(\log n)} rounds. Each round doubles {unsat=1-sat}, and size of graph is multiplied at most by a constant. It consists in 3 steps. The first one is innocuous (make graph regular and expanding; does not require zig-zag, inserting expanders in place of high degree vertices makes the graph regular, then adding the edges of an expander with same vertex set suffices for the needed expansion). The second one, gap amplification, can be thought of as a derandomized parallel repetition. It increases the number of colors. The third, alphabet reduction, brings back to a {3}-COLORING instance. The main tool for this is called composition.

Gap amplification consists in replacing vertices by their {t}-neighborhoods. Each vertex becomes aware of the badly colored edges in its {t}-neighborhood, this increases the proportion of bad edges in any coloring. Alphabet reduction works in the opposite way, it spreads vertices equipped with big labels into a cloud of vertices with 3 colors. This is Yoga!


1. Gap amplification


The vertex set does not change. Edge change: the edges of the new graph {G'} correspond to length {t} paths in original graph {G}.

The new colors (call them labels) encode {3}-colorings of {t}-neighborhoods. The constraints check local consistency. The proof that a perfect coloring of {G} gives rise to a perfect labeling of {G'} is straightforward.

The proof that

\displaystyle  \begin{array}{rcl}  unsat(G)>\delta>0 \quad \Rightarrow\quad unsat(G')>t\delta \end{array}

is much harder, it involves expansion. In one sentence, given a coloring of {G}, let {E^*} be the set of ill-colored edges. Then the set of ill-labelled edges of {G'} is related to the {t}-neighborhood of {E^*}, which thanks to expansion, is much larger that {E^{*}}. Here are details. The precise consequence of expansion we need is

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(\textrm{random path of length }t\textrm{ hits }E^*)\geq\Omega(\delta t). \end{array}

Given a labelling {A} of {G'}, we must show that {\geq\delta t} fraction of edges are ill-labelled. Define a coloring {a} of {G} by plurality (poll neighbors for their colors according to a random walk requirted to stop at each step with probability {1/t}, choose the color which occurs most frequently). Let {E^*} be the set of ill-colored edges of {a}. Choose a random path of length {t} in {G}, conditioned on containing an edge from {E^*}. The probability of the corresponding constraint in {G'} to be false is constant.


2. Alphabet reduction


Let {uv} be an edge of {G'}. The corresponding constraint {\phi} reads colors in a certain subgraph {G_{uv}} of {G}. Denote by {\alpha} (resp. {\beta}) the colors read in {t}-neighborhood of {u} (resp. {v}). {\phi(\alpha,\beta)=1} iff {\alpha} and {\beta} are valid colorings in {G_{uv}}.

Our next goal is to convert {\phi} into a bunch of local coloring predicates {c_i} over {\alpha} and {\beta} so that

\displaystyle  \begin{array}{rcl}  \phi(\alpha,\beta)=1 &\Rightarrow&\textrm{ all }c_i \textrm{ accept}\\ \phi(\alpha,\beta)=1 &\Rightarrow&\textrm{ the fraction of }c_i \textrm{'s that reject is }>\gamma. \end{array}

This looks circular, we are exactly back to our original PCP problem. But at a much smaller scale, depending on {t} only, so we are allowed to use an exponential size PCP, like the telephone bill PCP of my first lecture. This is our first encounter with a composition of PCPs. Prahladh Harsha will continue explaining composition. Recall the parallel between {q}-CSP’s and PCP verifiers. Composition is easier to describe in the language of PCP verifiers. So his talk will deal with PCP verifiers.


3. Questions


Question: How does one get sharp inapproximability bounds ? Answer: Raghavendra can do it for CSPs, but only conditionnally to UGC.

Linial: this work measures failure by a fraction of unsatisfied constraints. For me, the most natural formulation of the coloring problem is: what number of colors can we achieve in polytime. This is a different measurement, and little is known. Best lower bound is 5! Answer: UGC lower bound is {\Omega(\log n)}.






About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged , . Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s