\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{hyperref}
\usepackage{bbm}
\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
\newcommand{\eps}{\epsilon}
\newcommand{\A}{\mathcal{A}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\NP}{\mathcal{NP}}
\DeclareMathOperator*{\Val}{Val}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Heading: In the parentheses below, write the sequential number of the
%% talk, the talk date, the name of the speaker, and the name or names of
%% whoever wrote the scribe (seperated by commas).
\lecture{10}{May 12, 2008}{Guy Kindler}{Ori Brostovski}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Body: from here on it's your territory - write your scribe here.
In this lecture we describe a permutation test over the long code (Section
\ref{sec:long_permutation} and then go on to introduce the subject of hardness
of approximation and specifically the hardness of \emph{E3-LIN-2} based on the
\emph{Unique games conjecture} (Section \ref{sec:hardness}).
\section{In the previous lecture}
In the last lecture we discussed the coordinate permutation test
for odd Hadamard codes. Let us recall it.
\paragraph{Coordinate permutation test}{
\begin{itemize}
\item Codes:
$
C_1 = C_2 = \{\chi_S\}_{\substack{S \subseteq [n] \\ |S|\text{ odd}}}
$.
\item Constraint family:
$R_\tau := \{(\chi_S,\chi_{\tau(S)}) : \chi_S \in C_1\}$,
where $\tau$ is a permutation over $[n]$.
\item Query: Given codewords $f \in C_1$ and $g \in C_2$,
the test checks whether for
$x \in _R \left\{\pm1\right\}^n $,
$y \in_R \left\{\pm1\right\}^n $, and
$u \in_R \left\{\pm1\right\}$ the following equation is satisfied:
\[ f(x)f(y) = ug(u\tau(xy)) \;. \]
\item Completeness: 1.
\item Soundness: $\frac12 + \delta$ (for the coordinate
decoding schemes below).
\end{itemize}
}
\paragraph{Decoding schemes} {
\begin{itemize}
\item $D_1(f)$ - Output $\chi_S$ with probability $\hat{f}(S)^2$ ($\bot$ if
$|S|$ is even).
\item $D_2(g)$ - If $|T|$ is odd, and $\hat{g}(T) \geq \delta$, output
$\chi_T$ with probability $\frac{\hat{g}(T)}{\alpha}$ where
$\alpha := \sum_{|T|\text{ odd}} \hat{g}(T)$.
\end{itemize}
}
\section{Testing permutations over the long code}
\label{sec:long_permutation}
In the coordinate permutation test, the test's constraint family corresponded
to a set of permutations over $[n]$.
That set of permutations can be considered as a subset of the set of
permutations over the odd Hadamard code. It is a strict subset as
permutations like $\chi_S \to \chi_{[n] \setminus S}$ are not in it.
In this section we consider a test that allows checking all possible
permutations over long code words. Note that in the case of the long
code, the set of coordinate permutation corresponds to the set
of permutations over long code words.
Before we elaborate on the long code permutation test,
we define the distribution $\mu_\eps$:
\[
\mu_\eps =
\begin{cases}
+1 & \text{w.p. }1 - \eps \\
-1 & \text{w.p. }\eps \\
\end{cases}\;.
\]
\paragraph{Long code permutation test}{
\begin{itemize}
\item Codes:
$
C_1 = C_2 = \{\chi_i\}_{i \in [n]}
$.
\item Constraint family:
$R_\tau := \{(\chi_i,\chi_{\tau(i)}) : \chi_S \in C_1\}$,
where $\tau$ is a permutation over $[n]$.
\item Query: Given codewords $f \in C_1$ and $g \in C_2$,
the test checks whether for
$x \in_R \left\{\pm1\right\}^n $,
$y \in_R \left\{\pm1\right\}^n $,
$z \in_R\left\{\pm1\right\}$,
and $z \sim \mu_\eps^{(n)}$
the following equation is satisfied:
\[ f(x)f(y) = ug(u\tau(zxy)) \;. \]
\item Completeness: $1 - \eps$.
\item Soundness: $\frac12 + \delta$ (for the coordinate
decoding schemes below).
\end{itemize}
}
\paragraph{Decoding schemes} {
\begin{itemize}
\item $D_1(f)$ - Pick $S$ with probability $\hat{f}(S)^2$. Pick
$i \in_R S$, output $\chi_i$.
\item $D_2(g)$ -
Define $A$ as:
\begin{equation*}
A :=
\{
T :
|T| \leq \log_{1 - 2\eps}(0.5\delta) \land
\hat{g}(T) \geq \delta \land
|T|\text{ odd}
\}
\;.
\end{equation*}
If $A$ empty, return $\bot$. Else,
define $\alpha$ as:
\begin{equation*}
\alpha := \sum_{T \in A} \hat{g}(T)
\;.
\end{equation*}
Pick $T \in A$ with probability $\frac{\hat{g}(T)}{\alpha}$.
Pick $j \in_R T$ and return $\chi_j$.
\end{itemize}
}
\begin{theorem}
\label{thm:long_code}
The long code permutation test has completeness $1 - \eps$, and
soundness $\frac12 + \delta$ with
$\frac{\delta^2}{2\log_{1 - 2\eps}(0.5\delta)}$-satisfaction-rate.
\end{theorem}
\begin{proof}
\paragraph{Completeness}{
To show completeness, we assume that we have some $i \in [n]$
such that $f = \chi_i$ and $g = \chi_{\tau(i)}$.
We will show that for every $x$ and $y$, the equation
\begin{equation}
f(x)f(y) = g(\tau(xy))
\label{equ:completeness}
\end{equation}
is satisfied. Start from the left hand side:
\begin{align*}
\intertext{(Since $f = \chi_i$ and $g = \chi_{\tau_i}$.)}
f(x)f(y) &= \chi_i(x)\chi_i(y)\;, \\
\intertext{(Fourier characters are linear.)}
f(x)f(y) &= \chi_i(xy)\;, \\
\intertext{(Since $|\tau(i) = 1|$, $\chi_i(u,\dots,u) = u$.)}
f(x)f(y) &= u\chi_i(u, \dots, u)\chi_i(xy)\;, \\
\intertext{(If a permutation is applied both to a input
and to its set, the character's result stays the same.)}
f(x)f(y) &= u\chi_i(u, \dots, u)\chi_{\tau(i)}(\tau(xy))\;.
\end{align*}
We observe that $g(\tau(zxy)) \neq g(\tau(xy))$ if and only if
$z_i = -1$. Thus,
\begin{align*}
1 - \eps &= \Pr[g(\tau(zxy)) = g(\tau(xy))]\;, \\
\intertext{(Using equation (\ref{equ:completeness}) and our
result thus far.)}
1 - \eps &= \Pr[g(\tau(zxy)) = f(x)f(y)]\;.
\end{align*}
}
\paragraph{Soundness}{
As in the soundness proofs of other tests, we develop an expression
for $2\Pr[\text{accept}] - 1$:
\begin{align*}
2 \cdot \Pr[\text{accept}] - 1 &= \E_{x,y,u,z}[f(x)f(y)ug(u\tau(zxy))]\;, \\
\intertext{(Using Fourier coefficients.)}
2 \cdot \Pr[\text{accept}] - 1 &=
\sum_{R,S,T \subseteq [n]}\hat{f}(R)\hat{f}(S)\hat{f}(T)
\E_{x,y,u,z}[
\chi_R(x)
\chi_S(y)
u\chi_T(u,\dots,u)\chi_T(\tau(z))\chi_T(\tau(x))\chi_T(\tau(y))
]\;, \\
\intertext{(The expectation of $\chi_R(x)\chi_T(\tau(x))$ is 1 if
$T = \tau(R)$, and 0 otherwise.)}
2 \cdot \Pr[\text{accept}] - 1 &=
\sum_{S \subseteq [n]}\hat{f}(S)^2\hat{g}(\tau(S))
\E_{u,z}[u\chi_{\tau(S)}(u,\dots,u)\chi_{\tau(S)}(\tau(z))]\;, \\
\intertext{(The expectation of $u\chi_{\tau(S)}(u,\dots,u)$ is 1 if
$|S|$ is odd, and 0 otherwise. Expectation of a single
$\mu_\eps$ variable is $(1 - 2\eps)$ which means that the
expectation of $\chi_{\tau(S)}(\tau(z))$ is $(1 - 2\eps)^{|S|}$
due to expectation being multiplicative over independent variables.)}
2 \cdot \Pr[\text{accept}] - 1 &=
\sum_{\substack{S \subseteq [n] \\ |S|\text{ odd}}}
\hat{f}(S)^2\hat{g}(\tau(S))(1 - 2\eps)^{|S|}\;.
\end{align*}
Since we wish to prove soundness, we assume that
$\Pr[\text{accept}] > \frac12 + \delta$, this allows us to say that:
\begin{align}
\sum_{\substack{S \subseteq [n] \\ |S|\text{ odd}}}
\hat{f}(S)^2\hat{g}(\tau(S))(1 - 2\eps)^{|S|}
&\geq
2\delta\;,
\intertext{(Note that $\sum_S{\hat{f}(S)^2} = 1$, and $(1 - 2\eps) \leq 1$.
Hence, the total weight of the sets $S$ for which
$\hat{g}(\tau(S)) < \delta$ is less than $\delta$.
We can use this to bound the sum of all
sets $S$ in the above sum for which $\hat{g}(\tau(S)) \geq \delta$.)}
\sum_{
\substack{
S \subseteq [n] \\
|S|\text{ odd} \\
\hat{g}(\tau(S)) \geq \delta
}
}
\hat{f}(S)^2\hat{g}(\tau(S))(1 - 2\eps)^{|S|}
&\geq
\delta\;, \\
\intertext{(Note that $\sum_S{\hat{f}(S)^2} = 1$, and for
every $S$, $\hat{g}(\tau(S)) \leq 1$.
Hence, the total weight of the sets $S$ for which
$|S| < \log_{1 - 2\eps}(0.5\delta)$ is less than $\delta$.
We can use this to bound the sum of all
sets $S$ in the above sum for which
$|S| < \log_{1 - 2\eps}(0.5\delta)$.)}
\label{equ:sum_bound}
\sum_{
\substack{
S \subseteq [n] \\
|S|\text{ odd} \\
\hat{g}(\tau(S)) \geq \delta \\
|S| < \log_{1 - 2\eps}(0.5\delta)
}
}
\hat{f}(S)^2\hat{g}(\tau(S))
&\geq
0.5\delta\;.
\end{align}
}
Next, we are going to use this bound to finish our proof.
We show that the probability that the decoding schemes
will return codewords which satisfy the constraint is greater or equal than
$\frac{\delta^2}{2\log_{1 - 2\eps}(0.5\delta)}$:
\begin{align*}
\Pr[D_1(f)R_{\tau}D_2(g)] &\geq
\sum_{\substack{
S \subseteq [n] \\
|S|\text{ odd} \\
\hat{g}(\tau(S)) \geq \delta \\
|S| < \log_{1 - 2\eps}(0.5\delta)
}
}
\underbrace{
\frac{1}{\alpha}
\hat{f}(S)^2\hat{g}(\tau(S))
}_{\text{prob. we selected $S$ and $\tau(S)$}}
\cdot
\underbrace{
\frac{1}{|S|}
}_{\text{prob. that $j = \tau(i)$}}\;, \\
\intertext{(Since $|S| < \log_{1 - 2\eps}(0.5\delta)$.)}
\Pr[D_1(f)R_{\tau}D_2(g)] &\geq
\sum_{\substack{
S \subseteq [n] \\
|S|\text{ odd} \\
\hat{g}(\tau(S)) \geq \delta \\
|S| < \log_{1 - 2\eps}(0.5\delta)
}
}
\frac{1}{\alpha}
\hat{f}(S)^2\hat{g}(\tau(S))
\frac{1}{\log_{1 - 2\eps}(0.5\delta)}\;, \\
\intertext{(Using equation (\ref{equ:sum_bound}) and out result thus far.)}
\Pr[D_1(f)R_{\tau}D_2(g)] &\geq
\frac{0.5\delta}{\alpha\log_{1 - 2\eps}(0.5\delta)}\;, \\
\intertext{(As shown in the previous lecture, we have
$\alpha \leq \frac1\delta$.)}
\Pr[D_1(f)R_{\tau}D_2(g)] &\geq
\frac{\delta^2}{2\log_{1 - 2\eps}(0.5\delta)} \;.
\end{align*}
\end{proof}
\section{Hardness of approximation}
\label{sec:hardness}
A variant of theorem (\ref{thm:long_code}) can be used to prove an interesting
hardness result. We will first explain terms related to hardness of approximation,
and then we will describe the result.
\subsection{Introduction}
We will start with the definition of optimization problems and then move on
to approimxation problems.
\paragraph{Optimization problem}{
\begin{itemize}
\item Let $\I$ be a set of instances.
\item For every instance $I \in \I$,
there is a set of assignments $\A(I)$.
\item For every instance $I$ and an assignment $A \in \A(I)$, there is a value
$\Val_I(A)$.
\item Given an instance $I$, we wish to find $A$ such that:
\[
\Val_I(A) = \max_A\{\Val_I(A)\}\;.
\]
\end{itemize}
}
\paragraph{Gap problem} {
\begin{itemize}
\item Let $\I$, $\A$, $I$, $A$ and $\Val$
be defined the same as in an optimization problem.
\item Let $t_1$ and $t_2$ be two scalars such that $t_1 < t_2$.
\item We define a function $g : I \to \{0,1\}$ as following:
\[
g(i) =
\begin{cases}
1 & \exists A : \Val_I(A) \geq t_2 \\
0 & \forall A : \Val_I(A) \leq t_1 \\
\text{undefined behaviour} & \text{otherwise}
\end{cases}\;.
\]
(In some cases $\geq$ may be replaced with $>$ and $\leq$ may be replaced
with $<$).
\end{itemize}
}
The term \emph{hardness of approximation} refers to the hardness of
solving a given gap problem.
\subsection{Approximating E3-LIN-2}
\paragraph{E3-LIN-2}{
\begin{itemize}
\item An instance $I$ is a distribution over linear equations.
\item An assignment $A$ is assignment to the variables of the linear
equation.
\item $\Val_I(A)$ is defined as:
\[
\Val_I(A) := \Pr_{e \sim I}[A \text{ satisfies } e]\;.
\]
\end{itemize}
(For convenience we can think of an instance
as a collection of equations with positive weights whose sum is equal
to one. In this case $\Val_I(A)$ is the sum of weights of satisfied
equations.)
}
\\
We are interested in the following result:
\begin{theorem}
\label{thm:e3_lin_2}
It is hard to approximate E3-LIN-2 for a gap of
$(\frac12 + \delta, 1 - \eps)$.
\end{theorem}
In order to prove this result, we define the \emph{unique games} and
\emph{label cover} problems.
\paragraph{Unique games}{
\begin{itemize}
\item Let $k$ be a parameter.
\item An instance $I$ is a graph with a set of vertices $V$,
a distribution on edges $E$. For each edge $e$ there is some
\textbf{permutation}
$\tau_e \in S_k$.
\item An assignment is defined to be a function $A : V \to [k]$ which
assigns each vertex with a number.
\item $\Val_I(A)$ is defined as:
\[
\Val_I(A) = \Pr_{\substack{e \sim E \\ e = (u,v)}}[A(v) = \tau_e(A(u))]\;.
\]
\end{itemize}
When referring to the unique games problem we use the notation
$UG[k]$. It is conjectured that:
\begin{conjecture}[Unique games conjecture - Khot, 2002]
\label{conj:unique_games_conjecture}
For every $\eps$ and $\delta$, there exists $k$ such that
$(1 - \eps, \delta)$-gap version of UG($k$) is $\NP$-hard.
\end{conjecture}
}
\paragraph{Label cover}{
\begin{itemize}
\item Let $k$ be a parameter.
\item An instance $I$ is a graph with a set of vertices $V$,
a distribution on edges $E$. For each edge $e$ there is some
\textbf{function}
$\pi_e \in \left[k\right]^V$.
\item An assignment is defined to be a function $A : V \to [k]$ which
assigns each vertex with a number.
\item $\Val_I(A)$ is defined as:
\[
\Val_G(A) = \Pr_{\substack{e \sim E \\ e = (u,v)}}[A(v) = \tau_e(A(u))]\;.
\]
\end{itemize}
When referring to the label cover problem we use the notation
$LC[k]$. It has been proved that:
\begin{theorem}
For every $\eps$ and $\delta$, there exists $k$ such that
$(1 - \eps, \delta)$-gap version of LC($k$) is $\NP$-hard.
\end{theorem}
}
Theorem (\ref{thm:e3_lin_2}) can be proven by showing a reduction
from the gap version of label cover to E3-LIN-2, and using a variant of theorem
(\ref{thm:long_code}). In the next class we will show that if
conjecture (\ref{conj:unique_games_conjecture}) is correct then
so is theorem (\ref{thm:e3_lin_2}).
\end{document}