#LyX 1.5.3 created this file. For more info see http://www.lyx.org/ \lyxformat 276 \begin_document \begin_header \textclass article \begin_preamble \usepackage{amsfonts} \usepackage{hyperref} \newtheorem{define}{Definition} %\newcommand{\Z}{{\bf Z}} %\usepackage{psfig} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \input{defs.tex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Definitions: If you want to add definitions commands and macros to the %% scribe, please do it in this space %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end_preamble \language english \inputencoding auto \font_roman default \font_sans default \font_typewriter default \font_default_family default \font_sc false \font_osf false \font_sf_scale 100 \font_tt_scale 100 \graphics default \paperfontsize 11 \spacing single \papersize default \use_geometry false \use_amsmath 1 \use_esint 0 \cite_engine basic \use_bibtopic false \paperorientation portrait \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip medskip \quotes_language english \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \author "" \author "" \end_header \begin_body \begin_layout Standard \begin_inset ERT status collapsed \begin_layout Standard %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end_layout \begin_layout Standard \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard %% Heading: In the parentheses below, write the sequential number of the \end_layout \begin_layout Standard \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard %% talk, the talk date, the name of the speaker, and the name or names of \end_layout \begin_layout Standard \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard %% whoever wrote the scribe (seperated by commas). \end_layout \begin_layout Standard \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset ERT status collapsed \begin_layout Standard \backslash lecture \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard { \end_layout \end_inset 11 \begin_inset ERT status collapsed \begin_layout Standard } \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard { \end_layout \end_inset May 19, 2008 \begin_inset ERT status collapsed \begin_layout Standard } \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard { \end_layout \end_inset Guy Kindler \begin_inset ERT status collapsed \begin_layout Standard } \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard { \end_layout \end_inset Eric Shellef \begin_inset ERT status collapsed \begin_layout Standard } \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end_layout \begin_layout Standard \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset ERT status collapsed \begin_layout Standard %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end_layout \begin_layout Standard \end_layout \end_inset \begin_inset ERT status collapsed \begin_layout Standard %% Body: from here on it's your territory - write your scribe here. \end_layout \begin_layout Standard \end_layout \end_inset \end_layout \begin_layout Section Hardness of approximation of E3-LIN-2 \end_layout \begin_layout Standard We refresh from last lecture the definition of the unique game problem with parameter \begin_inset Formula $k$ \end_inset , UG[ \begin_inset Formula $k$ \end_inset ], and of the Unique Games Conjecture (UGC). \end_layout \begin_layout Standard An instance \begin_inset Formula $I$ \end_inset of the problem comprises of a set of vertices, \begin_inset Formula $V$ \end_inset , and a set of directed edges, \begin_inset Formula $E$ \end_inset . Each edge \begin_inset Formula $e\in E$ \end_inset has an associated weight, \begin_inset Formula $w(e)>0$ \end_inset such that \begin_inset Formula $w(E)=\sum_{e\in E}w(e)=1$ \end_inset and an associated permutation \begin_inset Formula $\tau_{e}\in S_{k}$ \end_inset . An assignment \begin_inset Formula $A$ \end_inset for \begin_inset Formula $I$ \end_inset is \begin_inset Formula $A:V\to[k]$ \end_inset , and \begin_inset Formula $val_{I}(A)=\mathbb{P}_{e=(u,v)\sim E}\left[A(v)=\tau_{e}(A(u))\right]$ \end_inset . \end_layout \begin_layout Standard UGC states that for all small enough \begin_inset Formula $\delta,\epsilon>0$ \end_inset there is a \begin_inset Formula $k$ \end_inset such that distinugishing between an instance \begin_inset Formula $I\in\mbox{UG}[k]$ \end_inset that satisfies \begin_inset Formula $opt(I)\ge1-\epsilon$ \end_inset and an instance \begin_inset Formula $J\in\mbox{UG}[k]$ \end_inset for which \begin_inset Formula $opt(J)\le\delta$ \end_inset is NP-hard. \end_layout \begin_layout Standard While hardness for UG[ \begin_inset Formula $k$ \end_inset ] is only conjectured, we can actually prove it for LC[ \begin_inset Formula $k$ \end_inset ] --- where we have a general function instead of a permutation. Note that LC[ \begin_inset Formula $k$ \end_inset ] is hard with a \begin_inset Formula $(1,\delta)$ \end_inset -gap, which is clearly impossible in the case of UG. \end_layout \begin_layout Standard The goal of this lecture is to prove that UGC implies hardness of approximation for E3-LIN-2, which was defined in the previous lecture. \end_layout \begin_layout Standard \begin_inset ERT status collapsed \begin_layout Standard \backslash begin{theorem} \end_layout \end_inset \end_layout \begin_layout Standard Assuming UGC, for all small enough \begin_inset Formula $\delta,\epsilon>0$ \end_inset , it is NP-hard to distinguish between instances of E3-LIN-2 which satisfy \begin_inset Formula $opt(I)>1-\epsilon$ \end_inset and instances where \begin_inset Formula $opt(I)<\frac{1}{2}+\delta$ \end_inset . \begin_inset ERT status collapsed \begin_layout Standard \backslash end{theorem} \end_layout \end_inset \end_layout \begin_layout Standard We prove Theorem 1 by showing a (polynomial-time) reduction r[ \begin_inset Formula $k$ \end_inset ] from an instance \begin_inset Formula $I$ \end_inset in UG[ \begin_inset Formula $k$ \end_inset ] to an instance \begin_inset Formula $I'$ \end_inset of E3-LIN-2 such that \begin_inset Formula \begin{equation} opt(I)>1-\epsilon\implies opt(I')>1-2\epsilon\label{eq:YesToYes}\end{equation} \end_inset \end_layout \begin_layout Standard and \begin_inset Formula \begin{equation} opt(I)<\frac{\delta^{3}}{32\log_{(1-2\epsilon)}(\nicefrac{\delta}{4})}\implies opt(I')<\frac{1}{2}+\delta,\label{eq:NoToNo}\end{equation} \end_inset and the number of equations in \begin_inset Formula $I'$ \end_inset is bounded by \begin_inset Formula $C(\delta,\epsilon)\cdot\left|V\left(I\right)+E(I)\right|$ \end_inset . \end_layout \begin_layout Standard Given the set of vertices in \begin_inset Formula $I$ \end_inset , \begin_inset Formula $V(I)$ \end_inset , we generate a set of variables \begin_inset Formula $V'=\left\{ f_{v}(x)\right\} _{\substack{v\in V\qquad\\ x\in\left\{ \pm1\right\} ^{k}} }$ \end_inset . Thus \begin_inset Formula $\left|V'\right|=2^{k}\left|V\right|$ \end_inset . \end_layout \begin_layout Standard For \begin_inset Formula $E'$ \end_inset we pick \begin_inset Formula $e=(u,v)\sim E$ \end_inset and apply the permutation-test with parameter \begin_inset Formula $\epsilon$ \end_inset on \begin_inset Formula $f_{u},f_{v}$ \end_inset and the permutation \begin_inset Formula $\tau_{e}$ \end_inset , using the random parameters \begin_inset Formula $x,y\sim\mu_{1/2}^{(k)},z\sim\mu_{\epsilon}^{(k)},\eta\sim\mu_{1/2}^{(1)}$ \end_inset . \end_layout \begin_layout Standard Explicitly, we have \begin_inset Formula \[ E'=\left\{ f_{u}(x)f_{u}(y)=\eta f_{v}\left(\eta\tau_{e}\left(xyz\right)\right)\ :\ x,y,z\in\left\{ \pm1\right\} ^{k},\eta\in\left\{ \pm1\right\} ,e=(u,v)\in E\right\} ,\] \end_inset \end_layout \begin_layout Standard \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none where the weight of each equation is \begin_inset Formula $w\left((u,v)\right)2^{-3k}(1-\epsilon)^{\left|\{i:z_{i}=1\}\right|}\epsilon^{\left|\{i:z_{i}=-1\}\right|}$ \end_inset . Notice that \begin_inset Formula $\left|E'\right|=2^{3k+1}\left|E\right|$ \end_inset . \end_layout \begin_layout Subsection \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none Correctness of Reduction \end_layout \begin_layout Standard To complete the proof of the theorem, it is enough to show that the above reduction has properties \begin_inset LatexCommand eqref reference "eq:YesToYes" \end_inset and \begin_inset LatexCommand eqref reference "eq:NoToNo" \end_inset . \end_layout \begin_layout Standard First we show \begin_inset LatexCommand eqref reference "eq:YesToYes" \end_inset (completeness): \end_layout \begin_layout Standard Assume \begin_inset Formula $opt(I)>1-\epsilon$ \end_inset , and let \begin_inset Formula $A$ \end_inset be an assignment with \begin_inset Formula $val_{I}(A)>1-\epsilon$ \end_inset . Define \begin_inset Formula $A'$ \end_inset for \begin_inset Formula $I'$ \end_inset by setting \begin_inset Formula $A'(f_{v}(x))=\chi_{A(v)}(x)$ \end_inset . Fixing the assignment \begin_inset Formula $A'$ \end_inset , the notation we chose for the variables of the E3-LIN-2 instance allow us to view them as functions of the binary word \begin_inset Formula $x$ \end_inset . Thus, somewhat abusing notation, we identify \begin_inset Formula $f_{v}(x)$ \end_inset with its assignment \begin_inset Formula $A'(f_{v}(x))$ \end_inset . \begin_inset Formula \begin{eqnarray*} val_{I'}(A') & = & \mathbb{P}_{e\sim E'}\left[A'\mbox{ satisfies }e\right]\\ & \ge & \mathbb{P}_{e\sim E}\left[A\mbox{ satisfies }e\right]\mathbb{P}_{x,y,z,\eta}\left[f_{u}(x)f_{u}(y)=\eta f_{v}\left(\eta\tau_{e}\left(xyz\right)\right)\ |\ A\mbox{ satisfies }e\right]\\ & \ge & val_{I}(A)(1-\epsilon)\ge(1-\epsilon)^{2}>1-2\epsilon,\end{eqnarray*} \end_inset where conditioning on \begin_inset Formula $A$ \end_inset satisfying \begin_inset Formula $e$ \end_inset gave us that \begin_inset Formula $f_{v}=\chi_{A(v)}=\chi_{\tau_{e}(A(u))}=f_{u}$ \end_inset , and thus we may use the \begin_inset Formula $1-\epsilon$ \end_inset completeness of the permutation test. \newline \end_layout \begin_layout Standard To prove \begin_inset LatexCommand eqref reference "eq:NoToNo" \end_inset , we show the contrapositive, namely, that if \begin_inset Formula $r[k](I)=I'$ \end_inset , and \begin_inset Formula $\exists A'$ \end_inset with \begin_inset Formula $val_{I'}(A')\ge\frac{1}{2}+\delta$ \end_inset then \begin_inset Formula $opt(I)\ge\frac{\delta^{3}}{32\log_{(1-2\epsilon)}(\nicefrac{\delta}{4})}$ \end_inset . The assignment \begin_inset Formula $A'$ \end_inset defines a function \begin_inset Formula $f_{v}(\cdot)$ \end_inset for each \begin_inset Formula $v\in V$ \end_inset . To use soundness of the permutation test, we need to show there are enough edges \begin_inset Formula $(u,v)\in E$ \end_inset for which \begin_inset Formula $f_{v}(x),f_{u}(x)$ \end_inset satisfy their equations in \begin_inset Formula $I'$ \end_inset with good probability on a random \begin_inset Formula $x$ \end_inset . This will be a consequence of our assumption on \begin_inset Formula $val_{I'}(A')$ \end_inset which lower bounds the weight of the \begin_inset Formula $\left|E'\right|$ \end_inset equations that are satisfied. Using soundness, we will randomly decode \begin_inset Formula $f_{v}(\cdot)$ \end_inset for each vertex in \begin_inset Formula $V$ \end_inset and prove that the average value of our random assignment to \begin_inset Formula $I$ \end_inset is lower bounded by the function of \begin_inset Formula $\delta$ \end_inset appearing in \begin_inset LatexCommand ref reference "eq:NoToNo" \end_inset . Since there is a deterministic choice of \begin_inset Formula $A$ \end_inset for which \begin_inset Formula $val(I)$ \end_inset is at least the average, this will prove what we want. \end_layout \begin_layout Standard For each \begin_inset Formula $v\in V$ \end_inset choose \begin_inset Formula $D^{v}$ \end_inset at random from either \begin_inset Formula $D_{1}(f_{v})$ \end_inset or \begin_inset Formula $D_{2}(f_{v})$ \end_inset (the permutation test decoders for the first and second word) to obtain a word \begin_inset Formula $\chi_{i}$ \end_inset , and let \begin_inset Formula $A$ \end_inset assign \begin_inset Formula $i$ \end_inset to \begin_inset Formula $v$ \end_inset (if we get \begin_inset Formula $\bot$ \end_inset we assign an arbitrary label). \end_layout \begin_layout Standard We use the following lemma to prove that \begin_inset Formula $\mathbb{E}\left[val_{I}(A)\right]$ \end_inset is large. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Standard \backslash begin{lemma} \end_layout \end_inset Let \begin_inset Formula $X$ \end_inset be an r.v. satisfying \begin_inset Formula $0\le X\le1$ \end_inset , then \begin_inset Formula \begin{equation} \mathbb{P}\left[X\ge\alpha\right]\ge\frac{\mathbb{E}\left[X\right]-\alpha}{1-\alpha}\label{eq:lem2}\end{equation} \end_inset \begin_inset ERT status open \begin_layout Standard \backslash end{lemma} \end_layout \end_inset \begin_inset ERT status open \begin_layout Standard \backslash begin{proof} \end_layout \end_inset \begin_inset Formula \[ 1\cdot\mathbb{P}\left[X\ge\alpha\right]+\alpha(1-\mathbb{P}\left[X>\alpha\right])\ge\mathbb{E}\left[X\right]\] \end_inset \begin_inset ERT status open \begin_layout Standard \backslash end{proof} \end_layout \end_inset \end_layout \begin_layout Standard For \begin_inset Formula $e=(u,v)\in E$ \end_inset , let \begin_inset Formula $P_{e}=\mathbb{P}_{x,y,z,\eta}\left[\mbox{permutation test[}\epsilon\mbox{] accepts on }f_{u},f_{v,}\tau_{e}\mbox{ with }A'\right]$ \end_inset . The law of total probability gives \begin_inset Formula \[ \frac{1}{2}+\delta\delta.\] \end_inset Let \begin_inset Formula $\mathcal{E}=\left\{ e\in E\ :\ P_{e}\ge\frac{1}{2}+\frac{\delta}{2}\right\} $ \end_inset be the subset of edges for which the test passes with good probability. The above shows the probabilistic weight of edges in \begin_inset Formula $\mathcal{E},$ \end_inset \begin_inset Formula $w(\mathcal{E})=\sum_{e\in\mathcal{E}}w(e)$ \end_inset is at least \begin_inset Formula $\delta$ \end_inset . For \begin_inset Formula $e=(u,v)\in E$ \end_inset , let \begin_inset Formula $\pi(e)=\mathbb{P}_{\chi_{u}\sim D_{1}(f_{u}),\chi_{v}\sim D_{2}(f_{v})}\left[\chi_{u}(x)=\chi_{v}(\tau_{e}(x))\right]$ \end_inset and recall that the permutation test has satisfaction rate \begin_inset Formula $s(\alpha)=\frac{\alpha^{2}}{2\log_{(1-2\epsilon)}(\nicefrac{\alpha}{2})}$ \end_inset for soundness of \family roman \series medium \shape up \size normal \emph off \bar no \noun off \color none \begin_inset Formula $\frac{1}{2}+\alpha$ \end_inset . Thus for \begin_inset Formula $e\in\mathcal{E},\ \pi(e)\ge s(\frac{\delta}{2})$ \end_inset . \end_layout \begin_layout Standard Finally, we lower bound \begin_inset Formula $\mathbb{E}\left[val_{I}(A)\right]$ \end_inset (the random decoder choice is averaged out) as follows \end_layout \begin_layout Standard \begin_inset Formula \begin{eqnarray*} \mathbb{E}\left[val_{I}(A)\right] & = & \mathbb{E}_{\substack{e=(u,v)\sim E\\ D^{u},D^{v}\in_{R}\left\{ D_{1},D_{2}\right\} } }\left[\mathbf{1}_{\left\{ A\mbox{ satisfies }e\right\} }\right]\\ & \ge & \sum_{e=(u,v)\in\mathcal{E}}w(e)\mathbb{E}\left[\mathbf{1}_{\left\{ D^{u}=D_{1},D^{v}=D_{2}\right\} }\mathbf{1}_{\pi(e)}|e\in\mathcal{E}\right]\\ & \ge & w(\mathcal{E})\min_{e\in\mathcal{E}}\left\{ \mathbb{E}\left[\mathbf{1}_{\left\{ D^{u}=D_{1},D^{v}=D_{2}\right\} }\mathbf{1}_{\pi(e)}\right]\right\} \ge\frac{\delta}{4}s(\frac{\delta}{2})\\ & = & \frac{\delta^{3}}{32\log_{(1-2\epsilon)}(\nicefrac{\delta}{4})}.\end{eqnarray*} \end_inset and this is what we wanted. \end_layout \end_body \end_document