\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\usepackage{amsfonts}


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

\newenvironment{proof-of-claim}{\noindent{\bf Proof of Claim}\hspace*{1em}}{\qed\bigskip}
\newcommand{\sgn}{\operatorname{{\mathrm sgn}}}

\def\Ex{{\rm E}\,}
\def\sgn{{\rm sgn}\,}

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

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{26}{May 10, 2007}{Ronitt Rubinfeld}{Chih-yu Chao}

%%%% body goes in here %%%%
\section{Recap from Last Time}
\begin{define}[Fourier cofficient]{
$\hat{f}(s) = \langle f, \chi_s \rangle = \frac{1}{2^n}\sum_{x \in \{\pm1\}^n}\limits f(x)\chi_s(x)$
}
\end{define}

\begin{theorem}
$\forall_{f, x} \  f(x) = \sum_{s\subset [n]}\limits \hat{f}(s)\chi_s(x)$
\end{theorem}

\par
Last time, we learned that the magnitute of the Fourier coefficient is in agreement with the linear function. Based on this, we can use Fourier analysis to test linearity.

\section{Uses of Fourier Analysis}
\par
Now, we are going to use Fourier analysis to:
\begin{enumerate}
\item estimate sums of powers of degree 1 Fourier coefficient of $f$
\item estimate the maximum of degree 1 Fourier coefficient
\end{enumerate}

\subsection{Estimate sums of powers}
\par
We would like to estimate sums of powers of degree 1 Fourier coefficients of $f$, given oracle access to $f$. (We are only inerested in sets of size 1, and thus ``degree 1''.)
\[\sum_{|s| = 1}\limits\hat{f}(s)^p \qquad (\textrm{for } p \geq 2)\]
\par
The algorithm is a random process:
\begin{itemize}
\item Pick $x^{(1)}, x^{(2)}, \ldots, x^{(p-1)} \in_\mathbb{R} \{\pm1\}^n$ uniformly
\item Pick noise vector $\mu$ such that 
$\textrm{entry }
\begin{array}{ll}
+1 \\
-1 \end{array}
\textrm{ with probability } 
\begin{array}{ll}
\frac{1}{2}+\frac{\eta}{2} \\
\frac{1}{2}-\frac{\eta}{2}\end{array}
$
\item $y \leftarrow f(x^{(1)})f(x^{(2)})\cdots f(x^{(p-1)})f(x^{(1)}\odot x^{(2)}\cdots x^{(p-1)}\odot \mu)\qquad \qquad $ (note that for $p=3$, it almost looks
like a linearity test with noise)
\end{itemize}
\par
We will show: $\Ex[y] = \sum_{s \subseteq [n]}\limits \eta^{|s|}\hat{f}(s)^p$, which will look a lot like the analysis of the linearity test last time.\\
\par
\begin{proof}{
\[
\Ex[y] = \Ex \left[ \sum_{s_1, s_2, \ldots , s_p}\limits \hat{f}(s_1) \hat{f}(s_2) \cdots \hat{f}(s_{p-1}) \hat{f}(s_p) \chi_{s_1}(x^{(1)}) \cdots \chi_{s_{p-1}}(x^{(p-1)}) \chi_{s_p}(x^{(1)}\odot x^{(2)} \cdots x^{(p-1)} \odot \mu) \right]
\]
Since
\[
\chi_{s_p}(x^{(1)}\odot x^{(2)} 
\cdots x^{(p-1)} \odot \mu) = 
\chi_{s_p}(x^{(1)}\odot x^{(2)} \cdots x^{(p-1)}) \cdot \chi_{s_p}(\mu) 
= (\chi_{s_p}(x^{(1)}) \cdot \chi_{s_p}(x^{(2)}) \cdots \chi_{s_p}(x^{(p-1)})) 
\cdot \chi_{s_p}(\mu),
\]
then 
$$ \Ex[y]  = 
\sum_{s_1, s_2, \ldots , s_p}\limits \hat{f}(s_1) \cdots \hat{f}(s_p) \Ex \left[ \chi_{s_1 \triangle s_p}(x^{(1)}) \chi_{s_2 \triangle s_p}(x^{(2)}) \cdots \chi_{s_{p-1} \triangle s_p}(x^{(p-1)}) \chi_{s_p}(\mu) \right] $$
$$
 =  \sum_{s_1, s_2, \ldots , s_p}\limits \hat{f}(s_1) \cdots 
\hat{f}(s_p) 
\Ex \left[ \chi_{s_1 \triangle s_p}(x^{(1)}) \right] 
\Ex \left[ \chi_{s_2 \triangle s_p}(x^{(2)}) \right]
\cdots 
\Ex \left[ \chi_{s_{p-1} \triangle s_p}(x^{(p-1)}) \right]
\Ex \left[ \chi_{s_p}(\mu) \right]
$$
The last line follows since the terms in the expectation are independent.
\begin{itemize}
\item if $s_1 = s_2 = \cdots = s_p$, $s_i \triangle s_p = \emptyset$, then
$$\Ex \left[ \chi_{s_i \triangle s_p}(x^{(i)}) \right] = 1$$
Also $\Ex[\chi_{s_p}(\mu)] = \eta^{|s_p|}$  since:
\[
\Ex[\mu_i] = 1 \cdot (1+\frac{\eta}{2}) + (-1) \cdot (1-\frac{\eta}{2}) = \eta
\]
\[
\Ex [\prod_{i \in s_p}\limits \mu_i] = \prod_{i \in s_p}\limits \Ex[\mu_i] = \eta^{|s_p|} \ 
\Longrightarrow \Ex[\chi_{s_p}(\mu)] = \eta^{|s_p|}
\]
\item otherwise, some $s_i \triangle s_p \neq \emptyset$. 
In this case, using reasoning as in the last lecture, 
$\Ex[\chi_{s_i \triangle s_p}] = 0$ \\
so, the entire product equals 0.
\end{itemize}
Therefore, $\Ex[y] = \sum_s \limits \hat{f}(s)^p \eta^{|s|}$ \\
}\end{proof}
\par
We want to estimate $\sum_{|s| = 1}\limits \hat{f}(s)^p$ to an additive $\pm \eta^2$, so we do the following:
\begin{enumerate}
\item Estimate $\mathcal{A} \equiv \Ex[f(x^{(1)}f(x^{(2)})) \cdots f(x^{(p)})] = \hat{f}(\emptyset)^p$
\item Estimate $\mathcal{B} \equiv \Ex[f(x^{(1)})f(x^{(2)})) \cdots f(x^{(p)})f(x^{(1)} \odot x^{(2)} \odot \cdots \odot x^{(p-1)} \odot \mu)] = \sum_s \limits \eta^s \hat{f}(s)^p$
\end{enumerate}
\par
Using the additive version of Chernoff bound: for var $x\in[-1, 1]$, to additive $\pm \varepsilon$ needs $O(\frac{1}{\varepsilon ^2})$ queries $\Rightarrow$ we need $O(\frac{1}{\eta ^4})$ queries. However, we only got rid of one term, \emph{i.e.} $\mathcal{B} - \mathcal{A} = \sum_{|s| > 0}\limits \eta^{|s|}\hat{f}(s)^p \equiv \mathcal{C}$, and we want to estimate to witin $\pm \eta^2$, so we will show that $\frac{\mathcal{C}}{\eta}$ is already a good approximate of $\sum_{|s| = 1}\limits\hat{f}(s)^p$ (with additive error $\eta$).
\begin{claim}
$\frac{\mathcal{C}}{\eta}$ is a good estimate of $\sum_{|s| = 1}\limits \hat{f}(s)^p$
\end{claim}

\begin{proof-of-claim}{
%$\sum_{|s|= 1}\limits \eta \hat{f}(s)^p$ is what we want to get.
\[
\sum_{|s|= 1}\limits \eta \hat{f}(s)^p = \sum_{|s| > 0}\limits \eta ^{|s|} \hat{f}(s)^p - \sum_{|s| > 1}\limits \eta ^{|s|} \hat{f}(s)^p
\]
$
\sum_{|s| > 0}\limits \eta ^{|s|} \hat{f}(s)^p = \mathcal{C}
$, so we want to claim that $\sum_{|s| > 1}\limits \eta ^{|s|} \hat{f}(s)^p$ is not too big, \emph{i.e.} $\eta^{|s|}$ is exponentially decayed:
\[
\sum_{|s| > 1}\limits \eta ^{|s|} \hat{f}(s)^p \leq \eta^2 \sum_{|s|>1}\limits|\hat{f}(s)^p| \textrm{, or we can say }
\sum_{|s| > 1}\limits \eta ^{|s|} \hat{f}(s)^p \leq \eta^2 \sum_{|s|>1}\limits\hat{f}(s)^2 \textrm{ since }f\textrm{ is boolean, } |\hat{f}(x) \leq 1|.
\]
Thus, by Parseval's theorem in the Boolean case, 
$\sum_{|s|>1}\limits\hat{f}(s)^2 \leq 1 \Rightarrow \sum_{|s| > 1}\limits \eta ^{|s|} \hat{f}(s)^p \leq \eta^2$. \\
So, $\sum_{|s| = 1}\limits \hat{f}(s)^p = \frac{\mathcal{C}}{\eta} \pm \frac{\eta^2}{\eta} \Rightarrow \eta$-additive 
$\Rightarrow \frac{\mathcal{C}}{\eta}$ to within $\pm \eta$. \\
}\end{proof-of-claim}

\begin{theorem}
For $p \geq 2$, we can estimate $\sum_{|s| = 1}\limits \hat{f}(s)^p$ to within additive $\pm \eta$ with $O(\frac{p}{\eta^4})$ queries.
\end{theorem}


\subsection{Estimate the maximum}
\par
We can also use Fourier analysis to estimate the maximum of degree 1 Fourier coefficient. (Note that this is a weak estimate.)
\par
If $\forall_i \hat{f}(\{i\}) < \alpha$, then $\sum_{|s| = 1}\limits \hat{f}(s)^4 < \sum_{|s| = 1}\limits \alpha^2\hat{f}(s)^2 < \alpha^2 \cdot 1 \qquad (\ast) $ \\
(Parseval when $f$ is boolean)

\begin{define}
$f$ is $\tau$-regular if $|\hat{f}(\{i\})| < \tau \quad \forall_i$
\end{define}

\begin{theorem}
$\exists O(\frac{1}{\tau^{16}})$-query test with following behavior:
\begin{itemize}
\item if $\exists i$ such that $|\hat{f}(\{i\})| \geq \tau$ then $\Pr[reject] \geq \frac{3}{4}$ (not $\tau$-regular)
\item if $\forall_i |\hat{f}(\{i\})| < \frac{\tau^2}{4}$ then $\Pr[accept] \geq \frac{3}{4}$ ($\frac{\tau^2}{4}$-regular)
\end{itemize}
\end{theorem}

\begin{proof}
We estimate $\sum_i\limits \hat{f}(\{i\})^4$ to within $\frac{\tau^4}{4}$, and accept iff estimate $\geq \frac{\tau^4}{2}$. \\
If $\exists i$ such that $|\hat{f}(\{i\})| \geq \tau$, then $\sum\hat{f}(\{i\})^4 \geq \tau^4$. Estimate $\geq \frac{3}{4}\tau^4$, so will reject. \\
If $\forall_i |\hat{f}(\{i\})| \leq \frac{\tau^2}{4}$, then by $(\ast), \ \sum\hat{f}(\{i\})^4 \leq \frac{\tau^4}{16}$. Estimate $\leq \frac{5}{16}\tau^4 < \frac{1}{2}$ and will accept. \\
\end{proof}

\section{LTF: Linear Threshold Function}
\par
$f(x) = \sgn (w_1 x_1 + \cdots + w_n x_n + \theta)$, where \\
$x_i \in \{\pm 1\}, w_i \in \mathbb{R}, \theta \in \mathbb{R}, \sgn (x) = \left\{ \begin{array}{ll}
+1 \\
-1 \end{array} \right.\textrm{ if } \begin{array}{ll} 
x \geq 0 \\
x < 0 \end{array}$
\par
There is a constant time tester independent of $n$, but we will only look at a special case here: \\
$\tau$-regular balanced LTF's (``balanced'' means that $\theta = 0$)

\begin{theorem}
$\exists$ testing algorithm $\mathbf{A}$ that requires $O(\frac{1}{\tau^8})$ queries:
\begin{itemize}
\item If $f$ is a balanced $\tau$-regular $LTF$,
then $ \Pr[\mathbf{A}\textrm{ passes}] \geq \frac{3}{4}$
\item If $C\tau^{1/6}$-far from any balanced $\tau$-regular LTF, 
$\Pr[\mathbf{A}\textrm{ fails}] \geq \frac{3}{4}$ ($C$ is a constant that will be determined later)
\end{itemize}
\end{theorem}

\par
The high-level algorithm works this way:
\begin{enumerate}
\item Estimate $\sum_{|s| = 1}\limits \hat{f}(s)^4$ to additive $\pm\tau^2$, if $> 2\tau^2$, fail
\item Estimate $\sum_{|s| = 1}\limits \hat{f}(s)^2$ to additive $\pm C_1 \tau^{1/3}$ ($C_1$ is another constant), if within $\pm 2C_1\tau^{1/3}$ of $\frac{2}{\Pi}$, output pass; else fail
\end{enumerate}
\section*{}
\begin{center}
\emph{(To be continued in the next lecture ...)}
\end{center}
\end{document}