\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\spacing{1.00}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS E6998-9:\hspace{0.12cm}Algorithmic
          Techniques for Massive Data} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribe:\hspace{0.08cm}#4}{#1}}

\newtheorem{theorem}{Theorem}
\newtheorem{goal}[theorem]{Goal}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\begin{document}

\lecture{Lecture 21: Linearity Testing}{Nov 19, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Nikita Nataraj}}
\section{Linear Testing}
Given a function $f$, in linear testing we determine whether it
is a linear function: i.e., $f(x+y) = f(x) + f(y)$ for all
$x,y$. Assume that we have the following function:
\begin{center}
$f: \{0,1\}^{n} \rightarrow R$

$x \xrightarrow{f} f(x)$
\end{center}

We can think of $f(x)$ is being describe as a complete truth table, as
we can sample $f(x)$. To make this proof easier we map the boolean
onto +1 and -1.
\begin{center}
$0 \rightarrow +1$

$1 \rightarrow -1$
\end{center}
From now on, we will consider the function
\begin{center}
$f: \{+1,-1\}^{n} \rightarrow \{+1,-1\}$
\end{center}
\begin{definition}
$f$ is linear if $\forall x,y \in \{+1,-1\}^n$
\begin{center}
$f(x\oplus y)=f(x)\cdot f(y)$

$x\oplus y=(x_{1}y_{1},x_{2}y_{2}...x_{n}y_{n})$
\end{center}
\end{definition}
The modulus addition is equivalent to a dot product. This is also
termed \textbf{Homomorphism} (for general groups).
\begin{problem}
The problem at hand is to distinguish between:
\end{problem}
\begin{itemize}
\item $f$ is linear
\item $f$ is $\epsilon$ far from linear, which means the following:
\begin{center}
$\forall g$ that is linear

$f(x)\neq g(x)$ on $\geq \epsilon 2^{n}$ inputs $x$.
\end{center}
\end{itemize}
\begin{goal} How many queries do we need to solve the above goal with 90\% success probability.
\end{goal}
\textbf{Motivation} [Blum-Luby-Rubinfield '90]
\begin{itemize}
\item self testing
\item self correction
\item 
PCP Theorem (probabilistically checkable proof):
informally it is as follows. For a given formula $\varphi$, we can
transform it into $\varphi$', where $\varphi$' is satisfiable if and only if $\varphi$ is satisfiable. 
For any proof (satisfyable assignment) of $\varphi'$, we can check
whether it is indeed satisfyable in $O(1)$ places.
\item PCP is often used to prove non-approximability: even
  approximating max clique upto a factor of $\sqrt{n}$ is a NP hard problem.
\end{itemize}
\textbf{Algorithm} for testing linearity is fairly basic.
\begin{itemize}
\item pick $x,y$ randomly
\item check the given property $f(x\oplus y)=f(x)\oplus f(y)$. Lets
  call this $T_{xy}$ (a test for x,y)
\item repeat the $T_{x,y}$ test for $O(1/\epsilon)$ times and fail if
  at least one of them fails.
\end{itemize}
\textbf{Analysis of Algorithm}
\begin{itemize}
\item If the function $f$ is linear, then $T_{xy}$ will pass.
\item If the function $f$ is $\epsilon$ far from linear, we need to find the Pr[$T_{xy}$ fails]:
\begin{center}
Pr[$T_{xy}$ fails] = 1 - Pr[$T_{xy}$ passes]

$\geq \epsilon$ 
\end{center}
\end{itemize}
\textbf{Example} [Coppersmith]
\begin{center}
$f$: $Z_{3^k} \rightarrow Z_{3^{k-1}}$

$f(3h+d)=h$ (where $d \in \{-1,0,+1\}$)
\end{center}
We have that $Pr[T_{xy}\ fails] = 2/9$, but $f$ is 2/3 far from linear.
\section{Fourier Analysis}
We will show how Fourier analysis can be used to determine linearity. It is given that
\begin{center}
$f:\{+1,-1\}^{n}\rightarrow R$, can be seen as a vector    $F \in R^{d}$ where $d=2^{n}$

${\mathcal F}=\{$set of all $f\}$
\end{center}
We define $f(x)$ as a summation of the multiplication of a basis vector and a scalar.
\begin{center}
Define: $f_{i}(x)$ = 1 for $i=x$, and 0 for $i\neq x$

Then, $f=\sum f(i)f_{i}$, i.e., $f(x)=\sum f(i)f_{i}(x)$ for all $x$.
\end{center}
This is equivalent to: a natural basis $e_{i}$ (where $i\in \{+1,-1\}^n$), $F=\sum x_{i}e_{i}$ where $x_{i}$ is a scalar and $e_{i}$ is a basis vactor.

We now introduce the Fourier basis. Fix $S \subseteq [n]$, then we define $\chi_{S}(x)$ as:
\begin{center}
$\chi_{s}(x)=\Pi x_{i}$ where $i \in S$

Define $\chi_{\emptyset}(x)=1$.
\end{center}
\textbf{Fact} $\chi_{S}$ for $S \subseteq [n]$ are a basis for $\mathcal
F$.
\begin{itemize}
\item There are $2^{n}$ of them.
\item $||\chi_{S}||^{2}$ = $\sum_x(\chi_{S}(x))^{2} = 2^{n}$.
\item Dot product: $\sum_x\chi_{S}(x)\chi_{T}(x) = \sum\prod_{i\in S}x_{i}\prod_{i\in T}x_{i} = \sum\prod_{i\in S\Delta T}x_{i} $

$= \sum_x\chi_{S\Delta T}(x) = \frac{1}{2^{n}}E[\prod_{i\in S\Delta
    T}x_{i}] = \frac{1}{2^{n}}\prod_{i\in S\Delta T}E[x_{i}] = 0$ if
  $S\neq T$.
\end{itemize}
Hence these basis functions $\chi_S$ form a basis for $\mathcal F$.

\begin{definition}
$<f,g>\triangleq\frac{1}{2^{n}}\sum_{x}f(x)g(x)$ which is essentially a dot product.
\end{definition}
In this definition, we get that $<\chi_{S},\chi_{S}>=1$ (norm of a
basis vector is one).
\begin{corollary}
 $\forall f$
\begin{center}
$f(x)=\sum_{S\subseteq [n]}\hat{f}(S)\chi_{S}(x)$
\end{center}
where $\hat{f}(S)$ is given by $\hat{f}_{S}=<f,\chi_{S}>$.

\end{corollary}
\textbf{Examples of Fourier transform}
\begin{center}
 \begin{tabular}{||c | c||} 
 \hline
 $f(x)$ & Fourier \\ [0.5ex] 
 \hline\hline
 1 & 1 \\ 
 \hline
 $X_{i}$ & $X_{i}$ \\
 \hline
 AND($X_{2}$,$X_{1}$) = -1 if $X_{2}$=$X_{1}$=-1, 1 otherwise & $\frac{1}{2}+\frac{1}{2}X_{1}+\frac{1}{2}X_{2}-\frac{1}{2}X_{1}X_{2}$ \\
 \hline
  $f=\chi_{S}$ & $\hat{f}_{S}=1$ and $\hat{f}_{T}=0$ for $T\neq S$   \\[1ex]
 \hline
\end{tabular}
\end{center}
\begin{theorem}[Plancherel's] shows that
\begin{center}
$<f,g>=\sum_{S\subseteq [n]}\hat{f}_{S}\hat{g}_{S}$
\end{center}
\end{theorem}

\textbf{Proof}
$<f,g>=E_{x}[f(x)g(x)]$

$=E[\sum_{S\subseteq [n]}\hat{f}(S)\chi_{S}(x)\sum_{T\subseteq [n]}\hat{g}(T)\chi_{T}(x)]$

$=\sum_{S,T}\hat{f}_{S}\hat{g}_{T}E[\chi_{S}(x)\chi_{T}(x)]$

The only terms that survive are those in which $S=T$ which makes the
expectation value equal 1. Therefore,

$<f,g>=\sum_{S}\hat{f}_{S}\hat{g}_{S}$.

\begin{theorem}[Parseval's]
$<f,f>=\sum_{S\subseteq [n]}\hat{f}_{S}^{2}$
\end{theorem}

If $f_{i}\{+,-1\}^{n}\rightarrow\{+1,-1\}$, then, $<f,f>=1$ or can be
written as $\sum\hat{f}_{S}^{2}=1$ by Plancherel's.
\section{Proof of Linearity with Fourier Analysis}



\begin{lemma} $\chi_{S}$ are exactly all the linear functions $f:\{+1,-1\}^{n} \rightarrow \{+1,-1\}$.
\end{lemma}
\begin{proof}
\begin{itemize}
\item First we prove $\chi_{S}$ is linear

$\forall x,y$

$\chi_{S}(x\oplus y)=\prod_{i\in S}x_{i}y_{i} = \prod_{i\in S}x_{i}\prod_{i\in S}y_{i} = \chi_{S}(x)\chi_{S}(y)$

\item if $f$ is linear then it is some $\chi_{S}$ (in problem set 5).
\end{itemize}
\end{proof}

$\hat{f}_{S}$ relates distance to basis function $\chi_{S}$. In
particular, if $f$ is
$\epsilon$-far from linearity, then we have:

$\hat{f}_{S}=<f,\chi_{S}> = E_{x}f(x)\chi_{S}(x)$

$=\Pr[f(x)=\chi_{S}(x)]-\Pr[f(x)\neq\chi_{S}(x)]$

$=1-dist(f,\chi_{S})-dist(f,\chi_{S}) = 1 - 2dist(f,\chi_{S})$

$\leq 1-2\epsilon$

Hence, none of the $\hat{f}_{S}$ coefficients are close to 1, and this will
cause the test to fail.

\begin{theorem}[Main theorem]
Define: $T_{xy} = 1$ if $f(x)\cdot f(y) = f(x \oplus y)$ and it is 0 otherwise.

If f is $\epsilon$ far then we prove that the $\Pr[T_{xy}=1]\le 1- \epsilon$.
\end{theorem}
\textbf{Proof} Let $\delta = \Pr[T_{xy}=0]$.
\begin{lemma}
$\Pr[T_{xy}=1]=1-\delta=\frac{1}{2}+\frac{1}{2}\sum_{S}\hat{f}_{S}^{3}$.
\end{lemma}

We prove that this lemma proves the above theorem.

$\delta$ = $1-(\frac{1}{2}+\frac{1}{2}\sum_{S}\hat{f}_{S}^{3})=\frac{1}{2}-\frac{1}{2}\sum_{S}\hat{f}_{S}^{3}$

Since $\hat{f}_{S}$ is upper bounded by $1-2\epsilon$

$\geq\frac{1}{2}-\frac{1}{2}(1-2\epsilon)\sum_{S}\hat{f}_{S}^{2}$

As proved above, we have $\sum_{S}\hat{f}_{S}^{2}=1$. Therefore,

$\geq\frac{1}{2}-\frac{1}{2}+\epsilon=\epsilon$.

Hence proven. We will prove the above lemma in the next lecture.
\end{document}