\documentclass[11pt]{article}
\usepackage{amsmath}
\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
%\renewcommand{\baselinestretch}{1.5}
\newcommand{\nc}{\newcommand}
\nc{\be}{\begin{equation}}
\nc{\ee}{\end{equation}}
\nc{\nn}{\nonumber}
\nc{\ba}{\begin{array}}
\nc{\ea}{\end{array}}
\nc{\bea}{\begin{eqnarray}}
\nc{\eea}{\end{eqnarray}}
\nc{\x}{{\bf x}}
\nc{\y}{{\bf y}}
\nc{\z}{{\bf z}}
\nc{\PM}{\{\pm1\}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{-8}{April 28, 2008}{Guy Kindler}{Shira Kritchman}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Body: from here on it's your territory - write your scribe here.
Last lecture we finished proving Kalai's theorem, and started to talk about codes and code testing.
This lecture we continue talking about codes.
More specifically, we define the {\em Hadamard code} and examine the {\em linearity test} for it.
Finally, we define the notion of {\em testing constraints},
and suggest a test for equality on the Hadamard code.
% Notation: $\x=(x_1,\dots,x_n)$
\section{The long code - Revision}
In this section we mostly revise material from the previous lecture.
We define the notions of {\em code family} and {\em code testing},
and we learn about the {\em long code}.
\begin{definition}[Code and code family]
A code is a set of strings over some alphabet $\Sigma$
(in this course $\Sigma=\PM$).
A code family is a set of codes with unbounded size
(where size refers to the number of words in a code).
\end{definition}
We will refer to an element of a code as a {\em code word}. To a general string we will sometimes refer as just {\em word}.
Note that usually we speak of a family of codes without explicitly
indexing each member. That is, we discuss some code $C$ which implicitly
depends on $n$, and should be properly denoted $C^{(n)}$.
\begin{definition}[Code tester]
A $q$-query code tester for a code $C$, with completeness parameter $c$ and soundness parameter $s$,
is a random procedure $T$, which reads $q$ locations from a string $f$
and either accepts or rejects the string, and satisfies:\\
(completeness) $f\in C$ $\Rightarrow$ $\Pr[T^f \mbox{accepts}]>c$\\
(soundness) $\Pr[T^f \mbox{accepts}]>s$ $\Rightarrow$ "There exists a reasonable decoding for $f$".
\end{definition}
Note that 'reasonable decoding' wasn't well defined.
It can mean that the word is very close to some unique code word,
or that it has high correlation with some code word and with not too many code words,
or even more generally, that there is a not too long list of code words which are
somehow related to $f$.
In theoretical computer science, code testers are important as a tool often used in the analysis of hardness of approximation.
The first code that we define is the {\em long code}.
The strings in the set $\PM^{2^n}$ can be understood as truth tables describing all
the Boolean functions on $n$ variables.
The long code is the set of all $f\in\PM^{2^n}$ that describe dictatorships:
\begin{definition}[Long code]
\[
C=\{\chi_i\}_{i\in[n]}\subseteq\PM^{2^n}
\]
\end{definition}
We now describe a test for a code similar to the long code - the set of all dictatorships
and minus dictatorships,
\[
\widetilde{C}=\{\chi_i\}_{i\in[n]}\cup\{-\chi_i\}_{i\in[n]}
\]
Before we describe the test, we should recall some more definitions.
\begin{definition}[The Not All Equal function]
NAE is the boolean function on $\PM^3$ which equals $-1$ on $(x,y,z)$ iff $x=y=z$.
\end{definition}
\begin{definition}[The set $\psi$] $\psi$ is the set of all legal votes,
\[
\psi=\left\{\left.(\x,\y,\z)\in\left(\PM^n\right)^3\right|\forall i\ \mbox{NAE}(x_i,y_i,z_i)=1\right\}
\]
\end{definition}
We are now ready to define the NAE test for the code $\widetilde{C}$.
\begin{definition}[NAE test]
Given $f\in\PM$, pick uniformly at random $\x,\y,\z\in\psi$,
and accept iff $\mbox{NAE}\left(f(\x),f(\y),f(\z)\right)=1$.
\end{definition}
Denote the test by $T_{NAE}$. Clearly, the NAE test has completeness $c=1$:\\
\noindent{\bf(Completeness)} $f\in \widetilde{C}$ $\Rightarrow$ $\Pr[T_{NAE}^f\mbox{ accepts}]=1$.\\
\noindent From Kalai's theorem (which we phrased in lecture \#7 and proved in lectures \#7 and \#8),
we know that if $\Pr[T_{NAE}^f\mbox{ accepts}]>1-\varepsilon$ then $f$ is $k\varepsilon$-close to a code word.
From this it follows easily that:\\
\noindent{\bf(Soundness)}
%$\Pr[T^f\mbox{ accepts}]>1-\delta$ $\Rightarrow$ $f$ is $k\delta$-close to a dictatorship or minus
%a dictatorship.
$\forall \delta$ there exists $s(\delta)$ such that if
$\Pr[T_{NAE}^f\mbox{ accepts}]>s(\delta)$ then $\exists i\in[n]$ for which
$\left|\hat{f}(i)\right|>1-\delta$.\\
\noindent Note that if $\hat{f}(i)>1-\delta$, then $f$ is close to the dictatorship
function $\chi_i$:
\[ ||f-\chi_i||_2^2 = \sum_{S\neq\{i\}} \hat{f}(S)^2+(\hat{f}(i)-1)^2
= 1-\hat{f}(i)^2 + (\hat{f}(i)-1)^2
= 2-2\hat{f}(i)
\le 2\delta
\]
and thus the Hamming distance between $f$ and $\chi_i$ is small:
\[
\Pr_{\x}[f(\x)\neq\chi_i(\x)] = \frac{||f-x_i||_2^2}4 \le \frac{\delta}2
\]
(similarly, if $-\hat{f}(i)>1-\delta$, then $f$ is close to $-\chi_i$).
\section{The Hadamard code}
In this section we define the {\em Hadamard code} and examine the {\em linearity test} for it.
The Hadamard code is the set of all Boolean functions on $n$ variables which are characters:
\begin{definition}[Hadamard code]
\[C=\{\chi_s\}_{s\subseteq n}\subseteq\PM^{2^n}\]
\end{definition}
We suggest testing it using the 3-query linearity test:
\begin{definition}[Linearity test]
Given $f:\PM^n\to\PM$, pick uniformly at random $\x,\y\in\PM^n$,
and accept iff $f(\x)f(\y)=f(\x\y)$.
\end{definition}
We now discuss the properties of the linearity test. We denote it by $T_{lin}$.
Clearly, the linearity test has completeness $c=1$:\\
\noindent{\bf(Completeness)} $f$ is a character $\Rightarrow$ $\Pr[T_{lin}^f\mbox{ accepts}]=1$.\\
\noindent As usual, we have to work harder to show soundness.\\
\noindent {\bf(Soundness)}
Here we wish to say something about $f$ given that the probability of accepting $f$ is high.
We consider two cases: $\Pr [T_{lin}^f\mbox{ accepts}]>1-\delta$, where $\delta$ is small,
and $\Pr [T_{lin}^f\mbox{ accepts}]\ge \frac12 + \delta$.
We present two soundness lemmas dealing with the two cases.
\begin{lemma}[Soundness lemma I for linearity test]
If \ $\Pr[T_{lin}^f\mbox{ accepts}]>1-\delta$ then $\exists S\subseteq[n]$ such that $\hat{f}_S>1-\delta$.
\end{lemma}
\begin{proof}
We wish to represent the acceptance probability as a function of the Fourier coefficients.
Note that the test accepts iff $f(\x)f(\y)f(\x\y)=1$. Thus,
\[
\E [f(\x)f(\y)f(\x\y)] = \Pr [T_{lin}^f\mbox{ accepts}]-\Pr [T_{lin}^f\mbox{ rejects}]
= 2\Pr [T_{lin}^f\mbox{ accepts}]-1
\]
Repeating what we have seen in the second exercise,
\begin{eqnarray*}
\E_{\x,\y} [f(\x)f(\y)f(\x\y)]
&=& \E_{\x,\y} \left\{\left[\sum_S\hat{f}(S)\chi_S(\x)\right]\left[\sum_T\hat{f}(T)\chi_T(\y)\right]\left[\sum_R\hat{f}(R)\chi_R(\x\y)\right]\right\}\\
&=& \sum_{S,T,R} \hat{f}(S)\hat{f}(T)\hat{f}(R)\E[\chi_S(\x)\chi_T(\y)\chi_R(\x\y)]\\
&=& \sum_{S} \hat{f}(S)^3
\end{eqnarray*}
Thus, if
$ \Pr[T_{lin}^f\mbox{ accepts}]>1-\delta $ then $\sum_{S} \hat{f}(S)^3=2Pr[T_{lin}^f\mbox{ accepts}]-1>1-2\delta$.
Since $\sum_{S} \hat{f}(S)^3 \le \max_S\{\hat{f}(S)\}\cdot\sum_{S} \hat{f}(S)^2=\max_S\{\hat{f}(S)\}$,
we get that if the acceptance probability is higher than $1-\delta$, then there exists $S\subseteq[n]$
such that $\hat{f}(S)>1-2\delta$.
Note that if $\delta$ is small (smaller than $\left(1-1/\sqrt{2}\right)/2=0.146$), then $S$ is unique.
In this case $\chi_S$ provides a unique decoding for $f$.
\end{proof}
\begin{lemma}[Soundness lemma II for linearity test]
If \ $\Pr[T_{lin}^f\mbox{ accepts}]> \frac12+\delta$ then $\exists S\subseteq[n]$ such that $\hat{f}(s)>2\delta$.
\end{lemma}
\begin{proof}
This follows immediately from the previous lemma:
$\Pr[T_{lin}^f\mbox{ accepts}]\ge \frac12+\delta=1-\left(\frac12-\delta\right)$
and hence $\max_S\{\hat{f}(S)\}\ge 1-2\left(\frac12-\delta\right)=2\delta$.
\end{proof}
%\begin{remark}
It seems that the second soundness lemma doesn't say much -
when $\delta$ is small, there could be many Fourier coefficients greater than $2\delta$.
But since $\sum_S\hat{f}(S)^2=1$, there could be no more than $\frac1{4\delta^2}$ such coefficients.
To each $\chi_S$ such that $\hat{f}(S)\ge 2\delta$ we call a {\em reasonable decoding}.
The list of reasonable decodings provides a {\em list decoding} -
a non-empty yet not too long list of reasonable decodings.\\
%\end{remark}
\begin{remark}
What if we know that $\Pr[T_{lin}^f\mbox{ accepts}]\le\frac12-\delta$?
Then $\Pr[T_{lin}^{-f}\mbox{ accepts}]=1-\Pr[T_{lin}^f\mbox{ accepts}]\ge\frac12+\delta$,
hence $\exists S\subseteq[n]$ such that $-\hat{f}(S)>2\delta$.
\end{remark}
%\begin{remark}
In exercise \#4 we will see an interesting code which has a 2-query test.
%\end{remark}
\section{Testing constraints}
In this section we define the notions of {\em constraint} and {\em constraint tester},
and suggest a test for equality on the Hadamard code.
\begin{definition}[Constraint]
A constraint between two codes $C_1$ and $C_2$ is a relation $R$ between them as sets.
That is, $f\in C_1$ and $g\in C_2$ satisfy the constraint if $fRg$.
\end{definition}
A simple example for a constraint is $C_1=C_2=C$ the Hadamard code,
and $f,g\in C$ satisfy the constraint if $f=g$.
Intuitively, a constraint tester is a procedure that receives as input two strings $f$ and $g$,
and checks whether (1) $f\in C_1$, (2) $g\in C_2$ and (3) $fRg$.
Therefore, a constraint tester is similar to a Kind(l)er egg.
To define things more rigorously, we need a few more definitions.
\begin{definition}[Constraint collection]
A constraint collection on two codes $C_1$ and $C_2$ is a set of relations over $C_1$ and $C_2$,
\[
\mathcal{R}=\{R_\lambda\}_{\lambda\in\Lambda}
\]
\end{definition}
(again, we have an implicit dependence on $n$. That is, $C_i$ is $C_i^{(n)}$,
and $\mathcal{R}$ is $\mathcal{R}^{(n)}$).
\begin{definition}[Decoding scheme]
A decoding scheme for a code $C$ is a map $D$ such that for any string $f$,
$D(f)$ is a distribution over $C\cup\{\bot\}$.
\end{definition}
We are now ready to define the notion of a constraint tester.
\begin{definition}[Constraint tester]
A $q$-query constraint tester for codes $C_1$ and $C_2$
and a constraint family $\mathcal{R}=\{R_\lambda\}_{\lambda\in\Lambda}$,
with completeness parameter $c$ and soundness parameter $s$,
is a random procedure $T$, which reads $\lambda\in\Lambda$ and $q$ locations from strings $f$ and $g$,
and either accepts or rejects, and satisfies:\\
(completeness) $f\in C_1$, $g\in C_2$ and $fR_\lambda g$ $\Rightarrow$ $\Pr[T^{f,g}(\lambda) \mbox{accepts}]>c$\\
(soundness) $T$ has soundness $s=s(\delta)$ for $\delta$-satisfaction rate,
if there exist decoding schemes $D_1,D_2$ for $C_1,C_2$ such that
\[
\Pr_{\mbox{randomness of }T}[T^{f,g}(\lambda)\mbox{ accepts}]\ge s
\Rightarrow
\Pr_{f'\sim D_1(f),g'\sim D_2(g)}[f'Rg']\ge\delta.
\]
\end{definition}
We now construct a 3-query test for identity between Hadamard words.
That is, given $f$ and $g$, we want to test if they are characters, and if $f=g$,
reading only three bits.\\
\begin{definition}[Testing linearity between Hadamard words]
Given $f$ and $g$ pick uniformly at random $\x,\y\in\PM^n$, and accept iff $f(\x)f(\y)=g(\x\y)$.
\end{definition}
We now discuss the properties of this test. We denote it by $T_{eq}$.
Clearly, the test has completeness parameter $c=1$:\\
\noindent {\bf (Completeness)} $f,g\in C$ and $f=g$ $\Rightarrow$ $\Pr[T_{eq}^{f,g}\mbox{ accepts}]=1$.\\
\noindent As for soundness, we show the following:\\
\noindent {\bf (Soundness)} If $\Pr[T_{eq}^{f,g}\mbox{ accepts}]>1-\delta$
then there exist (reasonable) decoding schemes $D_1$ and $D_2$ such that
(when $\delta$ is small enough) $\Pr_{f'\sim D_1,g'\sim D_2}[f'=g']$ is 'large'.\\
\begin{proof}
Suppose $\Pr[T_{eq}^{f,g}\mbox{ accepts}]>1-\delta$,
then
\[
\sum_S\hat{f}(S)^2\hat{g}(S)=\E[f(\x)f(\y)g(\x\y)]=2\Pr[T_{eq}^{f,g}\mbox{ accepts}]-1>1-2\delta
\]
This is a weighted mean of the coefficients of $g$, and hence there exists some $S\subseteq[n]$
such that $\hat{g}(S)>1-2\delta$. If $\delta$ is small enough, then $S$ is unique and we denote
it $S^*$.
Let $D_2$ be the decoding scheme which returns $\chi_{S^*}$.
As for $f$, we suggest two different decoding schemes:\\
\noindent (1) Note that by the Cauchy-Schwarz inequality,
$ \sum_S\left|\hat{f}(s)\hat{g}(S)\right|\le||f^2||\cdot||g^2||=1 $,
and therefore
\[
\max_S\{\hat{f}(S)\}
\ge \max_S\{\hat{f}(S)\} \sum_S \left|\hat{f}(S)\hat{g}(S)\right|
\ge \sum_S\hat{f}(S)^2\hat{g}(S) > 1-2\delta
\]
So again, if $\delta$ is small enough, $\exists! S^{**}$ such that $\hat{f}(S^{**})>1-2\delta$.
Hence, let $D_1$ be the decoding scheme which returns $\chi_{S^{**}}$.
If $\delta$ is small enough then we must have $S^{*}=S^{**}$
(because otherwise $\sum_S\hat{f}(S)^2\hat{g}(S)$ is too small).
Hence we get that $\Pr_{f'\sim D_1(f),g'\sim D_2(g)}[f'Rg']=1$.
\\
\noindent (2) $\sum_S\hat{f}(S)^2=1$, hence it defines a probability distribution over $2^{[n]}$.
Let $D_1$ be the decoding scheme returning $\chi_S$ with probability $\hat{f}(S)^2$.
Then
\[
\Pr_{f'\sim D_1,g'\sim D_2}[f'=g'] = \Pr[f'=\chi_{S^*}]=\hat{f}(S^*)^2
\]
This is large since $\hat{g}(S^*)>1-2\delta$, and therefore
$\max_{S\neq S^*}\{\hat{g}(S)\}<\sqrt{1-(1-2\delta)^2}=2\sqrt{\delta-\delta^2}$, and therefore
\[
\hat{f}(S^*)^2 \hat{g}(S^*)
> 1-2\delta - \sum_{S\neq S^*} \hat{f}(S)^2 \hat{g}(S)
\ge 1-2\delta - \max_{S\neq S^*}\{\hat{g}(S)\}
> 1-2\delta - 2\sqrt{\delta-\delta^2}.
\]
This gives
\[
\Pr_{f'\sim D_1,g'\sim D_2}[f'=g']
= \hat{f}(S^*)^2> \frac{1-\delta - 2\sqrt{\delta-\delta^2}}{\hat{g}(S^*)}
\ge 1-2\delta - 2\sqrt{\delta-\delta^2}.
\]
\end{proof}
\end{document}