\documentclass[10pt]{article}
\usepackage{amsmath, amssymb}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{2}{February 13, 2006}{Ronitt Rubinfeld}{Iolanthe Chronis}

%%%% body goes in here %%%%
				   
Lecture Outline: 
\begin{itemize}
\item  Linearity Testing (Introduction) 
\item  Observation about distributions  
\item  Self-correcting programs 
\begin{itemize}
     \item union bound
     \item Chernoff bound
     \item indicator variables
     \item linearity of expectations
\end{itemize}
\item   Proposed test for linearity
\begin{itemize}
     \item sampling claim - review ``gap'' bound
     \item Coppersmith's example
     \item proof of correctness and review of Markov's inequality (we didn't get to this)
\end{itemize}
\end{itemize}

\section{Linearity Testing -- An Introduction}
Let $G$ be a finite abelian group (ie $\Z_p$).  The theorems that we will prove today work for arbitrary finite groups, but our proofs may not.  
\begin{definition}
A function $f: G \rightarrow G$ is linear (homomorphic) if $\forall x,y \in G$, $f(x)+f(y)=f(x+y)$. 
\end{definition}
Examples of linear functions:

\begin{equation}
f(x)=x
\end{equation}
\begin{equation}
f(x)=3x \textrm{ (mod } l)
\end{equation}
Problem:  Can we tell if an arbitrary function $f$ is linear?  The function $f$ is a black box.  We know nothing about its internal structure; all we can do is query it, meaning we can pass in a value of $x$ and get out a value of $f(x)$.  To find out whether $f$ is linear, we need to query every single value in the domain.  If we do not, the following situation can occur:
\begin{equation}
f(x)=x \textrm{ for }x\neq 3, f(3)=2 
\end{equation}
There's no way to know that $f$ isn't linear unless we query $x=3$ itself.\\

\begin{definition}
A function f is called $\epsilon$-linear if there exists a function $g$ s.t. $g$ is linear and the following equation is true:
\begin{equation}
\frac{\textrm{number of $x$'s }s.t. f(x)=g(x)}{\textrm{number of x's}} = \textrm{Pr}_{x \in G} [f(x)=g(x)]\geq 1-\epsilon
\end{equation}
\end{definition}

In the following, we will discuss how to test that $f$ is $\epsilon$-linear without testing all of the values in the domain.

\section{An Observation About Distributions}
If G is a finite group,
\begin{equation}
\forall a,y, \in G  \textrm{ Pr}_x[y=a+x]=1/{|G|}
\end{equation}
\begin{remark}
If we pick $x\epsilon_R G$ then $a+x \epsilon_R G$.  We use this notation to denote that $a+x$ is distributed uniformly in $G$.
\end{remark}\\
Since $G$ is a group, inverses exist, so $y-a$ is a member of $G$, and only $x=y-a$ satisfies the equation $y=a+x$.\\

\begin{remark}
If $G$ is $Z_2^n$, addition is defined in the following manner:
\begin{equation}
(a_1,...,a_n)+(b_1,...,b_n)=(a_1+b_1,...,a_n+b_n)
\end{equation}
\end{remark}

\section{Self-Correcting Programs}
Say that $f$ is the function described above that is linear except at $x=3$.  We can define a linear function $g$ such that $g(i)=f(i)$ for all $i \neq 3$, and $g(3)=f(1)+f(2)$, or $g(3)=f(4)-f(1)$, or in general, $g(3)=g(x)+g(3-x)$ for any $x\in G$ except for $x=0$ or $x=3$.  This allows us to correct 1 error, but we can extend this to correct more as follows.\\
\\
For a general $\epsilon$-linear $f$ where $\epsilon \leq 1/8$, let $g$ be the closest linear function to $f$ (the following shows that when $\epsilon \leq 1/8$, $g$ is unique).  If we pick $y$ randomly from $G$, what is the probability that $g(x)=f(y)+f(x-y)$?


\begin{align}
&  \textrm{Let cond (1) be }f(y)\neq g(y) \textrm{   (and }Pr_y[\textrm{cond (1)}]\leq \epsilon) \\
&  \textrm{Let cond (2) be }f(x-y)\neq g(x-y) \textrm{   (and } Pr_{x,y}[\textrm{cond (2)}]\leq \epsilon)\\
&  \textrm{Pr}_{x,y}[\textrm{cond (1) or cond(2)}]\leq 2\epsilon \textrm{ by the union bound} \\
&  \textrm{We have that }\forall x,y, g(x)=g(y)+g(x-y) \\
&  \textrm{Therefore Pr}_{x,y}[g(x)=f(y)+f(x-y)]\geq 1-2\epsilon \geq 3/4
\end{align}


Using this bound, we can use the following algorithm to find the appropriate values for $g(x) $ using other parts of $f$.\\

\begin{tabbing}
Self-Corrector(x):\\
For \=$i=1...r$\\
\>   Pick $y$ randomly from $G$\\
\>   $answer_i\leftarrow f(y)+f(x-y)$\\
$output=$ most common $answer_i$\\
\end{tabbing}

\begin{theorem}
$Pr[output=g(x)$]$\geq 1-\beta$ (for proper choice of constants.)
\end{theorem}

\begin{proof}  Let's define a random indicator variable $\sigma_i = 1$ if $answer_i=g(x)$, and 0 otherwise.  Thus, the expected value of $\sigma_1$ is just the probability that $answer_i=g(x)$.  In other words, 


\begin{align}
& \textrm{E}[\sigma_i]=\textrm{Pr}[\sigma_i=1]\geq3/4\\
& \textrm{If } \Sigma \sigma_i > r/2 \textrm{ then }output=g(x)\\
& \textrm{E}[\Sigma \sigma_i]=\Sigma E[\sigma_i]=3r/4\\
& \textrm{Pr}[\sigma_i \leq r/2] \leq \textrm{Pr}[|\frac{\Sigma \sigma_i}{r}-\frac{\textrm{E}[\Sigma \sigma_i]}{r}|\leq 1/4]
\end{align}

Now we can use a Chernoff bound.  The mathematical statement of a Chernoff boundfor an indicator variable $\sigma_i$ with Pr[$\sigma_i$]$=p$ is\footnote{See notes for better bounds}:

\begin{equation}
\textrm{Pr}[|\frac{\Sigma \sigma_i}{r}-p|\leq \epsilon p]\leq 2e^{-rp\epsilon^2/3}
\end{equation}
Here, $p=3/4$ and $\epsilon p=1/4$, so $\epsilon=1/3$.  Also, choose $r=c \ln (1/\beta)$.  Plug these values into the Chernoff bound formula:

%\begin{equation}

\begin{align}
& 2e^{-r(3/4)(1/9)/3}\\
= \ & 2e^{-r/36}\\
= \ & 2e^{-c/36 \ln (1/\beta)}\\
< \ & \beta \textrm{ for }c < 36.
\end{align}
\end{proof}

%\end{equation}

\section{A Proposed Test of Linearity}
\begin{tabbing}
Here's a proposed test of linearity:\\
Repe\=at r times\\
\>Pick $x,y \in_R G$\\
\>If $f(x)+f(y)\neq f(x+y)$ output ``fail''\\
Output ``pass''
\end{tabbing}


However, this example due to Coppersmith shows that a function can pass for most choices of $x$ and $y$, but still be far from linear.
%\begin{equation}
\[
f(x)=\begin{cases}1 &\hbox{if $x \equiv 1$ (mod 3)}\\ 0 &\hbox{if $ x \equiv 0$ (mod 3)}\\ -1 &\hbox{if $x \equiv 2$ (mod 3)}
     \end{cases}
\]
%\end{equation}

This function fails for $x \equiv y \equiv 1$ (mod 3) and for $x \equiv y \equiv 2$ (mod 3), but it passes for all other cases.  Thus, it fails for only $2/9$ of the possible choices of $x$ and $y$.  However, the closest linear function to $f$ is the 0 function.  The function $f$ is only 0 in $1/3$ of all cases, so $f$ is $2/3$-linear.  It turns out that $2/9$ is a type of threshold in that functions that pass the linearity test {\em more} than $7/9$ of the time also are $\epsilon$-linear for a fairly small $\epsilon$.  We will begin a proof of this idea at the end of this lecture, and finish the proof in the next lecture.

\subsection{Sampling Theorem}
\begin{theorem} There exists an algorithm s.t. 
\begin{tabbing}
if f \=is linear, i.e. $f(x)+f(y)=f(x+y) \forall x,y$\\
\>output ``Pass''\\
if f is s.t. Pr[$f(x)+f(y) \neq f(x+y)$]$> \delta$\\
\>output ``Fail'' with probability $\geq 1-\beta$\\
The runtime of this algorithm will be O($\frac{1}{\delta}\ln\frac1\beta$)\\
\end{tabbing}
\end{theorem}

Bounds of this type will be refered to in this course as ``gap'' sampling bounds.  This is not a term sanctioned by the greater community, since we will do many sampling tasks of this type later.  ``Gap'' bound proofs always work in a manner similar to the following, which is the proof of the above theorem.\\
\\
\begin{remark}
$(1-x)^{1/x} \sim e^{-1}$
\end{remark}
 
\begin{proof}
Pr[output ``Pass''] $\leq (1-\delta)^r = {1-\delta}^{\frac{c}{\delta}\ln\frac{1}{\beta}} = e^{-c \ln{1/\beta}}=\beta^{-c} < \beta$
\end{proof}

Now we have shown that we can distinguish $f$'s that are linear from those for which the test $f(x)+f(y)=f(x+y)$ often fails (with probability higher than $\delta$.  However, Coppersmith's example shows us that some $f$'s that often pass that test (in the next lecture called ``group law failure'') are also very far from linear.  However, for low enough $\delta$, we will prove that $f$ is close to linear.

\begin{theorem}
Assuming Pr[$f(x)+f(y)\neq f(x+y)] < \delta$ and that $G$ is a finite group, $\delta < 2/9$ implies that $f$ is $\delta/2$-linear.
\end{theorem}
Actually, we will prove this weaker version:
\begin{theorem}
Assuming Pr[$f(x)+f(y)\neq f(x+y)] < \delta$ and that $G$ is a finite abelian group, $\delta < 1/16$ implies that $f$ is $2\delta$-linear.
\end{theorem}

\begin{definition}
If $g(x)=plurality_{y\in G}[f(x+y)-f(y)]$.  We'll refer to $f(x+y)-f(y)$ as $y$'s ``vote''.
\end{definition}
\begin{definition}
 $x$ is called $\rho$-good if Pr$_y[g(x)=f(x+y)-f(y)] > 1- \rho$.  Otherwise, $x$ is called $\rho$-bad.
\end{definition}
 Note that if $x$ is $\rho$-good for $\rho < 1/2$ then there is a ``majority agreement.''
\begin{claim}
If $\rho \leq 1/2$, Pr$_x[x$ is $\rho$-good and $g(x)=f(x)] > 1-\delta/\rho$
\end{claim}
We will prove the claim, and the rest of the theorem, in the next lecture.
\end{document}