## 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.

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}$

$\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.