Notes of Guy Kindler’s lecture nr 2


1. Estimate on soundness of dictatorship test, continued


Recall our dictatorship test: Pick {x} and {y} uniformly at random, independantly. Let {z\sim N_{\epsilon}(k)}, and {u} uniform in {\{\pm 1\}}. Accept iff {uf(x)f(y)f(uxyz)=1}.

We have shown last time that if {P=\mathop{\mathbb P}(\textrm{accept})}, then

\displaystyle  \begin{array}{rcl}  2P-1=\sum_{S\subset [k],\,|S|\,\mathrm{odd}}(1-2\epsilon)^{|S|}\hat{f}_{S}^{3}. \end{array}

Observe that for the dictator {x_i}, only {\{i\}} gives a nonzero coefficient, so {P=1-2\epsilon}, as required for completeness.

For soundness, assume that {P\geq 1-\epsilon-\alpha}. Then

\displaystyle  \begin{array}{rcl}  \sum_{S\subset [k],\,|S|\,\mathrm{odd}}(1-2\epsilon)^{|S|}\hat{f}_{S}^{3}\geq 1-2\epsilon-2\alpha. \end{array}

Since {\sum_{\mathrm{all}\,S}\hat{f}_{S}^{2}=1}, there exists {S} with {|S|} odd such that {\hat{f}_{S}\geq 1-2\epsilon-2\alpha}. Think of {\alpha} as much smaller than {\epsilon}. Since {|\hat{f}_{S}|\leq 1}, This implies that {|S|=1}, i.e. there exists {i\in[n]} such that {S=\{i\}}, and

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_x (f(x)x_i)=\hat{f}_{\{i\}}\geq 1-2\alpha. \end{array}

In particular, most of the time, {f(x)=x_i}.

Remark 1 Let {f(x)=x_1 x_2 x_3}, then {\mathop{\mathbb P}(\textrm{accept})\geq (1-\epsilon)^3 \geq 1-3\epsilon}.

Indeed, {uf(x)f(y)f(uxyz)=z_1 z_3 z_3}. It looks bad ({f} passes the test with high probability). It is not so bad, since {f} is dominated by a few coordinates.

How can one express that a coordinate plays a prominent role in a boolean function ?


2. Random decoding


We describe a random procedure that associates a coordinate to a boolean function, i.e. a {[n]}-valued random variable. Consider subsets {S\subset[n]} of odd size, relatively small, i.e. {|S|\leq\log_{1-2\epsilon}(\frac{\delta}{10})}. Choose a subset of {[n]} with probability {\hat{f}_{S}^{2}}, discard it and replace it by {\{1\}} if it is even or large. Then take {i} unformly at random in {S}.

We try to test simultaneously two functions, decide wether they are dictators with the same variable.

Theorem 1 Let {f}, {g:\{\pm 1\}^n\rightarrow \{\pm 1\}} be distinct functions. Take {x}, {y} uniformly at random in {\{\pm 1\}^n}, {u} unformly at random in {\{\pm 1\}}, and {z\sim N_{\epsilon}(n)}. Accept iff {uf(x)g(y)f(uxyz)=1}.

The completeness of the test is {\geq 1-\epsilon}.

The soundness of the test is {\leq \frac{1}{2}+\delta}. Furthermore, if {i} and {j} denote the random decoding variables associated to {f} and {g} respectively, then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(i=j)>\frac{\delta^2}{100\log_{1-2\epsilon}(\delta/10)}, \end{array}

independently on {n}.


Proof: A similar calculation as before gives

\displaystyle  \begin{array}{rcl}  2\mathop{\mathbb P}(\textrm{accept})-1&=&\sum_{S\subset [k],\,|S|\,\mathrm{odd}}(1-2\epsilon)^{|S|}\hat{f}_{S}^{2}\hat{g}_{S}\\ &\leq&\sum_{S\subset [k],\,|S|\,\mathrm{odd},\,|S|\leq \log_{1-2\epsilon}(\delta/10)}\hat{f}_{S}^{2}\hat{g}_{S}+\frac{\delta}{10}\\ &\leq&\sum_{S\subset [k],\,|S|\,\mathrm{odd},\,|S|\leq \log_{1-2\epsilon}(\delta/10),\,\hat{g}_{S}>\delta/10}\hat{f}_{S}^{2}\hat{g}_{S}+\frac{2\delta}{10}\\ &\leq&\frac{10}{\delta}\sum_{S\subset [k],\,|S|\,\mathrm{odd},\,|S|\leq \log_{1-2\epsilon}(\delta/10),\,\hat{g}_{S}>\delta/10}\hat{f}_{S}^{2}\hat{g}_{S}^{2}+\frac{2\delta}{10}\\ &\leq&\frac{10}{\delta}\log_{1-2\epsilon}(\delta/10)\sum_{S\subset [k],\,|S|\,\mathrm{odd},\,|S|\leq \log_{1-2\epsilon}(\delta/10),\,\hat{g}_{S}>\delta/10}|S|^{-1}\hat{f}_{S}^{2}\hat{g}_{S}^{2}+\frac{2\delta}{10}\\ \end{array}

If {\mathop{\mathbb P}(\textrm{accept})>\frac{1}{2}+\delta}, then {2P-1\geq 2\delta}, and we get

\displaystyle  \begin{array}{rcl}  \frac{\delta^2 }{100\log_{1-2\epsilon}(\delta/10)}&\leq&\sum_{S\subset [k],\,|S|\,\mathrm{odd},\,|S|\leq \log_{1-2\epsilon}(\delta/10),\,\hat{g}_{S}>\delta/10}|S|^{-1}\hat{f}_{S}^{2}\hat{g}_{S}^{2}\\ &\leq&\mathop{\mathbb P}(i=j), \end{array}

since {\hat{f}_{S}^{2}\hat{g}_{S}^{2}} is the probability that {S} be selected by both the {f} and the {g}-decoder, and {|S|^{-1}\hat{f}_{S}^{2}\hat{g}_{S}^{2}} is the probability that both decoders select the same coordinate. \Box

Remark 2 We have played with a weird looking code: a number between {1} and {n} is coded by the corresponding dictator function in {n} variables. It sounds terrible as a code (although it has been used during one of the first space missions, due to its suitability to analogic treatment), but it is very easy to decode. This is what we have used.


3. From decoding to hardness of approximation


We tested wether {i=j}. Similarly, for any permutation {\pi:[n]\rightarrow[n]}, we can test wether {i=\pi(j)}.

Reduction from a unique games (with {k} labels) instance {I} requires constructing an instance {I'} of E{3}LIN{(2)}, i.e. a distribution over linear equations in {3}-variables. To every variable {u} of {I} and {x\in\{\pm 1\}^k}, we associate a variable of {I'} denoted by {f_u (x)} (may look like a strange notation…). To define the distribution on equations, pick an edge {(v,w)} of {I} at random. Pick {x}, {y} uniformly at random in {\{\pm 1\}^k}, {u} uniformly at random in {\{\pm 1\}}, {z\sim N_{\epsilon}(k)} and view

\displaystyle  \begin{array}{rcl}  uf_w (x)f_v (\pi_{vw}(y))f_w (uxyz)=1 \end{array}

as an equation with unknowns {f_w (x)}, {f_v (\pi_{vw}(y))} and {f_w (uxyz)}.

What we have to show next time is

Completeness: If there exists an assignment {a} for {I} satisfying more than {1-\epsilon} fraction of constraints, then there exists an assignment {a'} for {I'} satisfying more than {1-2\epsilon} fraction of constraints.

Soundness: If there exists an assignment {a'} for {I'} satisfying more than {\frac{1}{2}+\delta} fraction of constraints, then there exists an assignment {a} for {I} satisfying more than {\frac{\delta^2}{100\log_{1-2\epsilon}(\delta/10)}} fraction of constraints.





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