% ToC#316, ToC Library number 1
% 8/30/08 acr ToC typesetting first pass.
\documentclass[gradsurvey]{toclibrary}

\tocdetails{%
   number=1,year=2008, firstpage=1,
   received={June 30, 2007},
   revised={August 5, 2008},
   published={September 25, 2008}
}



\runningauthor{Ronald de Wolf}
\runningtitle{A Brief Introduction to Fourier Analysis on the Boolean Cube}
\copyrightauthor{Ronald de Wolf}

\begin{document}

\begin{frontmatter}[classification=text]
\title{A Brief Introduction to Fourier Analysis\\ on the Boolean Cube}
\tocpdftitle{A Brief Introduction to Fourier Analysis on the Boolean Cube}
\tocpdfauthor{Ronald de Wolf}
\author[ronald]{Ronald de Wolf\thanks{CWI Amsterdam. 
%% Email rdewolf@cwi.nl. 
Partially supported by a Veni grant from the Netherlands Organization for Scientific Research (NWO), and by the European Commission under the Integrated Project Qubit Applications (QAP) funded by the IST directorate as Contract Number 015848.}}


\begin{abstract}
We give a brief introduction to the basic notions of Fourier analysis
on the Boolean cube,
illustrated and motivated by a number of applications 
to theoretical computer science.
\end{abstract}


\tocacm{F.0, F.2}
\tocams{42-02, 68-02, 68Q17, 68Q25, 68Q32}
\tockeywords{Fourier analysis, Boolean functions, coding theory, learning theory, hypercontractive inequality, influence of variables, polynomial}


\end{frontmatter}


\def\01{\{0,1\}}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\eps}{\varepsilon}
\newcommand{\Inf}{\mbox{Inf}}
\newcommand{\sign}{\text{sign}}
\newcommand{\poly}{\text{poly}}
\newcommand{\Exp}{{\mathbb{E}}}
\newcommand{\Var}{\text{Var}}
\newcommand{\norm}[1]{||#1||}
\newcommand{\inp}[2]{\langle{#1},{#2}\rangle} % inproduct, < , >


\section{Introduction}

Fourier transforms are widely used in mathematics, computer science, and engineering.
Examples include signal processing, data compression, fast multiplication of polynomials, quantum computing, as well as many others.
The Fourier transform most commonly used is the one over cyclic groups.
Here one decomposes a signal or function as a sum of periodic functions such as $\chi_y(x)=e^{2\pi i xy/n}$ or
(in the real case) sines and cosines. 

In the study of functions of $n$ Boolean variables, however, the most natural Fourier transform 
to consider is the one over the Abelian group $\mathbb{Z}_2^n$.  This is known as Fourier analysis over the Boolean cube,
and has over the past two decades become one of the most important and versatile tools for theoretical computer scientists.
The main purpose of this paper is to give a first introduction to the basic notions and properties of this area (\secref{secdefs})
and to illustrate and motivate them by means of a few relatively simple but elegant applications from diverse areas
(\secref{secsimplefourierapplications} and~\secref{secbonamibeckner}).
The intended audience is theoretical computer scientists interested in adding these techniques to their toolbox.
The selection of applications is somewhat biased by the author's own experience in learning this material in recent years,
and is by no means a complete survey---such a survey would probably require a whole book by now.
However, in \secref{seclastsection} we give pointers for further reading. 




\section{Definitions and basic properties}\label{secdefs}

\subsection{The vector space of functions on the Boolean cube}

Consider the $2^n$-dimensional vector space of all functions $f:\01^n\rightarrow\R$.
We define an inner product on this space by
$$
\inp{f}{g}=\frac{1}{2^n}\sum_{x\in\01^n}f(x)g(x)=\Exp[f\cdot g]\,,
$$
where the latter expectation is taken uniformly over all $x\in\01^n$.
This defines the $\ell_2$-norm
$$
\norm{f}_2=\sqrt{\inp{f}{f}}=\sqrt{\Exp[f^2]}\,.
$$


\subsection{The Fourier transform}

It will be convenient to identify a set $S\subseteq[n]=\{1,\ldots,n\}$ with its characteristic vector $S\in\01^n$.
For example for $S=\{1,3\}\subseteq[3]$ we can also write $S=(1,0,1)$ or $S=101$. We will often go back and forth between these notations. 
For each $S\subseteq[n]$, define a function $\chi_S:\01^n\rightarrow\{\pm 1\}$ by
$$
\chi_S(x)=(-1)^{S\cdot x}\,,
$$
where $S\cdot x=\sum_{i=1}^n S_ix_i=\sum_{i\in S}x_i$.
It is easy to see that
$$
\inp{\chi_S}{\chi_T}=\delta_{ST}= \begin{cases} 1 & \text{ if $S=T$}\\ 0 & \text{ if $S\neq T$} \end{cases}\,,
$$
hence the set of all $\chi_S$ is an orthonormal basis (called the \emph{Fourier basis}) for the space of all real-valued functions on $\01^n$.
Of course, there are many different bases for this space. What makes the Fourier basis particularly
useful for computer science is that the basis functions themselves have a simple
computational interpretation, namely as parity functions: 
$\chi_S(x)=-1$ if the number of $S$-variables having value 1 in the input $x$ is odd, and $\chi_S(x)=1$ if that number is even.

For any $f:\01^n\rightarrow\R$ we can define another function $\widehat{f}:\01^n\rightarrow\R$ by
$$
\widehat{f}(S)=\inp{f}{\chi_S}=\Exp[f\cdot\chi_S]\,.
$$
The linear map 
$$
\mathcal{F}:f\mapsto\widehat{f}
$$ 
is called the \emph{Fourier transform}.
The function $\widehat{f}=\mathcal{F}(f)$ is the Fourier transform \emph{of~$f$}, 
and $\widehat{f}(S)$ is the Fourier \emph{coefficient} of~$f$ at $S$.
This $\widehat{f}(S)$ may be viewed as a measure of the correlation between $f$ and $\chi_S$.
The set of Fourier coefficients is also called the \emph{Fourier spectrum} of $f$.
Since the $\chi_S$ form an orthonormal basis, the relation between $f$ and $\widehat{f}$ is
\begin{equation}\label{eqfourierexapnsion}
f=\sum_S\widehat{f}(S)\chi_S\,.
\end{equation}
Note that $f(\emptyset)=\sum_S\widehat{f}(S)$ is the sum of all Fourier coefficients,
while $\widehat{f}(\emptyset)=\Exp[f]$ is the average function value.  
A function is constant if, and only if, $\widehat{f}(S)=0$ for all $S\neq\emptyset$.

The \emph{degree} of $f$ is $\deg(f)=\max\{|S| \mid \widehat{f}(S)\neq 0\}$.
In particular the degree of the basis function $\chi_S$ is $|S|$, the number of variables it depends on.
Since $(-1)^{x_i}=1-2x_i$, the Fourier expansion Eq.~\eqref{eqfourierexapnsion}
represents $f$ as an $n$-variate \emph{polynomial} over the real numbers, of degree $\deg(f)$.

Let us consider some simple examples. If $f=\chi_S$ then $\widehat{f}(S)=1$ while all other Fourier coefficients are 0.
If $f(x)=\sum_{i\in S}x_i \bmod 2$ is a parity function in the usual 0/1 notation,
then $\widehat{f}(\emptyset)=1/2$ and $\widehat{f}(S)=-1/2$; all other coefficients are 0.
The special case where $S=\{i\}$ (\ie, $f(x)=x_i$) is known as a \emph{dictator} function, since its value is determined by only one variable.
A \emph{$k$-junta} is a function depending on at most $k$ variables; equivalently, there is a set $J\subseteq[n]$ of size $k$ such that 
$\widehat{f}(S)=0$ whenever $S\not\subseteq J$.
%The 2-bit OR-function has $\widehat{f}(\emptyset)=3/4$,  $\widehat{f}(\{1\})=\widehat{f}(\{2\})=-1/4$, and $\widehat{f}(\{1,2\})=1/4$.
Finally, if we pick a function $f:\01^n\rightarrow\{\pm 1\}$ uniformly at random, then each Fourier coefficient
is normally distributed with mean 0 and variance $1/2^n$, so much coefficients will be about $1/\sqrt{2^n}$ in absolute value.

Because the $\chi_S$ form an orthonormal basis, we immediately get the following equality:
$$
\inp{f}{g}=\sum_{S,T}\widehat{f}(S)\widehat{g}(T)\inp{\chi_S}{\chi_T}=\sum_S\widehat{f}(S)\widehat{g}(S)\,.
$$
In particular, with $f=g$ we obtain \emph{Parseval's Identity}:
$$
\norm{f}_2^2=\sum_S\widehat{f}(S)^2\,.
$$
This also implies
$$
\norm{f-g}_2^2=\sum_S(\widehat{f}(S)-\widehat{g}(S))^2\,.
$$
As an example, suppose $f$ is a probability distribution. Then we can analyze 
the $\ell_2$-distance between $f$ and the uniform distribution $g(x)=1/2^n$ as follows:
$$
\norm{f-g}_2^2=\sum_S(\widehat{f}(S)-\widehat{g}(S))^2=\sum_{S\neq\emptyset}\widehat{f}(S)^2\,,
$$
where we used $\widehat{f}(\emptyset)=\widehat{g}(\emptyset)=1/2^n$, 
and $\widehat{g}(S)=0$ whenever $S\neq\emptyset$.

\paragraph{Notational variants.}
The definition of $\mathcal{F}$ used here has become the standard one in computer science,
though one occasionally sees different normalizations. If we defined the inner product with a $2^{-n/2}$ instead of $2^{-n}$, 
then $\mathcal{F}$ would be its own inverse and Parseval would simply state $\norm{f}_2=\norm{\widehat{f}}_2$. 
However, with this modified inner product the $\chi_S$ functions no longer have norm~1.

Another variation is to view the variables as $\pm 1$-valued instead of 0/1-valued and to consider functions on $\{\pm1 \}^n$.
In this case the function $\chi_S$ is simply the product of the $S$-variables, and the Fourier representation 
is simply an $n$-variate multilinear polynomial over the reals, with $\widehat{f}(S)$ as the coefficient of the monomial $\chi_S$.
Similarly, depending on what is more convenient, we can treat the value of a Boolean function as 0/1-valued or as $\pm 1$-valued.
An advantage of the latter is that $\sum_S\widehat{f}(S)^2=\Exp[f^2]=1$ (by Parseval), which allows us to treat the squared Fourier coefficients as probabilities.

\subsection{Convolution}

Given any two functions $f,g:\01^n\rightarrow\R$, we define their \emph{convolution} $f*g:\01^n\rightarrow\R$ by
$$
(f*g)(x)=\frac{1}{2^n}\sum_{y\in\01^n}f(x\oplus y)g(y)\,,
$$
where `$\oplus$' denotes entrywise addition of $n$-bit strings.
If $X$ and $Y$ are independent $n$-bit random variables, with probability distributions $f$ and $g$, respectively,
then $2^n (f*g)$ is the distribution of the random variable $Z=X\oplus Y$:
$$
\Pr[Z=z]=\Pr[X=z\oplus Y]=\sum_{y\in\01^n}f(z\oplus y)g(y)\,.
$$
This arises naturally in certain computer-science settings, for instance when $Y$ is some error-pattern corrupting $X$,
or when $Y$ is some ``mask'' used to hide $X$ as in one-time pad encryption.
%Note that if $Y$ is uniformly distributed (\ie, $g(y)=1/2^n$ for each $y$), then $2^n (f*g)(z)=1/2^n$ for each $z\in\01^n$,
%so $X\oplus Y$ is uniformly distributed as well.

An important property is that the Fourier transform of the convolution $f*g$ 
is the product of the Fourier transforms of $f$ and $g$.
This is easily verified by writing out the definitions:
\begin{eqnarray*}
\widehat{f*g}(S) & = & \frac{1}{2^n}\sum_x (f*g)(x)\chi_S(x)\\
 & = & \frac{1}{2^{2n}}\sum_x \sum_y f(x\oplus y)g(y)\chi_S(x)\\
 & = & \frac{1}{2^n}\sum_y g(y)\chi_S(y)\left(\frac{1}{2^n}\sum_x f(x\oplus y)\chi_S(x\oplus y)\right)\\
 & = & \widehat{f}(S)\cdot \widehat{g}(S)\,.
\end{eqnarray*}
Suppose we have two functions $h_0=f*g_0$ and $h_1=f*g_1$, for instance from applying the same noise-process $f$ to distributions
$g_0$ and $g_1$.  Using the convolution, we can rewrite their distance as 
$$
\norm{h_0-h_1}_2^2 =\norm{f*(g_0-g_1)}_2^2=\sum_S\widehat{(f*(g_0-g_1))}(S)^2=\sum_S\widehat{f}(S)^2\cdot (\widehat{g_0}(S)-\widehat{g_1}(S))^2\,.
$$
This allows us to bound the difference between $h_0$ and $h_1$ by analyzing $\widehat{f}$ and $\widehat{g_0}-\widehat{g_1}$.





\section{Some elementary applications}\label{secsimplefourierapplications}

\subsection{Approximating functions by parities}

It is often useful to approximate complex objects by much simpler ones.
Consider any function $f:\01^n\rightarrow[-1,1]$. 
Suppose there exists a function $p:\01^n\rightarrow[-1,1]$ that has some positive correlation $\inp{f}{p}\geq\eps$ with $f$,
and suppose $p$ is \emph{sparse} in that the set $\mathcal{C}=\{S\mid\widehat{p}(S)\neq 0\}$ of nonzero Fourier
coefficients has at most $c$ elements.
A typical example is where $f$ is a Boolean function and $p$ a low-degree real polynomial approximating $f$, 
since degree-$d$ polynomials have at most $c=\sum_{i=0}^d\binom{n}{i}$ nonzero Fourier coefficients.
Now there exists a parity function that has nontrivial correlation with $f$, as follows:
$$
\eps\leq\inp{f}{p}=\sum_S\widehat{p}(S)\inp{f}{\chi_S}\leq\norm{p}_2\sqrt{\sum_{S\in{\mathcal{C}}}\inp{f}{\chi_S}^2}\,,
$$
where we used Cauchy-Schwarz and Parseval. This implies there exists an $S$ such that either $\chi_S$ 
or its negation has correlation $|\inp{f}{\chi_S}|\geq\eps/(\norm{p}_2\sqrt{c})\geq \eps/\sqrt{c}$ with $f$.


\subsection{List decoding the Hadamard code}\label{sseclistdecoding}

Error-correcting codes are important for storing and sending information in a way that protects against errors.
Consider the Hadamard code: for a given $S\in\01^n$, the codeword $H(S)\in\{\pm 1\}^{2^n}$ 
is defined as the concatenation of $\chi_S(x)$ for all $x$, say ordered in lexicographic order.
This code has a terrible rate: $n$-bit strings are blown up exponentially in size.  
On the other hand, it has excellent distance: any two codewords are at distance exactly $\frac{1}{2}2^n$. 
This means that we can always uniquely decode the initial string $S$ from a given word $w\in\{\pm 1\}^{2^n}$ 
that differs from the codeword $H(S)$ in less than 1/4 of the positions. This is easily phrased in terms of Fourier analysis.
View $w$ as a function $w:\01^n\rightarrow\{\pm 1\}$. Note that $\sum_S\widehat{w}(S)^2=\Exp[w^2]=1$ by Parseval.
Then $w$ has normalized distance $d(w,H(S))=1/2-\eps$ from codeword $H(S)$ if, and only if, $\widehat{w}(S)=2\eps$. 
If the error-rate is less than 1/4 ($\eps>1/4$) then the original string is the \emph{unique} $S$ satisfying $\widehat{w}(S)>1/2$.
(There cannot be two distinct $S$ and $S'$ with Fourier coefficients larger than 1/2, 
since then by the triangle inequality we would have the contradiction $1/2=d(H(S),H(S'))\leq d(H(S),w)+d(w,H(S'))<1/2$.) 

However, as soon as the error-rate is 1/4 or higher, unique decoding is no longer always possible.
For instance the word $w$ that consists of $\frac{3}{4}2^n$ 1s followed by $\frac{1}{4}2^n$ $-1$s could
either have come from $H(0^n)=1^{2^n}$ or from $H(10^{n-1})=1^{2^{n-1}}(-1)^{2^{n-1}}$.
Surprisingly, we can still do something useful even if the error-rate is very close to 1/2, say $1/2-\eps$ for small but positive $\eps$:
we can output a small list of potential strings that contains the original string $S$.
This is known as \emph{list decoding}.
It does not quite tell us what the original string was, but at least narrows it down to a small set of possibilities.
The reason is that not too many codewords $H(S)$ can simultaneously be at 
a distance $\leq 1/2-\eps$ from $w$: such $S$ correspond to Fourier coefficients $\widehat{w}(S)\geq 2\eps$, 
and not too many Fourier coefficients can be that large since their squares sum to~1. 
More formally:
$$
\#\{S: d(H(S),w)\leq 1/2-\eps\} 
\leq \frac{1}{4\eps^2}\sum_{S: d(w,H(S))\leq 1/2-\eps}\widehat{w}(S)^2
\leq \frac{1}{4\eps^2}\sum_S\widehat{w}(S)^2
%= \frac{\Exp[w^2]}{4\eps^2}
= \frac{1}{4\eps^2}\,.
$$
Note that this upper bound on the list size is independent of $n$.
For instance, if we have error-rate 0.49 (so $w$ is close to random), then still the list of
potential codewords has at most $\frac{1}{4(0.01)^2}=2500$ elements.
In fact, Goldreich and Levin~\cite{goldreich&levin} showed that we can efficiently, 
in time $\poly(n,1/\eps)$, \emph{find} this list, given oracle access to the $2^n$-bit string $w$.  
This was the first non-trivial list-decoding algorithm.
Later work by Sudan, Guruswami, and others showed similar results for many codes with good rates,
see for instance~\cite{sudan:listdecodingsurvey,guruswami:alglistdecoding} and the references therein.


\subsection{Learning under the uniform distribution}

A lot of work in the last two decades has used the Fourier transform for \emph{learning} under the uniform distribution.
The idea is that we can learn an unknown function $f:\01^n\rightarrow\R$ by approximating its Fourier coefficients.
Since the Fourier coefficient
$$
\widehat{f}(S)=\Exp[f\cdot\chi_S]
$$
is just an expectation under the uniform distribution on $\01^n$, we can approximate
it from uniformly drawn examples $(x_1,f(x_1)),\ldots,(x_m,f(x_m))$.
The empirical average
$$
\frac{1}{m}\sum_{j=1}^m f(x_j)\cdot \chi_S(x_j)
$$
will converge to the right value $\widehat{f}(S)$ as $m$ grows, and the Chernoff bound tells us how quickly 
this convergence happens.

Suppose we know $f$ is dominated by a few large Fourier coefficients, and we know a not-too-large set containing those coefficients.
A typical case is where $f$ can be approximated by a real polynomial of low degree $d$.  
Then we can approximate those coefficients quickly with a small sample size $m$, and hence learn a good approximation of $f$.
If $\alpha_S$ is our estimate for $\widehat{f}(S)$ and $h=\sum_S\alpha_S\chi_S$ the hypothesis that we output, 
then by Parseval our overall $\ell_2$-error is
$$
\norm{f-h}_2^2=\sum_S(\widehat{f}(S)-\alpha_S)^2\,.
$$
When $f$ has range $\{\pm 1\}$, we can use $\sign(h)$ as our hypothesis for $f$.
We have
$$
\Pr[f(x)\neq \sign(h(x))]=\frac{1}{2^n}\sum_{x:f(x)\neq {\rm sign}(h(x))} 1\leq \frac{1}{2^n}\sum_{x:f(x)\neq {\rm sign}(h(x))} (f(x)-h(x))^2\leq\norm{f-h}_2^2\,.
$$
These ideas have been used for learning constant-depth circuits~\cite{lmn:learnability},
for learning DNF~\cite{mansour:dnfuniform,jackson:dnf,klivans&servedio:dnf,bmos:dnfrandomwalkj}, juntas~\cite{mos:learningjuntas}, 
decision trees~\cite{kushilevitz&mansour:dectrees,odonnell&servedio:montrees},
and others.




\section{The Bonami-Beckner inequality and some of its consequences}\label{secbonamibeckner}

\subsection{Bonami-Beckner and KKL}\label{ssecbonami}

Consider a function $f:\01^n\rightarrow\R$.
Suppose its input $x\in\01^n$ is ``noisy:'' 
a new input $y$ is obtained by flipping, independently,
each bit of $x$ with a fixed probability $\eps\in[0,1]$. 
The resulting noisy version of $f$ is
$$
\widetilde{f}(x)= \Exp_y [f(y)]\,.
$$
Noise has a smoothing effect: sharp peaks in $f$ will be ``smeared out'' over nearby inputs.
Consider for instance a function that is non-zero only on input $0^n$: 
$f(0^n)=1$ and $f(x)=0$ for all $x\neq 0^n$. Then $\widetilde{f}$ is a fairly smooth probability distribution
``around'' $0^n$: $\widetilde{f}(x)=\eps^{|x|}(1-\eps)^{n-|x|}$. If $\eps\in(0,1/2)$ then the maximum 
of $\widetilde{f}$ still occurs at $0^n$, but $\widetilde{f}$ is much less sharply peaked than the original~$f$.

Now consider the linear map that takes $f$ to $\widetilde{f}$.  
Applying this map to the function $f$ defined by $f(x)=(-1)^{x_i}$ gives $\widetilde{f}(x)=(1-\eps)(-1)^{x_i}+\eps(-1)^{1-x_i}=(1-2\eps)(-1)^{x_i}$.
Similarly, applying it to $\chi_S$ gives $(1-2\eps)^{|S|}\chi_S$.
Hence our map is a function $T_\rho$ that merely shrinks the Fourier coefficient $\widehat{f}(S)$ by a factor $\rho^{|S|}$, 
where $\rho=1-2\eps\in[-1,1]$:
$$
\widetilde{f}=T_\rho(f)=\sum_S\rho^{|S|}\widehat{f}(S)\chi_S.
$$
Here we can see the smoothing effect in action: $T_\rho$ attenuates the higher-degree Fourier
coefficients, thus moving $f$ closer to a constant function.
For $\rho<1$, the constant $f$ are the only ones satisfying $T_\rho(f)=f$.

Generalizing the $\ell_2$-norm, for every $p\geq 1$ we define the $p$-norm of a function by 
$$
\norm{f}_p=\left(\frac{1}{2^n}\sum_x |f(x)|^p\right)^{1/p}.
$$
One can show this is monotone non-decreasing in~$p$.
Since $T_\rho(f)$ is an average of functions that all have the same $p$-norm as $f$, 
the triangle inequality immediately implies that $T_\rho$ is a contraction: 
for every $p\geq 1$ we have $\norm{T_\rho (f)}_p\leq\norm{f}_p$.
The \emph{Bonami-Beckner Hypercontractive Inequality}~\cite{Bon70,Gross75,Bec75} 
says that this inequality remains true even if we increase the left-hand side by going to a somewhat higher $q$-norm:

\begin{theorem}[Bonami-Beckner]\label{thbonamibeckner}
If $1\leq p\leq q$ and $0\leq\rho\leq\sqrt{(p-1)/(q-1)}$, then
$$
\norm{T_\rho (f)}_q\leq\norm{f}_p\,.
$$
\end{theorem}

This inequality is a crucial tool in most of the more advanced applications of Fourier analysis on the Boolean cube.
The case $\rho=\sqrt{(p-1)/(q-1)}$ is the strongest case, and implies all others by monotonicity of the $p$-norm.
Its proof is by induction on $n$. The base case ($n=1$) is actually the harder part of the induction.
We refer to Lecture~16 of~\cite{odonnell:notes} for a proof as well as some background and history.
Chapter~5 of the book of Janson~\cite{janson:gaussian} gives a more general treatment of hypercontractivity.
  
For us the most interesting cases are when either $p$ or $q$ equal~2,
since Parseval allows us to rewrite the 2-norm in terms of Fourier coefficients.
This leads to interesting statements about the relations between various norms of $f$.
For instance, suppose the degree of $f$ is at most $d$.  Then for all $p\in[1,2]$, and using $q=2$ and $\rho=\sqrt{p-1}$, we have
$$
(p-1)^d\norm{f}_2^2=(p-1)^d\sum_S\widehat{f}(S)^2\leq \sum_S(p-1)^{|S|}\widehat{f}(S)^2=\norm{T_{\sqrt{p-1}}(f)}_2^2\leq\norm{f}_p^2\,.
$$
Hence the $p$-norm of a low-degree function cannot be much smaller than its 2-norm.
A similar argument gives $\norm{f}_q^2\leq (q-1)^d\norm{f}_2^2$ for all $q\geq 2$.

In general, with $q=2$, $p\in[1,2]$, and $\rho=\sqrt{p-1}$, \thmref{thbonamibeckner} becomes
\begin{equation}\label{eqbbforq2}
\sum_S (p-1)^{|S|}\widehat{f}(S)^2=\norm{T_\rho(f)}_2^2\leq \norm{f}_p^2=\left(\frac{1}{2^n}\sum_x|f(x)|^p\right)^{2/p}.
\end{equation}
This gives an upper bound on the squared Fourier coefficients of $f$, in a way
that gives most weight to the low-degree coefficients: each coefficient is ``weighed down'' by~$(p-1)^{|S|}$.% 
\footnote{Recently Eq.~\eqref{eqbbforq2} was generalized from real-valued functions to \emph{matrix-valued} functions~\cite{brw:hypercontractive}.}
An important special case of Eq.~\eqref{eqbbforq2} is where $f$ has range $\{-1,0,1\}$.
This occurs for instance if $f$ is a Boolean function or the difference of two Boolean functions.  
In that case we have $\norm{f}_p^p=\Pr[f\neq 0]$ for any $p$.
Applying Eq.~\eqref{eqbbforq2} with $p=1+\delta$ gives the following \emph{KKL Inequality}, after Kahn, Kalai, and Linial~\cite{kkl:influence}.

\begin{corollary}[KKL]
For every $\delta\in[0,1]$ and $f:\01^n\rightarrow\{-1,0,1\}$, we have 
$$
\sum_S\delta^{|S|}\widehat{f}(S)^2 \leq (\Pr[f\neq 0])^{2/(1+\delta)}.
$$
\end{corollary}

Informally, with $\delta<1$ the left-hand side is dominated by the Fourier coefficients of low degree 
(\ie, those where $|S|$ is small). The right-hand side is smaller than the total ``Fourier weight'' $\sum_S\widehat{f}(S)^2=\Pr[f\neq 0]$
by a power $2/(1+\delta)>1$. Hence the inequality says that a $\{-1,0,1\}$-valued function with small support 
cannot have too much of its Fourier weight on low degrees.




\subsection{Random parities over a fixed set}\label{ssecrandomparities}

An application for which KKL seems to be almost tailor-made, is to
bound the expected bias of $k$-bit parities over a set $A\subseteq\01^n$.
Suppose we pick a set $S\subseteq [n]$ of $k$ indices uniformly at random, 
and consider the parity of the $k$-bit substring induced by $S$ and a uniformly random $x\in A$.
Intuitively, if $A$ is large then we expect that for most $S$, the bias $\beta_S$ of this parity to be small:
the number of $x\in A$ with $\chi_S(x)=1$ should be roughly the same as with $\chi_S(x)=-1$.
This setting is relevant to cryptography.  Suppose we have an $n$-bit string $x$ about which 
our adversary has some limited knowledge: he only knows that $x$ is uniformly distributed over some fairly large set~$A$.
Then our adversary will be unable to predict most parities of selected bits from $x$, and we 
can use such parities to obtain bits that are essentially unknown to him. We ourselves do not need 
to know $A$ for this; we only need to know a lower bound on its size, \ie, an upper bound on the adversary's knowledge.

The intuition that large $A$ leads to small biases is justified by the KKL Inequality.%
\footnote{To the best of our knowledge, the bound below was first shown by Talagrand~\cite[Eq.~(2.9)]{talagrand:increasingsets} for $k=2$,
using a large deviation inequality instead of hypercontractivity, and for general $k$ in~\cite{gkkrw:1way} using the KKL Inequality.
\cite{gkkrw:1way} used it to prove lower bounds for communication complexity.}
Note the connection between biases and Fourier coefficients: with $f$ the characteristic function of $A$, we have
$$
\beta_S=\Exp_{x\in A}[\chi_S(x)]=\frac{1}{|A|}\sum_{x\in A}\chi_S(x)=\frac{1}{|A|}\sum_{x\in\01^n}f(x)\chi_S(x)=\frac{2^n}{|A|}\widehat{f}(S)\,.
$$
Applying the KKL Inequality, for any $\delta\in[0,1]$ we can bound the sum of \emph{squared} biases by
$$
\sum_{S\in\binom{[n]}{k}}\beta_S^2=\frac{2^{2n}}{|A|^2}\sum_{S\in{\binom{[n]}{k}}}\widehat{f}(S)^2
\leq \frac{2^{2n}}{\delta^k |A|^2}\left(\frac{|A|}{2^n}\right)^{2/(1+\delta)}
\leq \frac{1}{\delta^k}\left(\frac{2^n}{|A|}\right)^{2\delta}.
$$
By differentiating, one can show that $\delta= {k}/[{2\ln(2^n/|A|)]}$ minimizes the right-hand side (assume $k\leq 2\ln(2^n/|A|)$ to ensure $\delta\in[0,1]$).
This gives
\begin{equation}
\Exp_S[\beta_S^2]=\frac{1}{\binom{n}{k}}\sum_{S\in\binom{[n]}{k}}\beta_S^2=O\left(\frac{\log(2^n/|A|)}{n}\right)^k. \label{eqbiasupperbound}
\end{equation}
The following example shows this bound is essentially tight, and hence the KKL Inequality is tight as well. 
Let $A=0^c\times\01^{n-c}$ consist of all $2^{n-c}$ strings starting with $c$ zeroes.
Then $\beta_S=1$ if $S\subseteq[c]$, and $\beta_S=0$ otherwise. The fraction of sets $S\in\binom{[n]}{k}$ satisfying $S\subseteq[c]$
is $\binom{c}{k}/\binom{n}{k}=\Omega(c/n)^k$. Hence $\Exp_S[\beta_S^2]=\Omega(c/n)^k=\Omega(\log(2^n/|A|)/n)^k$,
matching the upper bound of Eq.~\eqref{eqbiasupperbound}.

\subsection{Influences of variables}\label{ssecmaxinfluence}

Suppose we have $n$ players, and we have a function $f:\01^n\rightarrow\01$ where player~$i$ controls the bit $x_i$.
If $f$ is balanced (meaning exactly half of the $2^n$ inputs $x$ yield $f(x)=1$),
then we can use it to implement a \emph{collective coin flipping scheme}:
let each player pick their bit $x_i$ randomly and use $f(x)$ as the value of the coin flip.
If all players indeed follow this protocol, the result is a fair coin flip.
However, in order for this to be secure, small collusions of cheating players who can see 
the bits of the honest players should not be able to influence the function's output value too much.

Formally, the \emph{influence} of variable $i\in[n]$ on $f$ is defined as
$$
\Inf_i(f)=\Pr[f(x)\neq f(x\oplus e_i)]\,,
$$
where the probability is over uniform $x\in\01^n$, and $x\oplus e_i$ is $x$ with the $i$th bit flipped.
This measures the probability (over random bits for all other players) that player~$i$ can determine the function value.
One can generalize this definition to the influence of a \emph{set} $S$ of players in the obvious way:
$\Inf_S(f)$ is the probability that the function is non-constant when all variables outside of $S$ are set randomly.
Two extreme cases are the constant function (where $\Inf_i(f)=0$ for all $i$), and the parity function (where $\Inf_i(f)=1$ for all $i$). 
For the dictator function $f(x)=x_i$, the $i$th variable has influence 1 while all other influences are 0.
Another important example is the $n$-bit majority function, which is 1 if more than half of its input bits are 1, and which is 0 otherwise.
Here each variable has influence $\Theta(1/\sqrt{n})$, because the probability that the other 
$n-1$ bits are set such that $x_i$ determines the majority value is exactly $\binom{n-1}{\floor{n/2}}/2^{n-1}$.
Moreover, any set $S$ of, say, $10\sqrt{n}$ variables will with high probability be able to 
``tip the balance'' and determine the majority value when the other $n-10\sqrt{n}$ input bits are set randomly,
hence $\Inf_S(f)\approx 1$.

Can we find balanced functions where the influences of the variables are much smaller, ideally $O(1/n)$?
Ben-Or and Linial~\cite{benor&linial:coinflippingj} showed that the ``tribes'' function 
(an OR-AND tree with bottom fan-out about $\log n-\log\log n$) is a balanced function where 
every variable has influence $\Theta(\log(n)/n)$.
Kahn, Kalai, and Linial~\cite{kkl:influence} later showed that this is essentially optimal: for every 
Boolean function $f$ that is balanced or close to balanced, at least one of its variables has influence $\Omega(\log(n)/n)$. 
With some extra work (which we won't detail here), this implies the existence of a set of only
$O(n/\log n)$ variables that together determine the function value for almost all settings of the other variables.
Hence we cannot hope to use such functions for collective coin flipping protocols that 
are secure against a constant fraction of cheating players: 
a small set of $O(n/\log n)$ colluding players can already control the outcome with high probability.

The KKL result was one of the first major applications of Fourier analysis to Boolean functions.  
We will prove a slightly stronger result here due to Talagrand~\cite{talagrand:russo}.
Let $\Var[f]=\Exp[f^2]-\Exp[f]^2$ be the \emph{variance} of~$f$. By Parseval, this equals
$\norm{f}_2^2-\widehat{f}(\emptyset)^2=\sum_{S\neq\emptyset}\widehat{f}(S)^2$. 
Consider a function $f:\01^n\rightarrow\01$.
Assume that no variable has influence exactly 0 or 1 (influence-0 variables are irrelevant anyway,
and influence-1 variables can be ``factored'' out of the function).
Then we have
\begin{equation}\label{eqtalagrand}
\sum_{i=1}^n\frac{\Inf_i(f)}{\log(1/\Inf_i(f))}=\Omega(\Var[f]).
\end{equation}
The KKL result follows immediately from this: if $f$ is close to balanced then $\Var[f]=\Omega(1)$.
Hence there is an $i$ such that $\Inf_i(f)/\log(1/\Inf_i(f))=\Omega(1/n)$, which implies $\Inf_i(f)=\Omega(\log(n)/n)$.

The proof of Eq.~\eqref{eqtalagrand} is based on the following technical lemma, which uses Bonami-Beckner.

\begin{lemma}\label{lemtalagrand}
If $g:\01^n\rightarrow\mathbb{R}$ satisfies $\norm{g}_{3/2}\neq\norm{g}_2$, then
$$
\sum_{S\neq\emptyset}\frac{\widehat{g}(S)^2}{|S|}\leq \frac{2.5\,\norm{g}_2^2}{\log(\norm{g}_2/\norm{g}_{3/2})}\,.
$$
\end{lemma}

\begin{proof}
Using \thmref{thbonamibeckner} with $q=2$ and $p=1+\rho^2=3/2$ we get for every integer $k$
$$
\sum_{S:|S|=k}\widehat{g}(S)^2\leq 2^k\sum_S 2^{-|S|}\widehat{g}(S)^2=2^k\norm{T_{\sqrt{1/2}}(g)}_2^2\leq 2^k\norm{g}_{3/2}^2\,.
$$
For every integer $m$ we have (using $\sum_{k=1}^m 2^k/k\leq 4\cdot 2^m/(m+1)$, which is easily proved by induction):
$$
\sum_{S\neq\emptyset}\frac{\widehat{g}(S)^2}{|S|} 
 = \sum_{k=1}^m\sum_{S:|S|=k}\frac{\widehat{g}(S)^2}{k} + \sum_{S:|S|>m}\frac{\widehat{g}(S)^2}{|S|}
  \leq  \sum_{k=1}^m\frac{2^k\norm{g}_{3/2}^2}{k} + \sum_{S:|S|>m}\frac{\widehat{g}(S)^2}{m+1}
  \leq  \frac{4\cdot 2^m \norm{g}_{3/2}^2+\norm{g}_2^2}{m+1}
$$
Choose $m$ the largest integer satisfying $2^m\norm{g}_{3/2}^2\leq\norm{g}_2^2$.
Then $m+1>2\log(\norm{g}_2/\norm{g}_{3/2})$, and
$$
\sum_{S\neq\emptyset}\frac{\widehat{g}(S)^2}{|S|} \leq \frac{5\,\norm{g}_2^2}{m+1}\leq \frac{2.5\,\norm{g}_2^2}{\log(\norm{g}_2/\norm{g}_{3/2})}\,.
$$
%Finally, we have $\norm{g}_{3/2}^3\leq\norm{g}_1\norm{g}_2^2$ by Cauchy-Schwarz.
%This implies $\norm{g}_2/\norm{g}_1\leq (\norm{g}_2/\norm{g}_{3/2})^3$ and concludes the proof
%(note that $\norm{g}_1\neq\norm{g}_2$ implies that these norms are all non-zero).
\end{proof}

Now consider a variable $i$ and define $g(x)=f(x)-f(x\oplus e_i)$. 
Then $g(x)=0$ if $f(x)=f(x\oplus e_i)$, and $g(x)\in\{\pm 1\}$ otherwise.
Hence $\norm{g}_2^2=\norm{g}_{3/2}^{3/2}=\Inf_i(f)\in(0,1)$, and $\norm{g}_2/\norm{g}_{3/2}=\Inf_i(f)^{-1/6}$. 
The Fourier coefficients of $g$ are closely related to those of~$f$:
\begin{equation}\label{eqfourierdouble}
\widehat{g}(S)= \begin{cases}
2\widehat{f}(S) & \mbox{ if $i\in S$,}\\
0               & \text{otherwise.}
\end{cases}
\end{equation}
Applying \lemref{lemtalagrand} to $g$ gives
$$
\sum_{S:i\in S}\frac{4\widehat{f}(S)^2}{|S|}=\sum_S\frac{\widehat{g}(S)^2}{|S|}\leq \frac{2.5\,\norm{g}_2^2}{\log(\norm{g}_2/\norm{g}_{3/2})}=\frac{15\,\Inf_i(f)}{\log(1/\Inf_i(f))}\,.
$$
Summing over all $i$ gives Talagrand's result:
$$
4\Var[f]=4\sum_{S\neq 0}\widehat{f}(S)^2=\sum_{i=1}^n \sum_{S:i\in S}\frac{4\widehat{f}(S)^2}{|S|}\leq\sum_{i=1}^n \frac{15\,\Inf_i(f)}{\log(1/\Inf_i(f))}\,.
$$

\paragraph{Subsequent work.}
The subsequent ``BKKKL'' paper~\cite{bkkkl:influence} generalized the KKL result to the case of functions $f:[0,1]^n\rightarrow\01$
with real-valued input, with uniform measure on each real-valued variable $x_i$.
See Friedgut~\cite{friedgut:bkkkl} for some simplifications and corrections of this.
%Talagrand~\cite{talagrand:russo} strengthened the KKL result to $\sum_{i=1}^n\Inf_i(f)=\Omega(\log(1/\max_i\Inf_i(f)))$.
A recent related result is that any near-balanced Boolean function with a depth-$d$ decision tree
has a variable with influence $\Omega(1/d)$~\cite{dsss:dectreeinfluence}.


\subsection{The relation between influences, sensitivity, and degree}\label{ssecdegree}

In this section we relate influences to degree and sensitivity, both of which 
are important measures of the complexity of Boolean functions.\footnote{See the survey~\cite{buhrman&wolf:dectreesurvey}. 
Other Fourier-based results on polynomial degrees are in~\cite{odonnell&servedio:extremal,servedio:lowweightj,bvw:smallbias}.
This section does not need the Bonami-Beckner or KKL Inequalities, but is placed after \secref{ssecmaxinfluence} because 
it considers the influences defined there.}
The \emph{sensitivity} of a function $f:\01^n\rightarrow\01$ on input $x$ is
$$
s_x(f)=|\{i\mid f(x)\neq f(x\oplus e_i)\}|
$$
and the \emph{average sensitivity} of $f$ is
$$
\overline{s}(f)=\frac{1}{2^n}\sum_{x\in\01^n}s_x(f)\,.
$$
By linearity of expectation, average sensitivity equals the total influence:
\begin{equation}\label{eqavsinfl}
\overline{s}(f)=\sum_{i=1}^n\Inf_i(f)\,.
\end{equation}
Here we give a relation between degree and sensitivity due to Shi~\cite{shi:lowerbound}: 
average sensitivity lower bounds the degree of approximating polynomials.
Suppose a degree-$d$ $n$-variate real polynomial $p:\01^n\rightarrow[0,1]$ approximates $f:\01^n\rightarrow\01$, 
in the sense that there is an $\eps\in[0,1/2)$ such that $|f(x)-p(x)|\leq\eps$ for every $x\in\01^n$.
Let $q$ be the degree-$d$ polynomial $1-2p$. This has range $[-1,1]$, hence $\sum_S\widehat{q}(S)^2=\norm{q}_2^2\leq 1$. 
Note that $q(x)\in[-1,-1+2\eps]$ if $f(x)=1$, and $q(x)\in[1-2\eps,1]$ if $f(x)=0$.
Consider the function $q^{(i)}(x)=q(x)-q(x\oplus e_i)$.
Using Parseval and the analogue of Eq.~\eqref{eqfourierdouble}, we have
$$
(2-4\eps)^2\Inf_i(f)\leq\Exp[(q^{(i)})^2]=\sum_S\widehat{q^{(i)}}(S)^2=4\sum_{S:i\in S}\widehat{q}(S)^2.
$$
Dividing by 4 and summing over all $i$ gives the lower bound on the degree:
$$
(1-2\eps)^2\overline{s}(f)=(1-2\eps)^2\sum_{i=1}^n\Inf_i(f)\leq\sum_{i=1}^n\sum_{S:i\in S}\widehat{q}(S)^2=\sum_{S}|S|\widehat{q}(S)^2\leq d\sum_S\widehat{q}(S)^2\leq d\,.
$$
A random Boolean function has $\overline{s}(f)\approx n/2$ and $\eps$-approximate degree at least $n/2-O(\sqrt{n})$~\cite{ambainis:aa}
(for fixed~$\eps$), hence this bound is optimal up to constant factors for almost all $n$-bit functions.

Another Fourier-based lower bound on the degree is due to Nisan and Szegedy~\cite{nisan&szegedy:degree}.
Suppose $f:\01^n\rightarrow\01$ depends on all of its $n$ variables (equivalently, each variable has positive influence). 
Consider $f^{(i)}(x)=f(x)-f(x\oplus e_i)$.
This is an $n$-variate polynomial of degree $d\leq \deg(f)$, and it is non-constant because $f$ depends on $x_i$. 
It is well known that such a polynomial is non-zero on at least a $2^{-d}$-fraction of its inputs.%
\footnote{This is a basic and well known property of 
Reed-Muller error-correcting codes~\cite[p.~375]{MacWilliamsS77}.
In the computer science literature this fact is usually called the 
Schwartz-Zippel Lemma~\cite{schwartz:probabilistic,zippel:probabilistic}.} 
Hence 
$$
\Inf_i(f)=\Pr[f^{(i)}\neq 0]\geq 2^{-\deg(f)}
$$
for each $i$.  Summing over~$i$ we get
$$
\frac{n}{2^{\deg(f)}}\leq \sum_{i=1}^n\Inf_i(f)=\sum_{i=1}^n\sum_S\widehat{f^{(i)}}(S)^2=4\sum_S|S|\widehat{f}(S)^2\leq 4\, \deg(f)\sum_{S}\widehat{f}(S)^2\leq 4\, \deg(f)\,.
$$
This implies the bound from~\cite{nisan&szegedy:degree}:
$$
\deg(f)\geq\log(n)-O(\log\log n)
$$ 
for every Boolean function $f$ that depends on $n$ variables. 
As Nisan and Szegedy observed, the ``address function'' shows that
this bound is tight up to the $O(\log\log n)$ term. This function takes an input $x_1\ldots x_m y_0\ldots y_{2^m-1}$ 
of $n=m+2^m$ bits, and outputs $y_i$ where $i$ is the number whose binary representation is $x_1\ldots x_m$.
The function depends on all $n$ variables.
It is represented by 
$$
\sum_{i\in\01^m} y_i\prod_{j:i_j=1}x_j\prod_{j:i_j=0}(1-x_j)
$$
and hence has degree $m+1\leq \log n + 1$.



\section{A guide to literature}\label{seclastsection}

The examples given above illustrate the usefulness of Fourier analysis on the Boolean cube,
but they barely scratch the surface of the rich set of actual and potential applications.
In this last section we give pointers to the other main areas of application in computer science. 

\paragraph{PCPs and hardness of approximation.}
Possibly the most important application of Fourier analysis in theoretical computer science
is its use in designing and analyzing \emph{Probabilistically Checkable Proofs}.
These are encodings of witnesses for NP-like problems that can be verified probabilistically 
while querying only a small number of their bits. The famous PCP Theorem~\cite{almss:pcp,dinur:pcp} 
says that a language is in NP if, and only if, it has witnesses that can be verified probabilistically 
using only $O(\log n)$ bits of randomness and a \emph{constant} number of queries to bits of the witness.
Some of the most efficient PCPs are based on Fourier analysis, H{\aa}stad's 3-query PCP being a prime example~\cite{hastad:optimalj}.
Based on these PCPs, one can show NP-hardness results for approximations to many optimization problems,
such as finding a maximal clique in a graph or the maximal number of satisfied clauses in a given CNF formula.
Chapters~11 and~22 of the book by Arora and Barak~\cite{arora&barak:cc} give a good introduction to this material.

\begin{sloppypar}
A recent development is the use of the ``Unique Games Conjecture.'' This conjecture, due to Khot~\cite{khot:ugc}, 
says that it is hard to approximate the maximal number of satisfied constraints in problems with only two variables 
per constraint, where the value of either variable in a constraint determines the value of the other
(the variables are over a sufficiently large but constant domain).
Assuming this, one can prove essentially optimal inapproximability results for problems like 
max-cut~\cite{kkmo:maxcutj}, vertex cover~\cite{khot&regev:vertexcover}, 
and others~\cite{ckkrs:cut,khot&vishnoi:cutproblems,dmr:coloring,khot&odonnell:maxcutgain,raghavendra:csp},
which so far resisted the more standard inapproximability approach via PCPs.
Again, Fourier techniques are often essential in the analysis.
For instance, one of the main planks of the max-cut result is the ``Majority Is Stablest'' Theorem.
This was conjectured in a first version of~\cite{kkmo:maxcutj} and proved in~\cite{moo:noisestability}.
It says that among all balanced Boolean functions where every variable has low influence, 
the majority function has the maximal correlation between $f$ and its noisy version $\tilde{f}=T_\rho(f)$ 
(as defined in \secref{ssecbonami}).
\end{sloppypar}

\paragraph{Threshold phenomena.}
A \emph{threshold phenomenon} occurs if certain properties of a system change sharply in response to a small change
of an underlying parameter which is close to a specific value (the ``threshold'').
A typical example in nature is water, which is frozen if the temperature-parameter 
is just below 0$^\circ$C and liquid if the temperature is just above 0$^\circ$C.
In mathematics, such phenomena occur for instance in random graphs.
Let $G(n,p)$ denote an undirected graph on $n$ vertices, where each edge is included with probability $p$ 
(independent of the other edges). Erd\H{o}s and R\'enyi~\cite{erdos&renyi:randomgraphs} introduced this model and showed a sharp threshold
for connectivity: if $p$ is slightly below $(\log n)/n$ then the probability of $G(n,p)$ being connected tends to 0 with $n$,
while if $p$ is slightly larger than $(\log n)/n$ then this probability tends to 1.
Friedgut and Kalai~\cite{friedgut&kalai:sharp} later showed that \emph{every} monotone graph property has a sharp threshold.

Threshold phenomena occur also in complexity theory.  For instance, if one picks a random 3-SAT formula with $n$ variables and $m=cn$ clauses,
then for $c<4.2$ (roughly\footnote{Actually this value of 4.2 is a numerical estimate; proven upper and lower bounds on this number are far from tight. 
We refer to Part~3 of~\cite{ccandphysics} for details.}), the formula is most probably satisfiable, 
while for $c>4.2$ the formula is most probably unsatisfiable.
Similarly, one can view tight results on hardness of approximation as threshold phenomena:
for many NP-hard optimization problems, there exists a constant $c$ such that approximating 
the optimal value up to factor $c$ can be done in polynomial time, while approximating 
it to within a slightly better factor is NP-hard (or Unique-Games hard).
Kalai and Safra~\cite{kalai&safra:threshold} give a very interesting survey of these phenomena,
showing how influences and Fourier techniques are central to their analysis. Often these techniques
apply to the generalized setting where each input bit is~1 with probability~$p$.

\paragraph{Social choice theory.}
If $n$ people have to decide between two alternatives then they can use majority voting, 
which has all the properties one expects of a reasonable voting scheme.
However, as soon as they have to choose between three or more alternatives, 
Arrow's Theorem~\cite{arrow:difficulty} says that no ``ideal'' voting scheme exists.
Strong quantitative versions of this theorem can be obtained quite easily using Fourier techniques.
The surveys by Kalai~\cite{kalai:socialchoice} and O'Donnell~\cite{odonnell:survey} are 
excellent starting points for such connections between Fourier analysis and social choice theory.
A very recent related result is~\cite{fkn:elections}.

\paragraph{When are functions close to juntas?}
Recall that a $k$-junta is a function on $\01^n$ that depends on 
at most $k$ of its variables.
Friedgut~\cite{friedgut:fewcoor} showed that if the average 
sensitivity (a.\,k.\,a.~total influence) of a Boolean function $f$ is $I$
then $f$ is close to another Boolean function that is a $2^{O(I)}$-junta.
The ``address function'' from \secref{ssecdegree} shows the exponential 
is necessary:
it has average sensitivity $O(\log n)$ but cannot be approximated well 
by a Boolean function depending on only $o(n)$ variables.
Friedgut et al.~\cite{fkn:firsttwolevels} show that if the Fourier coefficients of degrees 0 and 1 have most of
the total weight, then $f$ is close to a 1-junta (\ie, a dictator or its negation).
Bourgain~\cite{bourgain:fourierdistribution} proved that the weight on higher-degree Fourier coefficients of 
a balanced Boolean function cannot decay too fast unless $f$ is close to a junta, and Dinur et al.~\cite{dfko:fouriertails} 
analyzed the same phenomenon for \emph{bounded}---but not necessarily Boolean---functions on the Boolean cube.

\paragraph{Other applications.}
Some results in the area of \emph{property testing} are based on Fourier analysis. 
Examples are the algorithm by Fischer et al.~\cite{fkrss:juntas} for testing if a Boolean function is close to or far from a $k$-junta, 
and the one by Alon et al.~\cite{aak:testingkwise} for testing if a distribution is close to or far from (almost) $k$-wise independence.
The above-mentioned work on PCPs also falls in this category, since one is basically testing whether a given witness is close to a valid proof or not.
In addition to the list-decoding example from \secref{sseclistdecoding}, there have been a number of 
other applications of Fourier analysis in coding theory, see for instance Section~4.3 of Linial's course notes (mentioned below) 
and Navon and Samorodnitsky~\cite{navon&samorodnitsky:delsarte}.
Fourier analysis has also been used for lower bounds on various kinds of communication complexity~\cite{raz:ccfourier,klauck:qcclowerj,gkkrw:1way,sherstov:dualpoly}, and for analysis of low-distortion embeddings of one metric space into another~\cite{LeeNaor04,khot&vishnoi:cutproblems}.

\paragraph{Other expository papers and courses.}
Several more extensive surveys on Fourier analysis of Boolean functions exist in the literature.
The early one by Bernasconi, Codenotti, and Simon~\cite{bcs:fourier} 
describes the main applications up to~1997.
\v{S}tefankovi\v{c}'s MSc thesis~\cite{stefankovic:thesis} is 
geared towards general applications of Fourier analysis in computer science, 
often over groups other than the Boolean cube.
The survey by Kalai and Safra~\cite{kalai&safra:threshold} 
%% is geared towards 
concentrates on threshold phenomena. %% LB
The very recent survey by O'Donnell~\cite{odonnell:survey} 
focuses on topics related to voting and hardness of approximation,
and also tries to demystify the Bonami-Beckner Inequality by 
presenting it as a generalization of
the Hoeffding-Chernoff bounds to higher-degree functions. 
Finally, let us point to the notes of a number of recent courses, 
which contain a wealth of additional material:
\begin{quote}
Irit Dinur and Ehud Friedgut: \url{http://www.cs.huji.ac.il/~analyt}\\
Subhash Khot: \url{http://www.cc.gatech.edu/~khot/Fourier.htm}\\
Guy Kindler: \url{http://dimacs.rutgers.edu/~gkindler/boolean-course}\\
Nati Linial: \url{http://www.cs.huji.ac.il/~nati/PAPERS/uw}\\
Elchanan Mossel: \url{http://www.stat.berkeley.edu/\%7Emossel/teach/206af05}\\
Ryan O'Donnell: \url{http://www.cs.cmu.edu/~odonnell/boolean-analysis}\\
Oded Regev: \url{http://www.cs.tau.ac.il/~odedr/teaching/analysis\_fall\_2007}
\end{quote}

\subsubsection*{Acknowledgments}
Thanks to David Garc\'{\i}a Soriano, Elena Grigorescu, Peter Harremo\"{e}s, Oded Regev, Nitin Saxena, Ben Toner, and Stephanie Wehner 
for useful comments and pointers. Also thanks to the anonymous ToC referees for many extremely helpful recommendations.

\bibliographystyle{tocplain}
\bibliography{gs001}

\begin{tocauthors}
\begin{tocinfo}[ronald]
Ronald de Wolf\\ %%~\tocabout\\
senior researcher\\
CWI Amsterdam\\
rdewolf\tocat{}cwi\tocdot{}nl \\
\url{http://homepages.cwi.nl/~rdewolf}
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
\begin{tocabout}[ronald]
{\sc Ronald de Wolf} graduated from the 
\href{http://www.science.uva.nl}{University of Amsterdam}
and \href{http://www.cwi.nl}{CWI} in 2001.  His advisors
were \href{http://homepages.cwi.nl/~buhrman}{Harry Buhrman}
and  \href{http://homepages.cwi.nl/~paulv}{Paul Vit\'{a}nyi}.
His CS interests include quantum computing, 
complexity theory, and learning theory. 
More details can be found on his 
\href{http://homepages.cwi.nl/~rdewolf}{homepage}.
He also holds a degree in philosophy, 
and enjoys classical music and literature.
\end{tocabout}
\end{tocaboutauthors}

\end{document}

