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}

\Box

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.

 

References

 

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.

 

Advertisements

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 http://www.math.ens.fr/metric2011/
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:

WordPress.com Logo

You are commenting using your WordPress.com 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