Theory of Computing Library Graduate Surveys, TCGS 1 (2008), pp. 1–20 www.theoryofcomputing.org

A Brief Introduction to Fourier Analysis on the Boolean Cube

Ronald de Wolf^{∗}

Received: June 30, 2007; revised: August 5, 2008; published: September 25, 2008.

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.

ACM Classification: F.0, F.2

AMS Classification: 42-02, 68-02, 68Q17, 68Q25, 68Q32

Key words and phrases: Fourier analysis, Boolean functions, coding theory, learning theory, hypercontractive inequality, influence of variables, polynomial

1 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 χ_{y}(x) = e^{2πixy/n} or (in the real case) sines and cosines.

Ronald de Wolf

In the study of functions of n Boolean variables, however, the most natural Fourier transform to consider is the one over the Abelian group ℤ_{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 (Section 2) and to illustrate and motivate them by means of a few relatively simple but elegant applications from diverse areas (Section 3 and Section 4). 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 Section 5 we give pointers for further reading.

∗CWI Amsterdam. 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.

Authors retain copyright to their work and grant Theory of Computing unlimited rights to publish the work electronically and in hard copy. Use of the work is permitted as long as the author(s) and the journal are properly acknowledged. For the detailed copyright statement, see http://theoryofcomputing.org/copyright.html.

\begin{matrix}c \\ ◯ \end{matrix} 2008 Ronald de Wolf

2 Definitions and basic properties

2.1 The vector space of functions on the Boolean cube

Consider the 2^{n}-dimensional vector space of all functions f : {0,1}^{n} → ℝ. We define an inner product on this space by

⟨f,g⟩ = \frac{1}{2^{n}} ∑_{x∈\{0,1\}^{n}}f(x)g(x) = 𝔼[f · g],

where the latter expectation is taken uniformly over all x ∈ {0,1}^{n}. This defines the ℓ_{2}-norm

||f||_{2} = \sqrt{⟨f,f⟩} = \sqrt{𝔼[f^{2}]}.

2.2 The Fourier transform

It will be convenient to identify a set S ⊆ [n] = {1,...,n} with its characteristic vector S ∈ {0,1}^{n}. For example for S = {1,3} ⊆ [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 ⊆ [n], define a function χ_{S}: {0,1}^{n} → {±1} by

χ_{S}(x) = (−1)^{S·x},

where S · x = ∑ _{i=1}^{n} S_{i}x_{i} = ∑_{i∈S} x_{i}. It is easy to see that

⟨χ_{S},χ_{T}⟩ = δ_{ST}= \{ \begin{matrix}1 & if S = T \\ 0 & if S ≠ T \end{matrix} ,

hence the set of all χ_{S} is an orthonormal basis (called the Fourier basis) for the space of all real-valued functions on {0,1}^{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: χ_{S}(x) = −1 if the number of S-variables having value 1 in the input x is odd, and χ_{S}(x) = 1 if that number is even.

For any f : {0,1}^{n} → ℝ we can define another function f̂: {0,1}^{n} → ℝ by

f̂(S) = ⟨f,χ_{S}⟩ = 𝔼[f · χ_{S}].

A Brief Introduction to Fourier Analysis on the Boolean Cube

The linear map

ℱ: f ↦ f̂

is called the Fourier transform. The function f̂ = ℱ(f) is the Fourier transform of f, and f̂(S) is the Fourier coefficient of f at S. This f̂(S) may be viewed as a measure of the correlation between f and χ_{S}. The set of Fourier coefficients is also called the Fourier spectrum of f. Since the χ_{S} form an orthonormal basis, the relation between f and f̂ is

f = ∑_{S} f̂(S)χ_{S}.  (2.1)

Note that f(∅) = ∑_{S} f̂(S) is the sum of all Fourier coefficients, while f̂(∅) = 𝔼[f] is the average function value. A function is constant if, and only if, f̂(S) = 0 for all S ≠ ∅.

The degree of f is deg(f) = max{|S| | f̂(S) ≠ 0}. In particular the degree of the basis function χ_{S} is |S|, the number of variables it depends on. Since (−1)^{x_{i}} = 1 − 2x_{i}, the Fourier expansion Eq. (2.1) represents f as an n-variate polynomial over the real numbers, of degree deg(f).

Let us consider some simple examples. If f = χ_{S} then f̂(S) = 1 while all other Fourier coefficients are 0. If f(x) = ∑_{i∈S} x_{i} mod2 is a parity function in the usual 0/1 notation, then f̂(∅) = 1/2 and f̂(S) = −1/2; all other coefficients are 0. The special case where S = {i} (i. e., f(x) = x_{i}) is known as a dictator function, since its value is determined by only one variable. A k-junta is a function depending on at most k variables; equivalently, there is a set J ⊆ [n] of size k such that f̂(S) = 0 whenever S ⊈ J. Finally, if we pick a function f : {0,1}^{n} → {±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 χ_{S} form an orthonormal basis, we immediately get the following equality:

⟨f,g⟩ = ∑_{S,T}f̂(S)ĝ(T)⟨χ_{S},χ_{T}⟩ = ∑_{S} f̂(S)ĝ(S).

In particular, with f = g we obtain Parseval’s Identity:

||f||_{2}^{2} = ∑_{S} f̂(S)^{2}.

This also implies

||f − g||_{2}^{2} = ∑_{S} (f̂(S) − ĝ(S))^{2}.

As an example, suppose f is a probability distribution. Then we can analyze the ℓ_{2}-distance between f and the uniform distribution g(x) = 1/2^{n} as follows:

||f − g||_{2}^{2} = ∑_{S} (f̂(S) − ĝ(S))^{2} = ∑_{S≠∅} f̂(S)^{2},

where we used f̂(∅) = ĝ(∅) = 1/2^{n}, and ĝ(S) = 0 whenever S ≠ ∅.

Notational variants. The definition of ℱ 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 ℱ would be its own inverse and Parseval would simply state ||f||_{2} = ||f̂||_{2}. However, with this modified inner product the χ_{S} functions no longer have norm 1.

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

2.3 Convolution

Given any two functions f,g: {0,1}^{n} → ℝ, we define their convolution f ∗ g: {0,1}^{n} → ℝ by

(f ∗ g)(x) = \frac{1}{2^{n}} ∑_{y∈\{0,1\}^{n}}f(x ⊕ y)g(y),

where ‘⊕’ 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 ⊕ Y:

Pr[Z = z] = Pr[X = z ⊕ Y] = ∑_{y∈{0,1}^{n}}f(z ⊕ 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.

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:

f̂ ∗ g(S) = \frac{1}{2^{n}} ∑_{x} (f ∗ g)(x)χ_{S}(x)
= \frac{1}{2^{2n}} ∑_{x} ∑_{y} f(x ⊕ y)g(y)χ_{S}(x)
= \frac{1}{2^{n}} ∑_{y} g(y)χ_{S}(y)( \frac{1}{2^{n}} ∑_{x} f(x ⊕ y)χ_{S}(x ⊕ y))
= f̂(S) · ĝ(S).

Suppose we have two functions h_{0} = f ∗ g_{0} and h_{1} = f ∗ g_{1}, for instance from applying the same noiseprocess f to distributions g_{0} and g_{1}. Using the convolution, we can rewrite their distance as

||h_{0}− h_{1}||_{2}^{2} = ||f ∗ (g_{0}− g_{1})||_{2}^{2} = ∑_{S} { \atop (f ∗ (g_{0}− g_{1}))} (S)^{2} = ∑_{S} f̂(S)^{2}· (ĝ_{0}(S) − ĝ_{1}(S))^{2}.

This allows us to bound the difference between h_{0} and h_{1} by analyzing f̂ and ĝ_{0}− ĝ_{1}.

3 Some elementary applications

3.1 Approximating functions by parities

It is often useful to approximate complex objects by much simpler ones. Consider any function f : {0,1}^{n} → [−1,1]. Suppose there exists a function p: {0,1}^{n} → [−1,1] that has some positive correlation ⟨f,p⟩ ≥ ε with f, and suppose p is sparse in that the set 𝒞 = {S | p̂(S) ≠ 0} of nonzero Fourier coefficients has at most c elements. A typical example is where f is a Boolean function and p a lowdegree real polynomial approximating f, since degree-d polynomials have at most c = ∑ _{i=0}^{d} \binom{n}{i} nonzero Fourier coefficients. Now there exists a parity function that has nontrivial correlation with f, as follows:

ε ≤ ⟨f,p⟩ = ∑_{S} p̂(S)⟨f,χ_{S}⟩ ≤ ||p||_{2}\sqrt{∑_{S∈𝒞}⟨f,χ_{S}⟩^{2}},

where we used Cauchy-Schwarz and Parseval. This implies there exists an S such that either χ_{S} or its negation has correlation |⟨f,χ_{S}⟩| ≥ ε/(||p||_{2}\sqrt{c}) ≥ ε/\sqrt{c} with f.

3.2 List decoding the Hadamard code

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 ∈ {0,1}^{n}, the codeword H(S) ∈ {±1}^{2^{n}} is defined as the concatenation of χ_{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 ∈ {±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: {0,1}^{n} → {±1}. Note that ∑_{S} ŵ(S)^{2} = 𝔼[w^{2}] = 1 by Parseval. Then w has normalized distance d(w,H(S)) = 1/2 − ε from codeword H(S) if, and only if, ŵ(S) = 2ε. If the error-rate is less than 1/4 (ε > 1/4) then the original string is the unique S satisfying ŵ(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′)) ≤ 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} −1s 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 − ε for small but positive ε: we can output a small list of potential strings that contains the original string S. This is known as 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 ≤ 1/2 − ε from w: such S correspond to Fourier coefficients ŵ(S) ≥ 2ε, and not too many Fourier coefficients can be that large since their squares sum to 1. More formally:

#\{S: d(H(S),w) ≤ 1/2 − ε\} ≤ \frac{1}{4ε^{2}} ∑_{S:d(w,H(S))≤1/2−ε} ŵ(S)^{2} ≤ \frac{1}{4ε^{2}} ∑_{S} ŵ(S)^{2} = \frac{1}{4ε^{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 [28] showed that we can efficiently, in time poly(n,1/ε), 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 [66, 30] and the references therein.

3.3 Learning under the uniform distribution

A lot of work in the last two decades has used the Fourier transform for learning under the uniform distribution. The idea is that we can learn an unknown function f : {0,1}^{n} → ℝ by approximating its Fourier coefficients. Since the Fourier coefficient

f̂(S) = 𝔼[f · χ_{S}]

is just an expectation under the uniform distribution on {0,1}^{n}, we can approximate it from uniformly drawn examples (x_{1},f(x_{1})),...,(x_{m},f(x_{m})). The empirical average

\frac{1}{m} ∑_{j=1}^{m} f(x_{j}) · χ_{S}(x_{j})

will converge to the right value 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 α_{S} is our estimate for f̂(S) and h = ∑_{S}α_{S}χ_{S} the hypothesis that we output, then by Parseval our overall ℓ_{2}-error is

||f − h||_{2}^{2} = ∑_{S} (f̂(S) − α_{S})^{2}.

When f has range {±1}, we can use sign(h) as our hypothesis for f. We have

Pr[f(x) ≠ sign(h(x))] = \frac{1}{2^{n}} ∑_{x:f(x)≠sign(h(x))}1 ≤ \frac{1}{2^{n}} ∑_{x:f(x)≠sign(h(x))}(f(x) − h(x))^{2} ≤ ||f − h||_{2}^{2}.

These ideas have been used for learning constant-depth circuits [46], for learning DNF [48, 32, 43, 13], juntas [50], decision trees [44, 57], and others.

4 The Bonami-Beckner inequality and some of its consequences

4.1 Bonami-Beckner and KKL

Consider a function f : {0,1}^{n} → ℝ. Suppose its input x ∈ {0,1}^{n} is “noisy:” a new input y is obtained by flipping, independently, each bit of x with a fixed probability ε ∈ [0,1]. The resulting noisy version of f is

f̃(x) = 𝔼_{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 ≠ 0^{n}. Then f̃ is a fairly smooth probability distribution “around” 0^{n}: f̃(x) = ε^{|x|}(1 − ε)^{n−|x|}. If ε ∈ (0,1/2) then the maximum of f̃ still occurs at 0^{n}, but f̃ is much less sharply peaked than the original f.

Now consider the linear map that takes f to f̃. Applying this map to the function f defined by f(x) = (−1)^{x_{i}} gives f̃(x) = (1 − ε)(−1)^{x_{i}}+ ε(−1)^{1−x_{i}} = (1 − 2ε)(−1)^{x_{i}}. Similarly, applying it to χ_{S} gives (1 − 2ε)^{|S|}χ_{S}. Hence our map is a function T_{ρ} that merely shrinks the Fourier coefficient f̂(S) by a factor ρ^{|S|}, where ρ = 1 − 2ε ∈ [−1,1]:

f̃= T_{ρ}(f) = ∑_{S} ρ^{|S|}f̂(S)χ_{S}.

Here we can see the smoothing effect in action: T_{ρ} attenuates the higher-degree Fourier coefficients, thus moving f closer to a constant function. For ρ < 1, the constant f are the only ones satisfying T_{ρ}(f) = f.

Generalizing the ℓ_{2}-norm, for every p ≥ 1 we define the p-norm of a function by

||f||_{p} = ( \frac{1}{2^{n}} ∑_{x} |f(x)|^{p}) ^{1/p}.

One can show this is monotone non-decreasing in p. Since T_{ρ}(f) is an average of functions that all have the same p-norm as f, the triangle inequality immediately implies that T_{ρ} is a contraction: for every p ≥ 1 we have ||T_{ρ}(f)||_{p} ≤ ||f||_{p}. The Bonami-Beckner Hypercontractive Inequality [10, 29, 6] says that this inequality remains true even if we increase the left-hand side by going to a somewhat higher q-norm:

Theorem 4.1 (Bonami-Beckner). If 1 ≤ p ≤ q and 0 ≤ ρ ≤ \sqrt{(p − 1)/(q − 1)} , then

||T_{ρ}(f)||_{q} ≤ ||f||_{p}.

This inequality is a crucial tool in most of the more advanced applications of Fourier analysis on the Boolean cube. The case ρ = \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 [53] for a proof as well as some background and history. Chapter 5 of the book of Janson [33] 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 ∈ [1,2], and using q = 2 and ρ = \sqrt{p − 1} , we have

(p − 1)^{d}||f||_{2}^{2} = (p − 1)^{d} ∑_{S} f̂(S)^{2} ≤ ∑_{S} (p − 1)^{|S|}f̂(S)^{2} = ||T\sqrt{p−1} (f)||_{2}^{2} ≤ ||f||_{p}^{2}.

Hence the p-norm of a low-degree function cannot be much smaller than its 2-norm. A similar argument gives ||f||_{q}^{2} ≤ (q − 1)^{d}||f||_{2}^{2} for all q ≥ 2.

In general, with q = 2, p ∈ [1,2], and ρ = \sqrt{p − 1} , Theorem 4.1 becomes

∑_{S} (p − 1)^{|S|}f̂(S)^{2} = ||T_{ρ}(f)||_{2}^{2} ≤ ||f||_{p}^{2} = ( \frac{1}{2^{n}} ∑_{x} |f(x)|^{p}) ^{2/p}.  (4.1)

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|}.^{1} An important special case of Eq. (4.1) 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 ||f||_{p}^{p} = Pr[f ≠ 0] for any p. Applying Eq. (4.1) with p = 1 + δ gives the following KKL Inequality, after Kahn, Kalai, and Linial [34].

Corollary 4.2 (KKL). For every δ ∈ [0,1] and f : {0,1}^{n} → {−1,0,1}, we have

∑_{S} δ^{|S|}f̂(S)^{2} ≤ (Pr[f ≠ 0])^{2/(1+δ)} .

Informally, with δ < 1 the left-hand side is dominated by the Fourier coefficients of low degree (i. e., those where |S| is small). The right-hand side is smaller than the total “Fourier weight” ∑_{S} f̂(S)^{2} = Pr[f ≠ 0] by a power 2/(1 + δ) > 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.

4.2 Random parities over a fixed set

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 ⊆ {0,1}^{n}. Suppose we pick a set S ⊆ [n] of k indices uniformly at random, and consider the parity of the k-bit substring induced by S and a uniformly random x ∈ A. Intuitively, if A is large then we expect that for most S, the bias β_{S} of this parity to be small: the number of x ∈ A with χ_{S}(x) = 1 should be roughly the same as with χ_{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, i. e., an upper bound on the adversary’s knowledge.

The intuition that large A leads to small biases is justified by the KKL Inequality.^{2} Note the connection between biases and Fourier coefficients: with f the characteristic function of A, we have

β_{S} = 𝔼_{x∈A}[χ_{S}(x)] = \frac{1}{|A|}∑_{x∈A}χ_{S}(x) = \frac{1}{|A|} ∑_{x∈\{0,1\}^{n}}f(x)χ_{S}(x) = \frac{2^{n}}{|A|}f̂(S).

Applying the KKL Inequality, for any δ ∈ [0,1] we can bound the sum of squared biases by

∑_{S∈\binom{[n]}{k}}β_{S}^{2} = \frac{2^{2n}}{|A|^{2}} ∑_{S∈\binom{[n]}{k}} f̂(S)^{2} ≤ \frac{2^{2n}}{δ^{k}|A|^{2}}( \frac{|A|}{2^{n}}) ^{2/(1+δ)} ≤ \frac{1}{δ^{k}} ( \frac{2^{n}}{|A|}) ^{2δ} .

1Recently Eq. (4.1) was generalized from real-valued functions to matrix-valued functions [7].

2To the best of our knowledge, the bound below was first shown by Talagrand [68, Eq. (2.9)] for k = 2, using a large deviation inequality instead of hypercontractivity, and for general k in [27] using the KKL Inequality. [27] used it to prove lower bounds for communication complexity.

Theory of Computing Library, Graduate Surveys TCGS 1 (2008), pp. 1–20 8

By differentiating, one can show that δ = k/[2ln(2^{n}/|A|)]minimizes the right-hand side (assume k ≤ 2ln(2^{n}/|A|) to ensure δ ∈ [0,1]). This gives

𝔼_{S}[β_{S}^{2}] = \frac{1}{\binom{n}{k}} ∑_{S∈\binom{[n]}{k}}β_{S}^{2} = O( \frac{log(2^{n}/|A|)}{n}) ^{k}.  (4.2)

The following example shows this bound is essentially tight, and hence the KKL Inequality is tight as well. Let A = 0^{c} × {0,1}^{n−c} consist of all 2^{n−c} strings starting with c zeroes. Then β_{S} = 1 if S ⊆ [c], and β_{S} = 0 otherwise. The fraction of sets S ∈ \binom{[n]}{k} satisfying S ⊆ [c] is \binom{c}{k}/\binom{n}{k} = Ω(c/n)^{k}. Hence 𝔼_{S}[β_{S}^{2}] = Ω(c/n)^{k} = Ω(log(2^{n}/|A|)/n)^{k}, matching the upper bound of Eq. (4.2).

4.3 Influences of variables

Suppose we have n players, and we have a function f : {0,1}^{n}→ {0,1} 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 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 influence of variable i ∈ [n] on f is defined as

Inf_{i}(f) = Pr[f(x) ≠ f(x ⊕ e_{i})],

where the probability is over uniform x ∈ {0,1}^{n}, and x ⊕ e_{i} is x with the ith 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 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 ith 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 Θ(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}{⌊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) ≈ 1.

Can we find balanced functions where the influences of the variables are much smaller, ideally O(1/n)? Ben-Or and Linial [8] showed that the “tribes” function (an OR-AND tree with bottom fan-out about logn − loglogn) is a balanced function where every variable has influence Θ(log(n)/n). Kahn, Kalai, and Linial [34] 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 Ω(log(n)/n). With some extra work (which we won’t detail here), this implies the existence of a set of only O(n/logn) 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/logn) 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 [67]. Let Var[f] = 𝔼[f^{2}] − 𝔼[f]^{2} be the variance of f. By Parseval, this equals ||f||_{2}^{2}− f̂(∅)^{2} = ∑_{S≠∅} f̂(S)^{2}. Consider a function f : {0,1}^{n} → {0,1}. 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

∑_{i=1}^{n} \frac{Inf_{i}(f)}{log(1/Inf_{i}(f))} = Ω(Var[f]).  (4.3)

The KKL result follows immediately from this: if f is close to balanced then Var[f] = Ω(1). Hence there is an i such that Inf_{i}(f)/log(1/Inf_{i}(f)) = Ω(1/n), which implies Inf_{i}(f) = Ω(log(n)/n).

The proof of Eq. (4.3) is based on the following technical lemma, which uses Bonami-Beckner.

Lemma 4.3. If g: {0,1}^{n} → ℝ satisfies ||g||_{3/2} ≠ ||g||_{2}, then

∑_{S≠∅} \frac{ĝ(S)^{2}}{|S|} ≤ \frac{2.5||g||_{2}^{2}}{log(||g||_{2}/||g||_{3/2})} .

Proof. Using Theorem 4.1 with q = 2 and p = 1 + ρ^{2} = 3/2 we get for every integer k

∑_{S:|S|=k} ĝ(S)^{2} ≤ 2^{k} ∑_{S} 2^{−|S|} ĝ(S)^{2} = 2^{k}||T\sqrt{1/2}(g)||_{2}^{2} ≤ 2^{k}||g||_{3/2}^{2}.

For every integer m we have (using ∑ _{k=1}^{m} 2^{k}/k ≤ 4 · 2^{m}/(m + 1), which is easily proved by induction):

∑_{S≠∅} \frac{ĝ(S)^{2}}{|S|} = ∑_{k=1}^{m} ∑_{S:|S|=k} \frac{ĝ(S)^{2}}{k} + ∑_{S:|S|>m} \frac{ĝ(S)^{2}}{|S|} ≤ ∑_{k=1}^{m} \frac{2^{k}||g||_{3/2}^{2}}{k} + ∑_{S:|S|>m} \frac{ĝ(S)^{2}}{m + 1} ≤ \frac{4 · 2^{m}||g||_{3/2}^{2}+ ||g||_{2}^{2}}{m + 1}

Choose m the largest integer satisfying 2^{m}||g||_{3/2}^{2} ≤ ||g||_{2}^{2}. Then m + 1 > 2log(||g||_{2}/||g||_{3/2}), and

∑_{S≠∅} \frac{ĝ(S)^{2}}{|S|} ≤ \frac{5||g||_{2}^{2}}{m + 1} ≤ \frac{2.5||g||_{2}^{2}}{log(||g||_{2}/||g||_{3/2})} .

Now consider a variable i and define g(x) = f(x)−f(x⊕e_{i}). Then g(x) = 0 if f(x) = f(x⊕e_{i}), and g(x) ∈ {±1} otherwise. Hence ||g||_{2}^{2} = ||g||_{3/2}^{3/2} = Inf_{i}(f) ∈ (0,1), and ||g||_{2}/||g||_{3/2} = Inf_{i}(f)^{−1/6} . The Fourier coefficients of g are closely related to those of f:

ĝ(S) = \{ \begin{matrix}2f̂(S) & if i ∈ S, \\ 0 & otherwise. \end{matrix}  (4.4)

Applying Lemma 4.3 to g gives

∑_{S:i∈S} \frac{4f̂(S)^{2}}{|S|} = ∑_{S} \frac{ĝ(S)^{2}}{|S|} ≤ \frac{2.5||g||_{2}^{2}}{log(||g||_{2}/||g||_{3/2})} = \frac{15Inf_{i}(f)}{log(1/Inf_{i}(f))} .

Summing over all i gives Talagrand’s result:

4Var[f] = 4 ∑_{S≠0} f̂(S)^{2} = ∑_{i=1}^{n} ∑_{S:i∈S} \frac{4f̂(S)^{2}}{|S|} ≤ ∑_{i=1}^{n} \frac{15Inf_{i}(f)}{log(1/Inf_{i}(f))} .

Subsequent work. The subsequent “BKKKL” paper [12] generalized the KKL result to the case of functions f : [0,1]^{n} → {0,1} with real-valued input, with uniform measure on each real-valued variable x_{i}. See Friedgut [23] for some simplifications and corrections of this. A recent related result is that any near-balanced Boolean function with a depth-d decision tree has a variable with influence Ω(1/d) [55].

4.4 The relation between influences, sensitivity, and degree

In this section we relate influences to degree and sensitivity, both of which are important measures of the complexity of Boolean functions.^{3} The sensitivity of a function f : {0,1}^{n} → {0,1} on input x is

s_{x}(f) = |{i | f(x) ≠ f(x ⊕ e_{i})}|

and the average sensitivity of f is

\overline{s}(f) = \frac{1}{2^{n}} ∑_{x∈\{0,1\}^{n}}s_{x}(f).

By linearity of expectation, average sensitivity equals the total influence:

\overline{s}(f) = ∑_{i=1}^{n} Inf_{i}(f).  (4.5)

Here we give a relation between degree and sensitivity due to Shi [64]: average sensitivity lower bounds the degree of approximating polynomials. Suppose a degree-d n-variate real polynomial p: {0,1}^{n} → [0,1] approximates f : {0,1}^{n} → {0,1}, in the sense that there is an ε ∈ [0,1/2) such that |f(x) − p(x)| ≤ ε for every x ∈ {0,1}^{n}. Let q be the degree-d polynomial 1 − 2p. This has range [−1,1], hence ∑_{S} q̂(S)^{2} = ||q||_{2}^{2} ≤ 1. Note that q(x) ∈ [−1,−1 + 2ε] if f(x) = 1, and q(x) ∈ [1 − 2ε,1] if f(x) = 0. Consider the function q^{(i)}(x) = q(x) − q(x ⊕ e_{i}). Using Parseval and the analogue of Eq. (4.4), we have

(2 − 4ε)^{2}Inf_{i}(f) ≤ 𝔼[(q^{(i)})^{2}] = ∑_{S} q̂^{(i)}(S)^{2} = 4 ∑_{S:i∈S} q̂(S)^{2}.

Dividing by 4 and summing over all i gives the lower bound on the degree:

(1 − 2ε)^{2}\overline{s}(f) = (1 − 2ε)^{2} ∑_{i=1}^{n} Inf_{i}(f) ≤ ∑_{i=1}^{n} ∑_{S:i∈S} q̂(S)^{2} = ∑_{S} |S|q̂(S)^{2} ≤ d ∑_{S} q̂(S)^{2} ≤ d .

3See the survey [15]. Other Fourier-based results on polynomial degrees are in [56, 62, 14]. This section does not need the Bonami-Beckner or KKL Inequalities, but is placed after Section 4.3 because it considers the influences defined there.

Theory of Computing Library, Graduate Surveys TCGS 1 (2008), pp. 1–20 11

A random Boolean function has \overline{s}(f) ≈ n/2 and ε-approximate degree at least n/2 − O(\sqrt{n}) [2] (for fixed ε), 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 [52]. Suppose f : {0,1}^{n} → {0,1} depends on all of its n variables (equivalently, each variable has positive influence). Consider f^{(i)}(x) = f(x) − f(x ⊕ e_{i}). This is an n-variate polynomial of degree d ≤ 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.^{4} Hence

Inf_{i}(f) = Pr[f^{(i)} ≠ 0] ≥ 2^{−deg(f)}

for each i. Summing over i we get

\frac{n}{2^{deg(f)}} ≤ ∑_{i=1}^{n} Inf_{i}(f) = ∑_{i=1}^{n} ∑_{S} f̂^{(i)}(S)^{2} = 4∑_{S} |S|f̂(S)^{2} ≤ 4 deg(f)∑_{S} f̂(S)^{2} ≤ 4 deg(f).

This implies the bound from [52]:

deg(f) ≥ log(n) − O(loglogn)

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(loglogn) term. This function takes an input x_{1}...x_{m}y_{0}...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}...x_{m}. The function depends on all n variables. It is represented by

∑_{i∈{0,1}^{m}} y_{i} ∏_{j:i_{j}=1} x_{j} ∏_{j:i_{j}=0} (1 − x_{j})

and hence has degree m + 1 ≤ logn + 1.

5 A guide to literature

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.

PCPs and hardness of approximation. Possibly the most important application of Fourier analysis in theoretical computer science is its use in designing and analyzing 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 [4, 17] says that a language is in NP if, and only if, it has witnesses that can be verified probabilistically using only O(logn) bits of randomness and a constant number of queries to bits of the witness. Some of the most efficient PCPs are based on Fourier analysis, Håstad’s 3-query PCP being a prime example [31]. 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 [3] give a good introduction to this material.

4This is a basic and well known property of Reed-Muller error-correcting codes [47, p. 375]. In the computer science literature this fact is usually called the Schwartz-Zippel Lemma [61, 69].

Theory of Computing Library, Graduate Surveys TCGS 1 (2008), pp. 1–20 12

A recent development is the use of the “Unique Games Conjecture.” This conjecture, due to Khot [37], 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 [38], vertex cover [40], and others [16, 41, 19, 39, 59], 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 [38] and proved in [49]. 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 f̃= T_{ρ}(f) (as defined in Section 4.1).

Threshold phenomena. A 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^{∘}C and liquid if the temperature is just above 0^{∘}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ős and Rényi [20] introduced this model and showed a sharp threshold for connectivity: if p is slightly below (logn)/n then the probability of G(n,p) being connected tends to 0 with n, while if p is slightly larger than (logn)/n then this probability tends to 1. Friedgut and Kalai [24] later showed that 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^{5}), 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 [36] 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.

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 [5] 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 [35] and O’Donnell [54] are excellent starting points for such connections between Fourier analysis and social choice theory. A very recent related result is [26].

5Actually 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 [58] for details.

Theory of Computing Library, Graduate Surveys TCGS 1 (2008), pp. 1–20 13

When are functions close to juntas? Recall that a k-junta is a function on {0,1}^{n} that depends on at most k of its variables. Friedgut [22] 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 Section 4.4 shows the exponential is necessary: it has average sensitivity O(logn) but cannot be approximated well by a Boolean function depending on only o(n) variables. Friedgut et al. [25] 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 (i. e., a dictator or its negation). Bourgain [11] 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. [18] analyzed the same phenomenon for bounded—but not necessarily Boolean—functions on the Boolean cube.

Other applications. Some results in the area of property testing are based on Fourier analysis. Examples are the algorithm by Fischer et al. [21] for testing if a Boolean function is close to or far from a k-junta, and the one by Alon et al. [1] 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 Section 3.2, 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 [51]. Fourier analysis has also been used for lower bounds on various kinds of communication complexity [60, 42, 27, 63], and for analysis of low-distortion embeddings of one metric space into another [45, 41].

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 [9] describes the main applications up to 1997. Štefankovič’s MSc thesis [65] 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 [36] concentrates on threshold phenomena. The very recent survey by O’Donnell [54] 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:

     Irit Dinur and Ehud Friedgut: http://www.cs.huji.ac.il/^{∼} analyt
     Subhash Khot: http://www.cc.gatech.edu/^{∼} khot/Fourier.htm
     Guy Kindler: http://dimacs.rutgers.edu/^{∼} gkindler/boolean-course
     Nati Linial: http://www.cs.huji.ac.il/^{∼} nati/PAPERS/uw
     Elchanan Mossel: http://www.stat.berkeley.edu/%7Emossel/teach/206af05
     Ryan O’Donnell: http://www.cs.cmu.edu/^{∼} odonnell/boolean-analysis
     Oded Regev: http://www.cs.tau.ac.il/^{∼} odedr/teaching/analysis fall 2007

Acknowledgments

Thanks to David García Soriano, Elena Grigorescu, Peter Harremoë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.

References

[1] N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie: Testing k-wise and almost k-wise independence. In Proc. 39th STOC, pp. 496–505. ACM Press, 2007. [STOC:1250790.1250863]. 5

[2] A. Ambainis: A note on quantum black-box complexity of almost all Boolean functions. Inform. Process. Lett., 71(1):5–7, 1999. [IPL:10.1016/S0020-0190(99)00079-4]. 4.4

[3] S. Arora and B. Barak: Complexity Theory: A Modern Approach. Cambridge University Press, 2009. To appear. Preliminary version available at

http://www.cs.princeton.edu/theory/complexity. 5

[4] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Earlier version in FOCS’92. [JACM:278298.278306]. 5

[5] K. Arrow: A difficulty in the concept of social welfare. J. Political Economy, 58(4):328–346, 1950. [doi:10.1086/256963]. 5

[6] W. Beckner: Inequalities in Fourier analysis. Ann. of Math., 102:159–182, 1975. 4.1

[7] A. Ben-Aroya, O. Regev, and R. de Wolf: A hypercontractive inequality for matrix-valued functions with applications to quantum computing. In Proc. 49th FOCS. IEEE Computer Society Press, 2008. 1

[8] M. Ben-Or and N. Linial: Collective coin flipping. In S. Micali, editor, Randomness and Computation, pp. 91–115. JAI Press, 1989. Earlier version in FOCS’85. 4.3

[9] A. Bernasconi, B. Codenotti, and J. Simon: On the Fourier analysis of Boolean functions. Technical Report IMC B4-97-03, Istituto di Matematica Computazionale, Pisa, 1997. 5

[10] A. Bonami: Étude des coefficients de Fourier des fonctions de L^{p}(G). Annales de l’Institut Fourier, 20(2):335–402, 1970. 4.1

[11] J. Bourgain: On the distribution of the Fourier spectrum of Boolean functions. Israel J. Math., 131(1):269–276, 2002. [Springer:657221r06x818652]. 5 [12] J. Bourgain, J. Kahn, G. Kalai, G. Katznelson, and N. Linial: The influence of vari-

ables in product spaces. Israel J. Math., 77(1–2):55–64, 1992. [Springer:456880489w184683]. 4.3

[13] N. Bshouty, E. Mossel, R. O’Donnell, and R. Servedio: Learning DNF from random walks. J. Comput. System Sci., 71(3):250–265, 2005. Earlier version in FOCS’03. [JCSS:10.1016/j.jcss.2004.10.010]. 3.3

[14] H. Buhrman, N. Vereshchagin, and R. de Wolf: On computation and communication with small bias. In Proc. 22nd Conference on Comput. Complexity, pp. 24–32. IEEE Computer Society Press, 2007. [CCC:10.1109/CCC.2007.18]. 3

[15] H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X]. 3

[16] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar: On the hardness of approximating sparsest cut and multicut. In Proc. 20th Conf. Comput. Complexity, pp. 144–153. IEEE Computer Society Press, 2005. [CCC:10.1109/CCC.2005.20]. 5

[17] I. Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Earlier version in STOC’06. [JACM:10.1145/1236457.1236459]. 5

[18] I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell: On the Fourier tails of bounded functions over the discrete cube. Israel J. Math., 160(1):389–412, 2007. Earlier version in STOC’06. [Springer:43k0r5p3g28k508g, STOC:10.1145/1132516.1132580]. 5

[19] I. Dinur, E. Mossel, and O. Regev: Conditional hardness for approximate coloring. In Proc. 38nd STOC, pp. 344–353. ACM Press, 2006. [STOC:1132516.1132567]. 5

[20] P. Erdős and A. Rényi: On random graphs I. Publicationes Mathematicae, 6:290–297, 1959. 5

[21] E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky: Testing juntas. J. Comput. System Sci., 68(4):753–787, 2004. Earlier version in FOCS’02. [JCSS:10.1016/j.jcss.2003.11.004]. 5

[22] E. Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [Springer:fxcj48rnbwv5gjdb]. 5

[23] E. Friedgut: Influences in product spaces: KKL and BKKKL revisited. Combin. Probab. Comput., 13(1):17–29, 2004. [Cambridge:10.1017/S0963548303005832]. 4.3

[24] E. Friedgut and G. Kalai: Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124:2993–3002, 1996. 5

[25] E. Friedgut, G. Kalai, and A. Naor: Boolean functions whose Fourier transform is concentrated at the first two levels. Adv. in Appl. Math., 29(3):427–437, 2002. [Elsevier:10.1016/S0196-8858(02)00024-6]. 5 [26] E. Friedgut, G. Kalai, and N. Nisan: Elections can be manipulated often. In Proc. 49th

FOCS. IEEE Computer Society Press, 2008. 5

[27] D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf: Exponential separations for one-way quantum communication complexity, with applications to cryptography. In Proc. 39th STOC, pp. 516–525. ACM Press, 2007. [STOC:1250790.1250866]. 2, 5

[28] O. Goldreich and L. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25–32. ACM Press, 1989. [STOC:73007.73010]. 3.2

[29] L. Gross: Logarithmic Sobolev inequalities. Amer. J. Math., 97(4):1061–1083, 1975. 4.1

[30] V. Guruswami: Algorithmic Results in List Decoding, volume 2(2) of Foundations and Trends in Theoretical Computer Science. Now Publishers, 2007. 3.2

[31] J. Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Earlier version in STOC’97. [JACM:10.1145/502090.502098]. 5

[32] J. Jackson: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. System Sci., 55(3):414–440, 1997. Earlier version in FOCS’94. [JCSS:10.1006/jcss.1997.1533]. 3.3

[33] S. Janson: Gaussian Hilbert Spaces, volume 129 of Cambridge Tracts in Mathematics. Cambridge University Press, 1997. 4.1

[34] J. Kahn, G. Kalai, and N. Linial: The influence of variables on Boolean functions. In Proc. 29th FOCS, pp. 68–80. IEEE Computer Society Press, 1988. 4.1, 4.3

[35] G. Kalai: Noise sensitivity and chaos in social choice theory. Technical report, Discussion Paper Series dp399. Center for rationality and interactive decision theory, Hebrew University, 2005.

Available at http://www.ma.huji.ac.il/^{∼} kalai/CHAOS.pdf. 5

[36] G. Kalai and S. Safra: Threshold phenomena and influence. In Percus et al. [58], pp. 25–60. 5, 5

[37] S. Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [STOC:509907.510017]. 5

[38] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. [SICOMP:10.1137/S0097539705447372]. 5

[39] S. Khot and R. O’Donnell: SDP gaps and UGC-hardness for MAXCUTGAIN. In Proc. 47th FOCS, pp. 217–226. IEEE Computer Society Press, 2006. [FOCS:10.1109/FOCS.2006.67]. 5

[40] S. Khot and O. Regev: Vertex cover might be hard to approximate to within 2 − ϵ. J. Comput. System Sci., 74(3):335–349, 2008. Earlier version in Complexity’03. [JCSS:10.1016/j.jcss.2007.06.019]. 5 [41] S. Khot and N. Vishnoi: The unique games conjecture, integrality gap for cut problems and

embeddability of negative type metrics into ℓ_{1}. In Proc. 46th FOCS, pp. 53–62. IEEE Computer Society Press, 2005. [FOCS:10.1109/SFCS.2005.74]. 5, 5

[42] H. Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20– 46, 2007. Earlier version in FOCS’01. [SICOMP:10.1137/S0097539702405620]. 5

[43] A. Klivans and R. Servedio: Learning DNF in time 2^{Õ(n^{1/3})}. J. Comput. System Sci., 68(2):303–318, 2004. Earlier version in STOC’01. [JCSS:10.1016/j.jcss.2003.07.007]. 3.3

[44] E. Kushilevitz and Y. Mansour: Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. Earlier version in STOC’91. [SICOMP:10.1137/0222080]. 3.3

[45] J. R. Lee and A. Naor: Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal., 14(4):745–747, 2004. [Springer:r36q4553fwheur9u]. 5

[46] N. Linial, Y. Mansour, and N. Nisan: Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607–620, 1993. Earlier version in FOCS’89. [JACM:10.1145/502090.502098]. 3.3

[47] F. MacWilliams and N. Sloane: The Theory of Error-Correcting Codes. North-Holland, 1977. 4

[48] Y. Mansour: An O(n^{loglogn}) learning algorithm for DNF under the uniform distribution. J. Comput. System Sci., 50(3):543–550, 1995. Earlier version in COLT’92. [JCSS:10.1006/jcss.1995.1043]. 3.3

[49] E. Mossel, R. O’Donnell, and K. Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Ann. of Math., 2008. To appear. Earlier version in FOCS’05. 5

[50] E. Mossel, R. O’Donnell, and R. Servedio: Learning functions of k relevant variables. J. Comput. System Sci., 69(3):421–434, 2004. Earlier version in STOC’03. [JCSS:10.1016/j.jcss.2004.04.002]. 3.3

[51] M. Navon and A. Samorodnitsky: On Delsarte’s linear programming bounds for binary codes. In Proc. 46th FOCS, pp. 327–338. IEEE Computer Society Press, 2005. [FOCS:10.1109/SFCS.2005.55]. 5

[52] N. Nisan and M. Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, 1994. Earlier version in STOC’92. [CC:p1711275700w5264]. 4.4

[53] R. O’Donnell: Lecture notes for a course “Analysis of Boolean functions”, 2007. Available at

http://www.cs.cmu.edu/^{∼} odonnell/boolean-analysis. 4.1

[54] R. O’Donnell: Some topics in analysis of Boolean functions. Technical report, ECCC Report TR08–055, 2008. Paper for an invited talk at STOC’08. [ECCC:TR08-055]. 5, 5 [55] R. O’Donnell, M. Saks, O. Schramm, and R. Servedio: Every decision tree has an

influential variable. In Proc. 46th FOCS, pp. 31–39. IEEE Computer Society Press, 2005. [FOCS:10.1109/SFCS.2005.34]. 4.3

[56] R. O’Donnell and R. Servedio: Extremal properties of polynomial threshold functions. In Proc. 18th Conf. Comput. Complexity, pp. 3–12. IEEE Computer Society Press, 2003. 3

[57] R. O’Donnell and R. Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. Earlier version in Complexity’06. [SICOMP:10.1137/060669309]. 3.3

[58] A.G. Percus, G. Istrate, and C. Moore, editors. Computational Complexity and Statistical Physics. Oxford University Press, 2006. 5, 36

[59] P. Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [STOC:1374376.1374414]. 5

[60] R. Raz: Fourier analysis for probabilistic communication complexity. Comput. Complexity, 5(3/4):205–221, 1995. [CC:p7346675080r85r4]. 5

[61] J. T. Schwartz: Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701–717, 1980. [JACM:10.1145/322217.322225]. 4

[62] R. Servedio: Every linear threshold function has a low-weight approximator. Comput. Complexity, 16(2):180–209, 2007. Earlier version in Complexity’06. [CC:64682257x6344776]. 3

[63] A. Sherstov: Communication lower bounds using dual polynomials. Technical report, ECCC Report TR08–057, 2008. [ECCC:TR08-057]. 5

[64] Y. Shi: Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables. Inform. Process. Lett., 75(1–2):79–83, 2000. [IPL:10.1016/S0020-0190(00)00069-7]. 4.4

[65] D. Štefankovič: Fourier transforms in computer science. Master’s thesis, University of Chicago, Department of Computer Science, 2000. Available at

http://www.cs.rochester.edu/^{∼} stefanko/Publications/Fourier.ps. 5

[66] M. Sudan: List decoding: Algorithms and applications. In Proc. Intern. Conf. IFIP TCS, volume 1872 of Lect. Notes in Comput. Sci., pp. 25–41. Springer, 2000. 3.2

[67] M. Talagrand: On Russo’s approximate 0-1 law. Ann. Probab., 22(3):1576–1587, 1994.

http://projecteuclid.org/euclid.aop/1176988612. 4.3

[68] M. Talagrand: How much are increasing sets positively correlated? Combinatorica, 16(2):243– 258, 1996. [Springer:uvm737238p44xk37]. 2

[69] R. E. Zippel: Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM 79, volume 72 of Lect. Notes in Comput. Sci., pp. 216–226. Springer, 1979. 4 AUTHOR

Ronald de Wolf senior researcher CWI Amsterdam rdewolf cwi nl

http://homepages.cwi.nl/^{∼} rdewolf

ABOUT THE AUTHOR

Ronald de Wolf graduated from the University of Amsterdam and CWI in 2001. His advisors were Harry Buhrman and Paul Vitányi. His CS interests include quantum computing, complexity theory, and learning theory. More details can be found on his homepage. He also holds a degree in philosophy, and enjoys classical music and literature.