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

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

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

\lecture{9}{May 20, 2009}{Ronitt Rubinfeld}{Mateus de Oliveira Oliveira and Daniel Shahaf}

%%%% body goes in here %%%%

%Blah Blah Blah

\def\zo{\{\,0,1\,\}}
\def\pmo{\{\,\pm1\,\}}
\def\GF{{\rm GF}}
% for source readability
\let\lxor\oplus
\let\biglxor\bigoplus
\def\fail{\textsf{fail}}
\def\pass{\textsf{pass}}
\def\symdiff{\mathbin{\triangle}}
\def\hatf{{\hat f}}

\section{The Boolean Function}

\[ f : \zo^n \to \zo \]
\[ f : \pmo^n \to \pmo \]

Can be viewed as: a truth table, a circuit, a 2-coloring of the $n$-dimensional
discrete cube, an indicator of a set ($f(x) = 1 \iff x \in S$).

% voting
% Fourier/harmonic analysis
% $\GF(2^n)$, linearity

Some concepts that are studied: ``simple'' functions --- $k$-juntas and
dictatorships (only $k$~inputs, respectively one input, affect the function's
value); fairness (each input bit has the `same' influence over the output) and
noise-sensitivity (behavior under flipping of some input bits); symmetry
(behavior under permutations of inputs).

\subsection{Linear (homomorphic) functions}

Our goal today: linearity testing (homomorphism testing): to decide whether
a function~$f$, given as a blackbox (oracle), is \emph{linear}
(\emph{homomorphic}).

\begin{definition}
    A function $f : \zo^n \to \zo$ is  \emph{linear} (\emph{homomorphic}) 
    if \[ f(x) + f(y) = f(x+y) \] for every $x,y \in \zo^n$.
\end{definition}
(The addition $x+y$ is addition modulo~$2$ in the vector space $(\Z_2)^n$;
that is, $x+y = (x_1, \dots, x_n) + (y_1, \dots, y_n) = (x_1 \lxor y_1,
\dots, x_n \lxor y_n)$.)

\paragraph{Examples}
\begin{itemize}
    \item The constant function $f(x) \equiv 0$ is homomorphic ($f(x) + f(y) = 0+0 = 0 = f(x+y)$).
    \item The constant function $f(x) \equiv 1$ is not ($1+1 \ne 1$).
    \item The projection function $f(x) = x_i$ (for some fixed~$i$) is a homomorphism.
    \item As is the function $f(x) = \biglxor_{i=1}^n x_i$.
\end{itemize}
\begin{claim}
    A function $f : \zo^n \to \zo$ is homomorphic iff it is one of the functions
    $f_S(x) = \biglxor_{i\in S} x_i$ (for $S \subset [n]$).
\end{claim}
\begin{proof-sketch}
    Every homomorphic function is uniquely determined by the values on the
    vectors $e_i = (0, \dots, 0, 1, 0, \dots, 0)$ (with $1$ at the $i$th
    coordinate, $1 \le i \le n$).  Since there are $2^n$ possible settings
    for the values $f(e_i)$ ($1 \le i \le n$), there are $2^n$ linear functions.
    It is easy to see that all functions $f_S$ are linear, and there are 
    $\abs{\set{S : S \subset [n]}} = 2^n$ of them.
    \qed
\end{proof-sketch}
\paragraph{Note}  If $S=\emptyset$ then $f_S(x) \equiv 1$, i.e., $f_\emptyset$
is a constant function.

\subsection{Testing for linearity}

Given a function $f$ as a blackbox, in order to check whether or not it is
linear, we have to query it on \emph{every} possible input.  For example, the
function given by $f(x) = 1$ if $x = e_{17}$ and $f(x) = 0$ otherwise is not
homomorphic, but agrees with the zero homomorphism everywhere except at $x
= e_{17}$.

\begin{definition}
    A function $f$ is \emph{$\epsilon$-close to linear} if there exists
    a linear function~$g$ that agrees with $f$ on all but an $\epsilon$-fraction
    of the domain; that is,
    \[ \Pr_x[f(x) = g(x)] = \frac{\abs{\set{x : f(x) = g(x)}}}{2^n} \ge 1-\epsilon. \]
    Otherwise, $f$ is \emph{$\epsilon$-far from linear}.
\end{definition}

% $\epsilon$ is a small constant

\subsubsection{Proposed tester}
\label{proposedTester}
\begin{itemize}
    \item Repeat $r = \bigO(\frac{1}{\epsilon} \log \frac{1}{\delta^*})$ times:
    \begin{itemize}
        \item Pick $x, y \in_R \zo^n$ independently and uniformly.
        \item If $f(x) + f(y) \ne f(x+y)$:
        \begin{itemize}
            \item Output \fail{} and halt.
        \end{itemize}
    \end{itemize}
    \item Output \pass{}.
\end{itemize}

\subsubsection{Analysis}
\begin{claim}\label{l9:linear:iff:Prob:eq:1}
    $f$ is linear if and only if $\Pr[\pass] = 1$.
\end{claim}
\begin{claim}
    If $\Pr_{x,y}[f(x) + f(y) \ne f(x+y)] \ge \epsilon$
    then $\Pr[\fail] \ge 1-\delta^*$.
\end{claim}
\begin{claim}\label{l9:claim:epsclose:then:lowfailprob}
    If $f$ is $\epsilon$-close to linear, then the test fails with probability
    at most $3\epsilon$. 
\end{claim}
\begin{proof-idea}
    Let $A_x$ denote the event $f(x) \ne g(x)$.  Then
    $\Pr_x[A_x] \le \epsilon$ and thus
    $\Pr[\fail] \le \Pr_{x,y}[A_x \lor A_y \lor A_{x+y}] \le 3\epsilon$ by union bound.
\end{proof-idea}

\paragraph{Plan}
By claim~\ref{l9:linear:iff:Prob:eq:1}, the test \fail{}s with probabiliy zero
iff the distance of $f$ from linear is zero.  By
claim~\ref{l9:claim:epsclose:then:lowfailprob}, a similar relation also holds
--- in one direction --- if we say `small' instead of `zero'.  The remainder of
this lecture shows the converse of
claim~\ref{l9:claim:epsclose:then:lowfailprob}.

\subsection{Notational switch}

We now consider boolean functions as $f:\pmo^n \to \pmo$ rather than
$f:\zo^n\to\zo$:  we map $0 \mapsto +1$ and $1 \mapsto -1$, and write the
operation as multiplication ($x\cdot y = (x_1 y_1, \dots, x_n y_n)$ for $x,
y \in \pmo^n$) rather than addition ($x + y = (x_1 \lxor y_1, \dots, x_n \lxor
y_n)$ for $x,y \in \zo^n$).  (In other words, we switch our representation from
the group $\Z_2$ of integers modulo~$2$ to the group~$\mu_2$ of square roots of
unity.)

\paragraph{Example}  The homomorphic functions are now written as $f_S(x)
= \prod_{i\in S} x_i$.  The rejection condition of the proposed linearity tester
is $f(x) \cdot f(y) \ne f(x\cdot y)$, where $x\cdot y$ is as defined in the
previous paragraph (and \emph{not} an inner product).

\subsection{Rejection probability}

It will be more convenient to represent the rejection condition of the proposed
tester in terms of equality rather than inequality.  We have the equivalence:
\[ f(x)f(y) \ne f(xy) \iff \bigl(f(x) f(y)\bigr) f(xy) = -1 \]
which suggests to consider the following indicator:
\[
    \frac{1 - f(x)f(y)f(xy)}{2} =
    \begin{cases}
        0, & \mbox{if the test accepts;} \\
        1, & \mbox{if the test rejects.}
    \end{cases}
\]
We also define
\[ \delta = \E_{x,y} \left[\frac{1 - f(x)f(y)f(xy)}{2}\right] \]
as the \emph{rejection probability} of one loop-iteration of the proposed
tester.  This gives the \emph{acceptance probability} of one loop-iteration of
that tester as:
\[ 1-\delta = \E_{x,y} \left[\frac{1 + f(x)f(y)f(xy)}{2}\right]. \]

\section{Basics of Fourier analysis of parity functions}

$\mathcal{G} = \set{g : \pmo^n \to \R}$ is a $2^n$-dimensional vector space (over
the field~$\R$, i.e., linear combinations are to be taken with real
coefficients).  This space is equipped with the inner product
\[ \ip{f,g} = \frac{1}{2^n} \sum_{x \in \pmo^n} f(x) g(x). \]

\subsection{Looking for a basis}

We look for a convenient basis of~$\mathcal{G}$.
\begin{itemize}
    \item The first idea is the \emph{indicator functions}: the functions~$e_a$
    (for $a \in \pmo^n$) given by $e_a(x) = 1$ if $a=x$ and $0$ otherwise.

    It is easy to see that $\set{e_a : a \in \pmo^n}$ is a basis, and that $g
    = \sum_a g(a) \cdot e_a$ (i.e., $g(x) = \sum_a g(a) \cdot e_a(x)$) for any
    function~$g$.

    \item However, the basis of \emph{character functions} $\chi_S(x) = \prod_{i
    \in S} x_i$ will be more convenient.  (These are the functions we used to
    call~$f_S$.)
\end{itemize}

\clearpage
\begin{lemma}
    $\set{\chi_S : S \subset [n]}$ is an orthonormal basis.
\end{lemma}
\begin{proof}
    Let $S \ne T$ be two distinct subsets of~$[n]$, and let $j \in S \symdiff
    T = \set{x : (x \in S) \ne (x \in T)}$.  Denote ``$x$ with the $j$th bit
    flipped'' by `$x^{\lxor j}$'.  Then
    \[ \ip{\chi_S, \chi_S} = \frac{1}{2^n} \sum_x \underbrace{\chi_S(x)^2}_{=1} = 1 \]
    and
    \begin{displaymath}
    \begin{split}
        \ip{\chi_S, \chi_T}
            &= \frac{1}{2^n} \sum_x \chi_S(x) \chi_T(x)
             = \frac{1}{2^n} \sum_x \biggl(\prod_{i \in S} x_j \cdot \prod_{j \in T} x_j\biggr)
          \\&= \frac{1}{2^n} \sum_x \prod_{i \in S \symdiff T} x_i
               \qquad\mbox{(because $\set{x_i:i\in S\cap T}$ cancel out)}
          \\&= \frac{1}{2^n} \sum_{\set{x,x^{\lxor j}}}
                             \biggl( \prod_{i \in S \symdiff T} x_i
                                    +\prod_{i \in S \symdiff T} (x^{\lxor j})_i \biggr)
          \\&= \frac{1}{2^n} \sum_{\set{x,x^{\lxor j}}}
                             \biggl(           x_j  \cdot \prod_{j\ne i \in S \symdiff T} x_i
                                    +\overline{x_j} \cdot \prod_{j\ne i \in S \symdiff T} (x^{\lxor j})_i \biggr)
          \\&= \frac{1}{2^n} \sum_{\set{x,x^{\lxor j}}}
                             \biggl(           x_j  \cdot \prod_{j\ne i \in S \symdiff T} x_i
                                    +\overline{x_j} \cdot \prod_{j\ne i \in S \symdiff T} x_i \biggr)
          \\&= \frac{1}{2^n} \sum_{\set{x,x^{\lxor j}}}
                             (x_j + \overline{x_j})
                             \biggl( \prod_{i \in S \symdiff T, i\ne j} x_i \biggr)
             = \frac{1}{2^n} \sum 0 = 0.
    \end{split}
    \end{displaymath}
\end{proof}

\begin{remark}
    The technique of separating out $x_j$ and its complement is an example of a \emph{pairing argument}.
    It considers together all pairs of words that differ only on a specific
    coordinate; for instance,
    $(+1, +1, -1, +1)$ with $(+1, +1, +1, +1)$,
    $(+1, +1, -1, -1)$ with $(+1, +1, +1, -1)$,
    $(-1, -1, -1, +1)$ with $(-1, -1, +1, +1)$,
    etc.
\end{remark}

\begin{corollary}
    We can write every function $f$  as $f = \sum_{S \subset [n]} \hatf(S)
    \chi_S$, where $\hatf(S) = \ip{f,\chi_S}$.
\end{corollary}


For example, if $f:x\mapsto x_i$ is the projection function,  we have that $f=\chi_i$, thus the Fourier coefficients of $f$ 
are $\hat{f}(S)=\langle \chi_{i}, \chi_S \rangle$ which is equal to $1$ if $S=\{i\}$ and $0$ otherwise. 
Similarly, if $f:x\mapsto 1$ is the constant function, then $f=\chi_{\emptyset}$ and $\hat{f}(S)$ will be equal to 
$1$ if $S=\emptyset$ and $0$ otherwise. 



\subsection{Some useful facts about the Fourier Transform}

\begin{lemma} 
$\chi_S\cdot \chi_T = \chi_{S\Delta T}$
\end{lemma}

\begin{lemma}{Fourier Coefficient of any parity function}
\label{lemma:Coefficient}
$$f(x)=\chi_S(x) \Leftrightarrow \forall Z\subseteq [n],\hspace{0.2cm} \hat{f}(Z) = \left\{\begin{array}{ll} 1 & \mbox{when $S=Z$} \\ 0 & \mbox{Otherwise} \end{array}\right. $$
\end{lemma}

\begin{lemma}{Agreement with linear functions vs max Fourier coefficient}
\label{lemma:Agreement}
$$ \hat{f}(S) = 1 - 2 \Pr[f(x) \neq \chi_S(x)] \Leftrightarrow \DIST(f,\chi_S) = \frac{1-\hat{f}(S)}{2} $$ 

or equivalently

$$ \hat{f}(S) = -1 + 2 \Pr[f(x) \neq \chi_S(x)] \Leftrightarrow \DIST(f,\chi_S) = \frac{1-\hat{f}(S)}{2} $$ 
\end{lemma}
\begin{proof}

Its enough to prove that 

$$\DIST(f, \chi_S) = \Pr_{x\in \{\pm 1\}^n}[f(x) -\chi_S(x)].$$

The proof of this fact proceeds as follows: 

\begin{equation}
\begin{array}{rcl}
\hat{f}(S) & = & \frac{1}{2^n} \sum_{x}f(x)\chi_S(x) \\
	   &   & \\
	   & = & \frac{1}{2^n} \left[ \sum_{x,f(x)=\chi_S(x)} 1  +  \sum_{x,f(x)\neq\chi_S(x)} -1\right] \\
	   &   & \\
	   & = & (1- \DIST(f,\chi_S))\cdot 1  + \DIST(f,\chi_S)\cdot(-1) \\  
	   &   & \\
	   & = & 1 - 2 \DIST(f,\chi_S) \\
\end{array}
\end{equation}
\end{proof}

\begin{lemma}
If $S\neq T$ then $\DIST(\chi_S, \chi_T) = \frac{1}{2}$. 
\end{lemma}
\begin{proof}
Let  $f=\chi_T$. Then 
\begin{equation}
\begin{array}{rcl}
\hat{f}(S) & = & 0 \mbox{\hspace{0.4cm}( by lemma \ref{lemma:Coefficient})} \\
	   &   & \\
	   & = & 1-2\DIST(f,\chi_S)  \mbox{ \hspace{0.4cm}(by lemma \ref{lemma:Agreement})} \\ 
	   &   & \\
	   & \Rightarrow & \DIST(f,\chi_S)=\frac{1}{2}  \\  
	   &   & \\
	   & \Rightarrow & \DIST(\chi_T,\chi_S)= \frac{1}{2} \\
\end{array}
\end{equation}

\end{proof}

A very important theorem in Fourier Analysis is the following: 

\begin{theorem}[Plancherel's theorem]
Let $f,g:\{\pm 1\}\rightarrow \mathbb{R}$. Then 
$$\langle f, g \rangle = \E_{x\in \{\pm 1\}^n}[f(x)g(x)]= \sum_{S\subseteq [n]} \hat{f}(S)\hat{g}(S).$$
\end{theorem}
\begin{proof}
$$
\begin{array}{rcl}
\langle f, g\rangle  & = &  \langle \sum_{S}\hat{f}(S)\chi_S , \sum_{T} \hat{g}(T)\chi_{T}  \rangle\\
	   	     &   & \\
	   	     & = & \sum_{S}\sum_{T} \hat{f}(S)\hat{g}(T) \langle \chi_S, \chi_T \rangle \mbox{\hspace{0.4cm} by bilinearity of $\langle,\rangle $}\\
	   	     &   & \\
		     & = & \sum_{S} \hat{f}(S)\hat{g}(S)  \mbox{\hspace{0.3cm} (because $\langle \chi_S,\chi_T\rangle=1$ if $S=T$ and $0$ if $S\neq T$)}
\end{array}
$$
\end{proof}

We call special attention to the following corollary of Plancherel's theorem: 

\begin{corollary}[Parseval's Theorem]
If $f:\{\pm 1\}^n \rightarrow \mathbb{R}$ then $\langle f,f\rangle= \E[f(x)^2] = \sum_S \hat{f}(S)^2$. 
\end{corollary}

Which for boolean functions $f:\{0,1\}^n\rightarrow \{\pm 1\}$ reduces to the next corollary, by observing that 
in this case $f(x)^2=1$ for every $x$.

\begin{corollary}[Boolean Parseval's Theorem]
If $f:\{\pm 1\}^n\rightarrow\{\pm 1\}$ then $\sum_S \hat{f}(S)^2=1$.
\end{corollary}



\begin{lemma}
$\E[f]=\E[f(x)\cdot 1] = \hat{f}(\emptyset)\chi_{\emptyset}(\emptyset)= \hat{f}(\emptyset)$. 
\end{lemma}

\begin{lemma}
$\E[\chi_S(x)] = \left\{
\begin{array}{cl} 
1 & \mbox{if $S=\emptyset$} \\ 
0 & \mbox{Otherwise} \\
\end{array}
\right.$
\end{lemma}


%\begin{figure}[htp]
%\centering
%\includegraphics[scale=0.8]{inspectionQuestion2}
%\caption{Question 2}\label{figure:question2}
%\end{figure}

\section{Linearity Testing}

The goal of this section is to prove the converse of claim~\ref{l9:claim:epsclose:then:lowfailprob}, i.e, to show that if $f$ is $\epsilon$-far from linear, then the probability that 
the algorithm described in subsection \ref{proposedTester} finds two $x,y$ for which $f(x + y) \neq f(x) + f(y) $
is high. More precisely,

$$\Pr[f(x)f(y)f(x\cdot y)= -1] \geq \epsilon $$

\begin{lemma}[Main Lemma]
$$ 1- \delta = \Pr[f(x)f(y)f(x y) = 1] = \frac{1}{2} + \frac{1}{2}\sum_{S\in [n]} \hat{f}(s)^3 $$
\end{lemma}
\begin{proof}
$$1-\delta = \E_{xy}\left[ \frac{1+ f(x)f(y)f(xy)}{2}\right] = \frac{1}{2} + \frac{1}{2} \E_{xy}[f(x)f(y)f(xy)]$$

and 

$$
\begin{array}{rcl}
 \E_{xy}[f(x)f(y)f(xy)] & = &   \E_{xy}[(\sum_{S}\hat{f}(S)\chi_S(x) ) (\sum_{T}\hat{f}(T)\chi_T(y) )(\sum_{U}\hat{f}(U)\chi_T(xy) ) ] \\ 
	   	     &   & \\
	   	     & = & \E_{xy}[\sum_{STU}\hat{f}(S)\hat{f}(T)\hat{f}(U) \chi_{S}(x)\chi_{T}(y)\chi_{U}(xy)] \\
	   	     &   & \\
		     & = & \sum_{STU}\hat{f}(S)\hat{f}(T)\hat{f}(U) \E[\chi_{S}(x)\chi_{T}(y)\chi_{U}(xy)] \\
		     &   & \\
		     & = & \sum_{S=T=U} \hat{f}(S)^3.
\end{array}
$$

The last equality follows from the fact that 

$\E_{xy}[\chi_S(x)\chi_T(y)\chi_U(xy)] = \E[\chi_S(x)\chi_U(x)] \cdot \E[\chi_T(y)\chi_U(y)] = 
\left\{\begin{array}{cl} 
1 & \mbox{if $S=U$ and $T=U$} \\
0 & \mbox{otherwise}
\end{array} \right. $


\end{proof}


Now we are ready to prove the goal stated in the beginning of this section. 

\begin{proof}
Assume $\Pr[f(x)f(y)f(xy) = -1] < \epsilon$. Then we show that $f$ is $\epsilon$-close to linear. 
$$ 1- \epsilon = \Pr[f(x)f(y)f(x y) = 1] = \frac{1}{2} + \frac{1}{2}\sum_{S\subseteq [n]} \hat{f}(S)^3 $$

then 

$$
\begin{array}{rcl}
1-2\epsilon  & \leq &  \sum_{S\subseteq [n]}\hat{f}(S)^3 \\
	   	     &   & \\
	   	     & \leq & \max_{S}{\hat{f}(S)} \sum_{S\subseteq [n]} \hat{f}(S)^2 \\ 
	   	     &   & \\
		     & \leq  & \max_S{\hat{f}(S)} \\ 
\end{array}
$$
Now let $T$ be such that $\hat{f}(T)=\max_{S}{\hat{f}(S)}$. Then $1-2\epsilon \leq \hat{f}(T)$. By lemma \ref{lemma:Agreement} $\DIST(f,\chi_{T}) \leq \epsilon$.  
\end{proof}


\end{document}




