\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
\newenvironment{notation}{\noindent{\bf Notation}\hspace*{1em}}{\bigskip}
\newtheorem{exercise}{Exercise}
\newtheorem{example}{Example}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{1}{February 18, 2008}{Guy Kindler}{Gillat Kol}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This course covers topics concerning harmonic analysis of \emph{Boolean
functions}, and their relations to computer science. We often consider these functions
as special cases of functions to $\mathbb{R}$.
\begin{definition}
A function $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ is called a \textsf{Boolean function}.
\end{definition}
The main application of harmonic analysis is deducing \emph{global} \emph{properties}
from \emph{local} ones:
\begin{example}
Suppose that a Boolean function $f$ satisfies the following property:
\begin{equation}
\forall x,y\in\{-1,1\}:\ f(x) \cdot f(y)=f(x \cdot y). \label{local_property}
\end{equation}
Property \ref{local_property} is \textbf{local} in the sense that in order to verify it we
only need to consider point triplets. Using harmonic
analysis we can easily infer that $f$ satisfies the following \textbf{global}
property:
\begin{equation}
\exists S\subseteq[n]:\ f(x)=\prod_{i\in S}x_{i}. \label{global_property}
\end{equation}
That is, $f$ is the parity function of a subset of the coordinates.
\end{example}
Property \ref{global_property} can also be deduced without the use of harmonic analysis.
However, it is not clear how one can obtain the next robustness property with good parameters without harmonic analysis.
\begin{example}[robustness]
Suppose that $f$ does not satisfy the above property,
but is ``close'' to satisfying it. Specifically, suppose
\begin{equation}
\Pr\left[f(x)\cdot f(y)=f(x\cdot y)\right]\geq0.9.
\end{equation}
Using harmonic analysis it can be shown that $f$ is close to a parity
function. Namely, one can show that $f$ satisfies a property of the form:
\begin{equation}
\exists S\subseteq[n]:\ \Pr\left[f(x)=\prod_{i\in S}x_{i}\right]\geq p
\end{equation}
for some $p\geq0.7$. For now, we are not interested in the best possible value of $p$.
\end{example}
\vspace{0.2in}
Harmonic analysis turns out to be useful in different fields of theoretic
CS, e.g.: property testing, proof checking (PCP), circuit lower bounds, graph threshold phenomena.
\section*{Influence}
The \emph{influence} of an input variable $x_{i}$ on a function $f$
is the probability that flipping this variable at a random input $x$ will alter the value
of the function $f$. The influence measures of how "energetic" $f$ is; a high $I(f)$
means that $f$ is typically quite sensitive to bit flips, a low $I(f)$ indicates that it is not so
sensitive.
Denote $e_{i}=(1,...,1,\underset{pos\, i}{-1},1,...,1)$.
For $x=(x_{1},\ldots,x_{n})$ and $y=(x_{1},\ldots,x_{n})$ let $x\cdot y=(x_{1}\cdot y_{1},\ldots,x_{n}\cdot y_{n})$.
\begin{definition}[influence]
Let $f$ be a Boolean function. The \textsf{influence}
of the $i^{th}$ coordinate on $f$ is $I_{i}(f)=\Pr_{x}\left[f(x)\neq f(x\cdot e_{i})\right]$.
The \textsf{total influence} of $f$'s coordinates is $I(f)=\sum_{i=1}^{n}I_{i}(f)$.
\end{definition}
Note that $I(f)=n\cdot\Pr_{x,i}\left[f(x)\neq f(x\cdot e_{i})\right]$.
\vspace{0.1in}
Influence is a useful parameter when studying boolean functions,
and harmonic analysis allows us to answer influence-related questions.
\begin{example}
Denote $\mathtt{parity}(x)=\prod_{i\in[n]}x_{i}$. $I(\mathtt{parity})=n$.
\end{example}
\begin{exercise}
Show $I(f)=n$ implies $f=\pm\mathtt{parity}$.
\end{exercise}
\vspace{0.1in}
$\triangleright$ \emph{What is the Boolean function with the smallest total influence?}
Clearly $f(x)\equiv1$ has total influence $0$. To make this question
more interesting, we require the function to be \emph{balanced}, i.e. attain
$-1$ and $1$ an equal number of times.
\begin{definition} [balanced function] $f$ is called \textsf{balanced}
if $\mathbb{E}_{x}\left[f(x)\right]=0$.
\end{definition}
\vspace{0.1in}
$\triangleright$ \emph{Now, what is the balanced Boolean function with the smallest
influence? } One option to consider is the following:
\begin{example}
$f(x)=x_{17}$ is a balanced function with low influence, $I(f)=1$.
In general, $I(\mathtt{dictatorship})=1$ for any function $\mathtt{dictatorship}$
that depends only on a single variable.
\end{example}
It turns out that dictatorship has the minimal influence among all balanced functions.
Furthermore, we will show that this result is robust.
Without the use of harmonic analysis it not clear how this result can be proved,
even without the robustness property.
\vspace{0.1in}
The function suggested in the last example depends only on coordinate.
$\triangleright$ \emph{What if $f$ is balanced, but must depend on all the coordinates?}
\vspace{0.1in}
Denote by $S_{n}$ the group of all permutations of $n$ elements.
\begin{definition} [symmetric function] A Boolean function $f$ is called \textsf{symmetric} if
$\forall\pi\in S_n,\,(x_{1},\ldots,x_{n})\in\{-1,1\}^{n}$ it holds
that $f(x_{1},\ldots,x_{n})=f(x_{\pi(1)},\ldots,x_{\pi(n)})$.
\end{definition}
\begin{definition}
A group $G\subseteq S_n$ is called transitive if $\forall i,j$ $\exists\pi\in G$
such that $\pi(i)=j$.
\end{definition}
\begin{definition} [transitive function] A Boolean function $f$ is called \textsf{transitive}
if there exists a transitive group of permutations $G$ such that
$\forall\pi\in G,\,(x_{1},\ldots,x_{n})\in\{-1,1\}^{n}$ it holds
that $f(x_{1},\ldots,x_{n})=f(x_{\pi(1)},\ldots,x_{\pi(n)})$.
\end{definition}
Note that every symmetric function is also transitive (take $G=S_n$).
\begin{example}
$f(x_{1},x_{2},x_{3},x_{4})=(x_{1}\wedge x_{2})\,\vee\,(x_{3}\wedge x_{4})$
is transitive. E.g., for $i=1$ and $j=4$ the permutation $\pi=(4312)$
satisfies $\pi(1)=4$ and $f(x_{1},x_{2},x_{3},x_{4})=f(x_{\pi(1)},x_{\pi(2)},x_{\pi(3)},x_{\pi(4)})$
$=f(x_{4},x_{3},x_{1},x_{2})$.
\end{example}
\begin{exercise}
Show that if $f$ is transitive then $\forall i,j$ it holds that
$I_{i}(f)=I_{j}(f)$.
\end{exercise}
Let us consider the simplest symmetric function one can think of:
\begin{example}
The majority function $\mathtt{maj}(x)=sign(\sum_{i=1}^{n}x_{i})$
is symmetric and balanced for odd $n$'s.
Assume for simplicity that $n$ is odd. It holds:
\begin{eqnarray*}
I(\mathtt{maj}) & = & n\cdot\Pr_{x,i}\left[\mathtt{maj}(x)\neq\mathtt{maj}(x\cdot e_{i})\right]\\
& \leq & n\cdot\Pr_{x}\left[\sum_{i=1}^{n}x_{i}\in\{1,-1\}\right]\\
& \approx & n\cdot\frac{1}{\sqrt{n}}\\
& = & \sqrt{n}\end{eqnarray*}
\end{example}
\vspace{0.1in}
$\triangleright$ \emph{Are there transitive balanced functions with maximal influence
smaller than that of the majority function?} Yes! We introduce a function
called $\mathtt{tribes}$. The tribes function is transitive, but has a smaller symmetry group.
\begin{example}
Denote $n=c\cdot k\lg k$, with some constant $c$. We partition the
$n$ coordinates into $ck$ \textquotedblleft{}tribes\textquotedblright{}
of size $\lg k$ each. For a given $x\in\{-1,1\}^{n}$, we set $f(x)=1$
iff there exists a tribe such that all members of the tribe are $1$.
Formally: \[
f(x)=(x_{1}\wedge\cdots\wedge x_{\lg k})\vee(x_{\lg k+1}\wedge\cdots\wedge x_{2\lg k})\vee\cdots\vee(x_{n-\lg k+1}\wedge\cdots\wedge x_{n}).\]
Note that the function is transitive since all tribes are of the same
size. The function is also (roughly) balanced: The probability that
any given tribe is voting unanimously $1$ is $2^{-\lg k}=\frac{1}{k}$.
Thus, the probability that no tribe gives a unanimous $1$ is $(1-\frac{1}{k})^{ck}\rightarrow\frac{1}{2}$
by appropriate choice of $c=ln2$, so the function is balanced.
\end{example}
Let us calculate the influence of the $i^{th}$ variable (by symmetry,
all variables have the same influence). The $i^{th}$ variable makes
a difference only if every other tribe has not made a unanimous $1$
vote, and if all other members of $i$'s tribe voted $1$. This happens
with probability \[
I_{i}(f)=\left(1-\frac{1}{k}\right)^{ck-1}\cdot\left(\frac{1}{2}\right)^{\lg k-1}\approx\theta\left(\frac{1}{k}\right)=\theta\left(\frac{\lg n}{n}\right).\]
We conclude that $I(f)=\theta(\lg n)$.
\vspace{0.2in}
It turns out that the tribes function has the minimal total influence among all balanced transitive Boolean functions,
and majority among all the symmetric ones.
The minimality of the total influence of the tribes function can be deduced from the following result of Friedgut.
\begin{definition}[$J$-junta]
$f$ is a $J$-junta if it depends on at most $J$ coordinates.
\end{definition}
\begin{definition}[$(J,\epsilon)$-junta]
$f$ is a $(J,\epsilon)$-junta if there exists
a $J$-junta $g$ such that \[\Pr_{x}\left[f(x)=g(x)\right]\geq1-\epsilon.\]
\end{definition}
\begin{theorem}[Freidgut 94']
Let $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$. If $I(f)\leq k$
then for every $\epsilon>0$, $f$ is $(9^{\frac{k}{\epsilon}},\epsilon)$-junta.
\end{theorem}
Friedgut's Theorem is a kind of "symmetry-breaking" result. Suppose that we try to construct an "almost transitive" function with low influence. We can push the influence lower and lower until $\theta(log n)$ while keeping the function close to transitive, but as soon as one pushes the influence below this threshold, it has to break symmetry and become essentially a kind of junta.
This phenomenon has analogies in physics, and it is very useful in theoretical computer science.
We may see some applications of this phenomenon in this course.
\end{document}