Notes of Guy Kindler’s lecture nr 3


1. The coordinated dictatorship test


Recall our dictatorship test. It depends on a parameter {\epsilon>0}. Choose uniformly at random vectors {x}, {y\in\{\pm 1\}^n}, {z\in N_{\epsilon}(n)} (meaning independant {z_i} with {\mathop{\mathbb P}(z_i =-1)=\epsilon}) and {t\in\{\pm 1\}}.

Then query {f(x)}, {f(y)} and {f(uxyz)} and accept iff {tf(x)f(y)f(txyz)=1}. Completeness is {1-\epsilon} and soundness is {1-\epsilon-\alpha}.


1.1. First attempt


A coordinated dictatorship test is designed to recognize wether two boolean functions {f} and {g} are dictators and are the same dictator. Our first attempt was as follows. Given the same distribution on {x,y,z,u} as above, query {f(x)}, {g(y)} and {f(txyz)} and accept iff {tf(x)g(y)f(txyz)=1}.

Completeness is {1-\epsilon} and soundness is {1-\epsilon-\alpha}, meaning that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(\textrm{accept})>1-\epsilon-\alpha \Rightarrow \exists i \textrm{ such that }H(f,w_i),\,H(g,w_i)<\sqrt{\alpha}. \end{array}

This is not sufficient, since we want soundness {\frac{1}{2}+\delta}. And our analysis assumed {\alpha\ll\epsilon}.


1.2. Introducing a random decoder


Use the idea of randomized decoding. Now our coordinated dictatorship test has three parameters {\epsilon>0}, {\delta>0} and {\phi{\mathbb R}_+ \rightarrow{\mathbb R}_+}. Data are two boolean functions {f} and {g} and a permutation {\pi} of {[n]}. We want a test that makes {3} queries to {f}, {g}, and detects wether {f=w_i}, {g=w_j} with {j=\pi(i)}. The test involves a random decoder {\psi}, i.e. a random map from boolean functions to indices in {[n]}.

Completeness: If {f=w_i} and {g=w_j} with {j=\pi(i)}, then {\mathop{\mathbb P}(\textrm{accept})\geq 1-\epsilon}.

Soundness: If {\mathop{\mathbb P}(\textrm{accept})\geq \frac{1}{2}+\delta}, then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(\pi(\psi(f))=\psi(g))\geq\phi(\delta). \end{array}

Last time, we described a random decoder {\psi} such that the corresponding coordinated dictatorship test satisfies the above requirement with {\psi(\delta)=\delta^4 /100}.


2. Reduction from Unique games to GAP {3}LIN{(2)}


2.1. UGC


A Unique games instance {I} is the data of a graph, a distribution over edges, and for each edge {uv}, a bijection {\pi_{uv}:[k]\rightarrow[k]}. Say edge {uv} is satisfied by an assignment {\mathcal{A}:V\rightarrow[k]} if {\pi_{uv}(\mathcal{A}(u))=\mathcal{A}(v)}. In other words, the value of assignment {\mathcal{A}} on instance {I} is

\displaystyle  \begin{array}{rcl}  I(\mathcal{A})=\mathop{\mathbb P}_{uv\in E}(\pi_{uv}(\mathcal{A}(u))=\mathcal{A}(v)). \end{array}

The gap problem {(\epsilon,\delta)}-UG{(k)} is to distinguish between

  • YES : {\exists \mathcal{A}} such that {I(\mathcal{A})\geq 1-\epsilon};
  • NO : {\forall \mathcal{A}}, {I(\mathcal{A})\leq \delta}.

Subhash Khot’s Unique Games Conjecture states that {\forall\epsilon>0}, {\forall\delta>0}, {\exists k=k(\epsilon,\delta)} such that {(\epsilon,\delta)}-UG{(k)} is NP-hard.

Assuming UGC, we want to show hardness of {(1-\epsilon,\frac{1}{2}+\delta)}-GAP {3}LIN{(2)}. So given an instance {I'} of {(\epsilon',\delta')}-UG{(k)}, we shall construct an instance {I} of {(1-\epsilon,\frac{1}{2}+\delta)}-GAP {3}LIN{(2)}, in such a way that YES instances are mapped to YES instances and NO instances are mapped to NO instances.


2.2. The gadget


There will be {2^k} variables for every vertex {u\in V} in our {3}LIN{(2)} instance. We view these boolean variables as the values of some (variable) boolean function {f_u :\{\pm 1\}^k \rightarrow\{\pm 1\}}. Whence the (a bit strange) notation {f_u (x)} for these variables.

We define a distribution over equations as follows. Pick an edge {uv\in E} at random. Pick {x,y,z,t} at random as in the test. Generate equation {tf_u (x)f_{v}(\pi_{uv}(y))f_u (txyz)=1}. It is indeed a linear equation over {{\mathbb Z}/2{\mathbb Z}} with three variables.


2.3. Completeness


Assume that {I'} is a YES case, i.e. that there exists an assignment {\mathcal{A}} with {I'(\mathcal{A}')\geq 1-\epsilon'}. Define an assigment {\mathcal{A}} of {I} as follows. For all {x\in\{\pm 1\}^k}, all boolean functions {f_u},

\displaystyle  \begin{array}{rcl}  \mathcal{A}(f_u (x))=x_{\mathcal{A}'(u)}. \end{array}

In other words, we decide that {f_u} is a dictator at coordinate {\mathcal{A}'(u)}. With probability {\geq 1-\epsilon'} over the choice of edge {uv}, {\pi_{uv}(\mathcal{A}'(u))=\mathcal{A}'(v)}. In this case, the probability, over equations, that the test accepts, is {1-\epsilon}. So {I(\mathcal{A})\geq 1-\epsilon'-\epsilon}.


2.4. Soundness


Assume that {I} is not a NO case, i.e. there exists an assignment {\mathcal{A}} such that {I(\mathcal{A})>\frac{1}{2}+\delta}. We must construct an assignment {\mathcal{A}'} with {I'(\mathcal{A}')>\delta'}. We choose random decoding parameters {(\epsilon,\frac{\delta}{2},\phi)}. {\mathcal{A}} gives us a function {f_u :\{\pm 1\}^k\rightarrow \{\pm\}} for every vertex {u}. Generate {\mathcal{A}'} randomly by applying the random decoding procedure {\psi} to {f_u}, i.e. we set

\displaystyle  \begin{array}{rcl}  \mathcal{A}'(u)=\psi(f_u). \end{array}

By assumption, on average over edges {uv}, {\mathcal{A}} satisfies the random equation

\displaystyle  tf_u (x)f_{v}(\pi_{uv}(y))f_u (txyz)=1

with probability {>\frac{1}{2}+\delta}. So, by Markov inequality, for at least {\delta/2} fraction of edges {uv}, the test accepts with probability {>\frac{1}{2}+\frac{\delta}{2}}. The soundness of the coordinated dictatorship test implies that for these edges, {\mathop{\mathbb P}(\psi(f_u)=\psi(f_v \circ\pi_{uv})>\phi(\delta)}. So the expected fraction of edges {uv} satisfied by {\mathcal{A}'} is {\geq \frac{\delta}{2}\phi(\frac{\delta}{2})=:\delta'}. So there is an assignment {\mathcal{A}'} such that {I'(\mathcal{A}')>\delta'}. I.e. {I'} is not a NO instance of Unique games.


2.5. Conclusion


The UGC-inapproximability bound obtained is optimal. Indeed, a random assignment of variables solves any {3}LIN{(2)} instance with probability {1/2}. More generally, Uri Zwick proved (by constructing SDPs) that all {3}-variable constraint satisfaction problems admit {2}-approximations.


3. NP-hardness of approximating {3}LIN{(2)}


This is Johan Håstad’s 1998 theorem.


3.1. Black box: hardness of LABEL COVER


We start from LABEL COVER{(k)}. Instances {I'} are directed graphs, for each edge, a constraint {\pi_{uv}:[k]\rightarrow[k]} (which need not be {1-1}). An assignment is a {[k]}-valued function {\mathcal{A}'} on vertices. An edge is satisfied by {\mathcal{A}} if {\pi_{uv}(\mathcal{A}'(u)=\mathcal{A}'(v)}. The value of assignment {\mathcal{A}} is

\displaystyle  \begin{array}{rcl}  I'(\mathcal{A}')=\mathop{\mathbb P}_{uv}(uv \textrm{ is satisfied}). \end{array}

The gap problem {(1,\delta')}-LABEL COVER{(k)} amounts to deciding between

  • YES : {\exists \mathcal{A}'} such that {I'(\mathcal{A}')=1};
  • NO : {\forall \mathcal{A}}, {I'(\mathcal{A}')\leq \delta'}.

It follows from the work of many people (initially, the PCP and parallel repetition theorems, more direct proofs have been proposed recently by Moshkovitz and Raz, Dinur and Harsha) that for all {\delta'>0}, {\exists k} such that {(1,\delta')}-LABEL COVER{(k)} is NP-hard.


3.2. The test


To have a reduction from LABEL COVER{(k)} to {3}LIN{(2)}, we need an improved test and decoding procedure, since the constraint is not {1-1} any more.

Let {\pi:[k]\rightarrow[k]} be an arbitrary map.

Let {T(\epsilon,\pi)} be the following test. The data are two Boolean functions {f} and {g}. The test is designed to detect pairs of dictators which correspond to the same coordinate. So denote by {\pi^{-1}y=y'} where {y'_{i}=y_{\pi(i)}}.

Choose uniformly at random vectors {x}, {y\in\{\pm 1\}^n}, {z\in N_{\epsilon}(n)} and {t\in\{\pm 1\}}. Then query {f(x)}, {g(y)} and {f(ux\pi^{-1}(y)z)} and accept iff {tf(x)g(y)f(tx\pi^{-1}(y)z)=1}.


3.3. Completeness


Lemma 1

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(\textrm{accept})-\mathop{\mathbb P}(\textrm{accept})=\sum_{S\subset[n],\,|S|\,\mathrm{odd}}\hat{f}_S^2 \hat{g}_{\pi_2 (S)} (1-2\epsilon)^{|S|}, \end{array}

where {\pi_2 (S)} is the set of coordinates {j} such that {|S\cap\pi^{-1}(j)|} is odd.


Proof: Let {P=\mathop{\mathbb P}(\textrm{accept})}. Then

\displaystyle  \begin{array}{rcl}  2P-1&=&\sum_{S,\,T,\,R}\hat{f}_S \hat{g}_T \hat{f}_R \mathop{\mathbb E}(tw_S (x)w_T (y)w_R (tx\pi^{-1}(y)z))\\ &=&\sum_{T,\,|S|\,\mathrm{odd}}\hat{f}_S^2 \hat{g}_T \mathop{\mathbb E}(w_T (y)w_S (\pi^{-1}(y)))(1-2\epsilon)^{|S|}\\ &=&\sum_{T,\,|S|\,\mathrm{odd}}\hat{f}_S^2 \hat{g}_T \mathop{\mathbb E}(w_T (y)w_{\pi_2 (S)} (y))(1-2\epsilon)^{|S|}\\ &=&\sum_{|S|\,\mathrm{odd}}\hat{f}_S^2 \hat{g}_{\pi_2 (S)}(1-2\epsilon)^{|S|}. \end{array}


It follows that completeness is {\geq 1-\epsilon}. Also, if {\mathop{\mathbb P}(\textrm{accept})>\frac{1}{2}+\delta}, then for some odd size {S}, {\hat{f}_S^2 \hat{g}_{\pi_2 (S)}} is large.


3.4. Soundness


{f} and {g} play unsymmetric roles, but this does not matter. The decoding algorithm will be applied first to {f} and {g}, and then to {g} and {f}.

Now among all {S} with {|S|} of odd size {<\log_{1-2\epsilon}(\frac{\delta}{10})}, pick {S} at random with probability {\hat{f}_S^2} (discard large sets) and pick {i\in S} uniformly at random. Among all {T} with {|T|} of size {<\log_{1-2\epsilon}(\frac{\delta}{10})} and {\hat{g}_T >\frac{\delta}{3}}, pick {T} at random with probability {\hat{g}_S^2} (discard large sets) and pick {j\in T} uniformly at random.


\displaystyle  \begin{array}{rcl}  2\delta&<&\sum_{S\subset[n],\,|S|\,\mathrm{odd}}\hat{f}_S^2 \hat{g}_{\pi_2 (S)} (1-2\epsilon)^{|S|}\\ &\leq&\sum_{S\subset[n],\,|S|\,\mathrm{odd},\,|S|\leq\log_{1-2\epsilon}(\frac{\delta}{10})}\hat{f}_S^2 \hat{g}_{\pi_2 (S)} +\frac{\delta}{10}\\ &\leq&\sum_{|S|\,\mathrm{odd},\,|S|\leq\log_{1-2\epsilon}(\frac{\delta}{10}),\,\hat{f}_{\pi_2 (S)} >\frac{\delta}{3}}\hat{f}_S^2 \hat{g}_{\pi_2 (S)} +\frac{\delta}{3}+\frac{\delta}{10}, \end{array}

and this leads to

\displaystyle  \begin{array}{rcl}  \sum_{|S|\,\mathrm{odd},\,|S|\leq\log_{1-2\epsilon}(\frac{\delta}{10}),\,\hat{f}_{\pi_2 (S)} >\frac{\delta}{3}}\hat{f}_S^2 \hat{g}_{\pi_2 (S)}>\delta. \end{array}

So the probability that {S} is chosen for {f} and {g} is chosen for {g} is {\pi_2 (S)} is {\geq \frac{\delta^2}{3}}. Since {|S|} is odd, {\pi_2 (S)} is not empty, so the probability that the further choices {i} and {j} satisfy {\pi(i)=j} is {\geq \frac{\delta^2}{3\log_{1-2\epsilon}(\frac{\delta}{10})}}. This gives an upper bound on soundness.


3.5. Reduction from {(1,\delta')}-LABEL COVER{(k)} to {3}LIN{(2)}


Not essentially different from previous reduction.

Riikka Kangaslampi: {k} seems to play no role. Answer: that is right. It merely must be taken large to have NP-completeness.




Irit Dinur; Prahladh Harsha; Composition of low-error 2-query PCPs using decodable PCPs. FOCS 2009.

Dana Moshkovitz; Ran Raz; Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. Journal of Computational Complexity (to appear).

Uri Zwick; Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. Proc. of 9th SODA (1998), 201–210.



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 Course 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