Analysis of Boolean Functions

Linearity testing and Arrow’s theorem

Open Problem (S. Srinivasan): Suppose g:\{-1,1\}^{n}\to\pm\big{[}\frac{2}{3},1\big{]} where g(x)\in\big{[}\frac{2}{3},1\big{]} if $\sum_{i=1}^{n}x_{i}\geq\frac{n}{2}$ and g(x)\in\big{[}-1,-\frac{2}{3}\big{]} if $\sum_{i=1}^{n}x_{i}\leq-\frac{n}{2}$. Prove $\deg(f)=\Omega(n)$.

In this workshop we will study the analysis of boolean functions and its applications to topics such as property testing, voting, pseudorandomness, Gaussian geometry and the hardness of approximation. Two recurring themes that we will see throughout the week are:

The noisy hypercube graph is a small set expander.

Every boolean function has a “junta part” and a “Gaussian part”.

We will write $\hat{f}(S)$ to denote the coefficient $c_{S}$ and $\chi_{S}(x)$ for the function $\prod_{i\in S}x_{i}$, and call $f(x)=\sum_{S\subseteq[n]}\hat{f}(S)\chi_{S}(x)$ the Fourier expansion of $f$. We adopt the convention that $\chi_{\emptyset}\equiv 1$, the identically $1$ function. We will write $\deg(f)$ to denote $\max_{S\subseteq[n]}\{|S|\,:\,\hat{f}(S)\neq 0\}$, and call this quantity the Fourier degree of $f$.

We will sometimes refer to $\chi_{S}(x):\{-1,1\}^{n}\rightarrow\{-1,1\}$ as the “parity-on-$S$” function, since it takes value 1 if there are an even number of $-1$ coordinates in $x$ and $-1$ otherwise. Using the notation of Theorem 1, we have that $\widehat{\mathsf{MAJ}_{3}}(\left\{1\right\})=\frac{1}{2}$, $\widehat{\mathsf{MAJ}_{3}}(\left\{1,2,3\right\})=-\frac{1}{2}$, $\widehat{\mathsf{MAJ}_{3}}(\left\{1,2\right\})=0$, and $\deg(\mathsf{MAJ}_{3})=3$.

Let $f,g:\{-1,1\}^{n}\rightarrow\{-1,1\}$. We define the inner product between $f$ and $g$ as

Proof. First note that $\chi_{S}\cdot\chi_{T}=\chi_{S\Delta T}$ since $\prod_{i\in S}x_{i}\prod_{j\in T}x_{j}=\prod_{i\in S\Delta T}x_{i}\prod_{j\in S\cap T}x_{j}^{2}=\prod_{i\in S\Delta T}x_{i}$, where the final equality uses the fact that $x_{i}^{2}=1$ for $x_{i}\in\{-1,1\}$. Next, we claim that

noting that this implies the theorem since $S\Delta T=\emptyset$ iff $S=T$. Recall that we have defined $\chi_{\emptyset}$ to be the identically 1 function, and if $U\neq\emptyset$ then exactly half the inputs $x\in\{-1,1\}^{n}$ have $\chi_{U}(x)=1$ and the other half $\chi_{U}(x)=-1$.

Proof. To see that this holds, we check that

Here we have used the Fourier expansion of $f$ for the first equality, linearity of the inner product for the second, and orthonormality of parity functions (Theorem 3) for the last.

Next we have Plancherel’s theorem, which states that the inner product of $f$ and $g$ is precisely the dot product of their vectors of Fourier coefficients.

Proof. Again we use the Fourier expansions of $f$ and $g$ to check that

The second equality holds by linearity of inner product, and the last by orthonormality.

Proof. For the first equality, we check that $\hat{f}(\emptyset)=\operatorname{{\bf E}}[f(x)\chi_{\emptyset}(x)]=\operatorname{{\bf E}}[f(x)]$. The second equality holds because

Here the second equality uses an application of Parseval’s identity.

It is nice to think of $\hat{f}(S)^{2}$ as the “weight” of $f$ on $S$, with the sum of weights of $f$ on all $2^{n}$ subsets $S$ of $[n]$ being 1 by Parseval’s. Often it will also be convenient to stratify these weights according to the cardinality of the set $S$.

For example, in this notation we have $\mathbf{W}^{0}(\mathsf{MAJ}_{3})=\mathbf{W}^{2}(\mathsf{MAJ}_{3})=0$ and $\mathbf{W}^{1}(\mathsf{MAJ}_{3})=\mathbf{W}^{3}(\mathsf{MAJ}_{3})=1/2$.

Note that $(f*g)(x)=(g*f)(x)$, since $(\boldsymbol{y},\boldsymbol{y}+x)$ is just a uniformly random pair of inputs with distance $x$ and therefore has the same distribution as $(\boldsymbol{y}+x,\boldsymbol{y})$. Similarly it can be checked that the convolution operator is commutative: $(f*g)*h=f*(g*h)$. The following facts also follow easily from definitions:

$\langle\varphi,f\rangle=\mathop{{\bf E}\/}_{y\sim\varphi}[f(y)]$.

$(\varphi*f)(x)=\operatorname{{\bf E}}_{y\sim\varphi}[f(x+y)]$.

The density for $z=y_{1}+y_{2}$, where $y_{1}\sim\varphi_{1}$ and $y_{2}\sim\varphi_{2}$, is $\varphi_{1}*\varphi_{2}$.

Proof. By Theorem 12 and Plancherel, both sides of the identity equal $\sum_{S\subseteq[n]}\hat{f}(S)\hat{g}(S)\hat{h}(S)$.

2 Blum-Luby-Rubinfeld

It is natural to consider analogous notions for approximate linearity.

A straightforward generalization of argument given in the proof of Proposition 16 shows that Definition 18 (approximately linear $\#2$) implies Definition 17 (approximately linear $\#1$). However, the argument for the reverse implication no longer holds. We will adopt Definition 18 as our notion of approximate linearity for now, and we will see that the linearity test of Blum, Luby, and Rubinfeld [BLR93] implies that both definitions are in fact equivalent. The Fourier-analytic proof we present here is due to Bellare et. al [BCH+96].

3 Voting and influence

Puzzle: Is it possible for $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ to have exactly $k$ non-zero Fourier coefficients, for $k=0,1,2,3,4,5,6,7$? Classify all functions with $2$ non-zero Fourier coefficients.

Puzzle: Find all $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ with $\mathbf{W}^{1}(f)=1$.

The following are a few reasonable properties one may expect of a voting scheme:

Monotone: if $x_{i}\leq y_{i}$ for all $i\in[n]$ then $f(x)\leq f(y)$.

Symmetric: $f(\pi(x))=f(x)$ for all permutations $\pi\in S_{n}$ and $x\in\{-1,1\}^{n}$.

Transitive-symmetric (weaker than symmetric): for all $i,j\in[n]$ there exists a permutation $\pi\in S_{n}$ such that $\pi(i)=j$ and $f(x)=f(\pi(x))$ for all $x\in\{-1,1\}^{n}$.

Later in this section (for the proof of Arrow’s theorem) we will also assume that voters vote independently and uniformly; this is known as the impartial culture assumption in social choice theory.

$(D_{i}f)(x)=\sum_{S\ni i}\hat{f}(S)\chi_{S\backslash i}(x)$.

The quantity $\sum_{i=1}^{n}{\bf 1}(f(x)\neq f(x^{\oplus i}))$ is known as the sensitivity of $f$ at $x$, and so the total influence of a boolean function is also known as its average sensitivity. If $f$ is viewed as a 2-coloring of the boolean hypercube, the total influence can also be seen to be equal to $n$ times the fraction of bichromatic edges.

The proof of this proposition follows immediately from the Fourier expression for variable influence given by Theorem 24. Notice that each Fourier coefficient is weighted by its cardinality in the sum, and so total influence may also be viewed as a measure of the “average degree” of $f$’s Fourier expansion.

4 Noise stability and Arrow’s theorem

Let $\rho\in$ and fix $x\in\{-1,1\}^{n}$. Let $N_{\rho}(x)$ be the distribution on $\{-1,1\}^{n}$ where $y\sim N_{\rho}(x)$ if for all $i\in[n]$, $y_{i}=x_{i}$ with probability $\rho$, and $y_{i}$ is uniformly random $\pm 1$ with probability $1-\rho$. More generally, for $\rho\in$, we have that $N_{\rho}(x)$ is the distribution on strings $y$ where

If $x\sim\{-1,1\}^{n}$ is uniformly random and $y\sim N_{\rho}(x)$, we say that $x$ and $y$ are $\rho$-correlated strings; equivalently, $x$ and $y$ are $\rho$-correlated if they are both uniformly random and $\operatorname{{\bf E}}[x_{i}y_{i}]=\rho$ for all $i\in[n]$.

$(T_{\rho}f)(x)=\sum_{S\subseteq[n]}\rho^{|S|}\hat{f}(S)\chi_{S}(x)$.

Proof. The first identity follows from the linearity of the noise operator, along with the observation that $(T_{\rho}\chi_{S})(x)=\rho^{|S|}\chi_{S}(x)$. The second holds by noting that

Suppose there is an election with $n$ voters and three candidates: $A,B$ and $C$. Each voter ranks the candidates by submitting three bits indicating her preferences: whether the prefers $A$ to $B$ (say, $-1$ if so and $1$ otherwise), and similarly for $B$ versus $C$ and $C$ versus $A$. Clearly a rational voter cannot simultaneously prefer $A$ to $B$, $B$ to $C$ and $C$ to $A$; her ordering of the candidates must be non-cyclic.

A triple $(a,b,c)\in\{-1,1\}^{3}$ is rational if not all three bits are equal (i.e., $(a,b,c)$ defines a total ordering, and is a valid preference profile). We define the function $\mathsf{NAE}:\{-1,1\}^{3}\rightarrow\{1,0\}$ to be $1$ iff not all three bits are equal.

Now suppose the preferences of the $n$ voters are aggregated into three $n$-bit strings $x,y$ and $z$, and the aggregate preference of the electorate is represented by the triple $(f(x),f(y),f(z))$ for some boolean function $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$. Clearly we would like for the the outcome of the election to be rational; that is, $\mathsf{NAE}(f(x),f(y),f(z))=1$.

With $\mathsf{MAJ}$ as the aggregating function it is possible that all voters submit rational preferences and yet the aggregated preference string is irrational.

Suppose $f$ is an aggregating function that always produces a rational outcome if all voters vote rationally. Then $f=\pm{\sf DICT}_{i}$ for some $i\in[n]$. If $f$ is further restricted to be unanimous (i.e. $f(1,\ldots,1)=1$ and $f(-1,\ldots,-1)=-1$; certainly a very reasonable assumption) then $f$ must be a dictator.

The main result of this section is a robust version of Arrow’s impossibility theory due Gil Kalai [Kal02]. It expresses the probability that an aggregating function $f$ produces a rational outcome in terms of the noise stability of $f$, under the impartial culture assumption (each voter selects an $\mathsf{NAE}$-triple $(x_{i},y_{i},z_{i})$ uniformly and independently).

Proof. Using the arithmetization $\mathsf{NAE}(a,b,c)=\frac{3}{4}-\frac{1}{4}(ab+bc+ac)$, we first note that

Theorem 35 does indeed imply Arrow’s impossibility theorem since

and so if $\operatorname{{\bf E}}[\mathsf{NAE}(f(x),f(y),f(z))]=1$ then $\mathbf{W}^{1}(f)\geq 1$. Furthermore note that the probability of an irrational outcome is at least $1-\varepsilon$ then $\mathbf{W}^{1}\geq 1-O(\varepsilon)$. By a theorem of E. Friedgut, G. Kalai and A. Naor [FKN02], if $\mathbf{W}^{1}(f)\geq 1-\varepsilon$ then $f$ is $O(\varepsilon)$-close to $\pm{\sf DICT}_{i}$ for some $i\in[n]$. Therefore Kalai’s theorem is in fact a robust version of Arrow’s impossibility theorem: if most rational voter preference profiles aggregate to a rational outcome, then the aggregating function must be close to a dictator or anti-dictator.

We conclude by giving an upper bound on level-1 Fourier weight of transitive-symmetric functions. By Theorem 35, this gives an upper bound on the probability that such functions aggregate rational voter preference profiles to a rational outcome. We will also prove a generalization of this fact (Proposition 42) using the Berry-Esséen theorem tomorrow.

Suppose $\hat{f}(i)=\hat{f}(j)$ for all $i,j\in[n]$. Then $\mathbf{W}^{1}(f)\leq{\textstyle\frac{2}{\pi}}+o_{n}(1)$.

Proof. First note that \sum_{i=1}^{n}\hat{f}(i)^{2}=n\cdot\hat{f}(1)^{2}=n\cdot\big{(}\frac{1}{n}\sum_{i=1}^{n}\hat{f}(i)\big{)}^{2}=\frac{1}{n}\big{(}\sum_{i=1}^{n}\hat{f}(i)\big{)}^{2}. The claim then follows since we have seen that $\sum_{i=1}^{n}\hat{f}(i)\leq\sum_{i=1}^{n}\widehat{\mathsf{MAJ}}(i)\sim\sqrt{2n/\pi}$ (Proposition 27).

Noise stability and small set expansion

Puzzle: Compute the Fourier expansion of $\mathsf{MAJ}_{n}$. Hint: consider $T_{\rho}D_{i}\mathsf{MAJ}(1,\ldots,1)$.

Let $B\geq 1$. We say that a random variable $X$ is $B$-reasonable if $\operatorname{{\bf E}}[X^{4}]\leq B\cdot\operatorname{{\bf E}}[X^{2}]^{2}$. Equivalently, $\|X\|_{4}\leq B^{1/4}\cdot\|X\|_{2}$.

For example, a uniformly random $\pm 1$ bit (i.e. a Rademacher random variable) is $1$-reasonable, and a standard Gaussian is 3-reasonable. The Berry-Esséen theorem [Ber41, Ess42] is a finitary version of the central limit theorem, giving explicit bounds on the rate at which reasonable random variables converge towards the Gaussian distribution.

where \varepsilon=\big{(}B\cdot\sum_{i=1}^{n}\sigma_{i}^{4}\big{)}^{1/2}\leq\sqrt{B}\cdot\max\left\{|\sigma_{i}|\right\}.

We prove the Berry-Esséen theorem with a weaker bound of \varepsilon=\big{(}B\cdot\sum_{i=1}^{n}\sigma_{i}^{4}\big{)}^{1/5} in Section 4.2.

Let $\mathcal{G},\mathcal{G}^{\prime}\sim N(0,1)$ be independent standard Gaussians. Set $\mathcal{H}=(\mathcal{G},\mathcal{G}^{\prime})\cdot(\rho,\sqrt{1-\rho^{2}}):=\rho\cdot\mathcal{G}+\sqrt{1-\rho^{2}}\cdot\mathcal{G}^{\prime}$. Then $\mathcal{G}$ and $\mathcal{H}$ are $\rho$-correlated Gaussians. Note that if $\mathcal{G}$ and $\mathcal{H}$ are $\rho$-correlated Gaussians then $\operatorname{{\bf E}}[\mathcal{G}\mathcal{H}]=\rho\cdot\operatorname{{\bf E}}[\mathcal{G}^{2}]+\sqrt{1-\rho^{2}}\cdot\operatorname{{\bf E}}[\mathcal{G}]\operatorname{{\bf E}}[\mathcal{G}^{\prime}]=\rho$.

and so it suffices to argue that $\operatorname{{\bf Pr}}[\mathsf{MAJ}(x)\neq\mathsf{MAJ}(y)]\to{\textstyle\frac{1}{\pi}}\arccos(\rho)$. Next, we view

While the standard central limit theorem tells us that $\vec{X}=(x_{1}+\ldots+x_{n})/\sqrt{n}$ and $\vec{Y}=(y_{1}+\ldots+y_{n})/\sqrt{n}$ each individually converges towards the standard Gaussian $\mathcal{G}\sim N(0,1)$, the two-dimensional central limit theorem states that $(\vec{X},\vec{Y})$ actually converge to $\rho$-correlated Gaussians $(\mathcal{G},\mathcal{H})$ as $n\to\infty$. In fact, the two-dimensional Berry-Esséen theorem quantifies this rate of convergence, bounding the error by $\pm O(1/\sqrt{n})$ as long as $\rho$ is bounded away from $\pm 1$. Combining this with Sheppard’s formula, we conclude that

2 The noisy hypercube graph

We now give a self-contained proof this fact, due to Talagrand [Tal96]:

Let $f:\{-1,1\}^{n}\to\{0,1\}$ and $\alpha=\operatorname{{\bf E}}[f]$. Then $\mathcal{W}_{1}(f)=O(\alpha^{2}\ln(1/\alpha))$.

The first summand is at most $\alpha\cdot t_{0}$, and the second is at most

by Hoeffding, where the inequality holds since $t_{0}\geq 1$. Choosing $t_{0}=(2\ln(1/\alpha))^{1/2}\geq 1$, we get

The claimed inequality then follows by applying (5).

Let $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ with $|\hat{f}(i)|\leq\varepsilon$ for all $i\in[n]$. Then $\mathbf{W}^{1}(f)\leq\frac{2}{\pi}+O(\varepsilon)$.

3 Bonami’s lemma

The next theorem, due to Bonami [Bon70], states that low degree multilinear polynomials of Rademachers are reasonable random variables (this is sometimes known as $(4,2)$-hypercontractivity).

Proof. We proceed by induction on $n$. If $n=0$ then $f$ is the constant and the inequality holds trivially for all $d$. For the inductive step, let

Notice that $g$ has degree at most $d$, $h$ has degree at most $d-1$, and both are polynomials in $n-1$ variables. Notice also that the random variable $x_{n}$ is independent of both $g$ and $h$. Therefore, we have:

where we used independence for the second equality. Now note that $\operatorname{{\bf E}}[x_{n}]=\operatorname{{\bf E}}[x_{n}^{3}]=0$, $\operatorname{{\bf E}}[x_{n}^{2}]=\operatorname{{\bf E}}[x_{n}^{4}]=1$, and $\operatorname{{\bf E}}[g^{2}h^{2}]\leq\sqrt{\operatorname{{\bf E}}[g^{4}]}\sqrt{\operatorname{{\bf E}}[h^{4}]}$ by Cauchy-Schwarz. Therefore,

and so we have shown that $\operatorname{{\bf E}}[f^{4}]\leq 9^{d}\cdot\operatorname{{\bf E}}[f^{2}]^{2}$.

KKL and quasirandomness

Open Problem: Prove that among all functions $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ with $\deg(f)\leq d$, the quantity $\sum_{i=1}^{n}\hat{f}(i)$ is maximized by $\mathsf{MAJ}_{d}$. Less ambitiously, show $\sum_{i=1}^{n}\hat{f}(i)=O(\sqrt{\deg(f)})$.

We begin by proving the $\rho=1/3$ case of the small set expansion theorem: let $A\subseteq\{-1,1\}^{n}$ be a set of density $\alpha=|A|\cdot 2^{-n}$, and ${\bf 1}_{A}:\{-1,1\}^{n}\to\{0,1\}$ be its indicator function. We will need the following variant of Bonami’s lemma; its proof is identical to that of Theorem 43.

Theorem 44 is a special case of the hypercontractivity inequality [Bon70, Gro75, Bec75]: if $1\leq p\leq q\leq\infty$ and $\rho\leq\sqrt{\frac{p-1}{q-1}}$, then $\|T_{\rho}f\|_{q}\leq\|f\|_{p}$.

Proof. We will need a corollary of Theorem 44 that will also be useful for us when proving the KKL theorem in the next section: $\|T_{1\sqrt{3}}f\|_{2}^{2}\leq\|f\|_{4/3}^{2}$. To see that this holds, we check that

Here (3.1) is by Hölder’s inequality and (7) by applying Theorem 44 to $T_{1/\sqrt{3}}f$; dividing both sides by $\|T_{1/\sqrt{3}}f\|_{2}$ yields the claim. Applying this corollary to $f={\bf 1}_{A}$ completes the proof:

Here the second equality is an application of Parseval’s, and the final uses the fact that ${\bf 1}_{A}$ is $\left\{0,1\right\}$-valued.

2 Kahn-Kalai-Linial

This bound on the maximum influence is tight for the Ben-Or Linial TRIBES function [BL89]: the $2^{k}$-way OR of $k$-way AND’s of disjoint sets of variables (so $n=k\cdot 2^{k}$). We remark that while Corollary 47 only gives a $\log(n)$ improvement over the $1/n$ bound that follows directly from the Poincaré inequality, this factor makes a crucial difference in many applications (e.g. it is the crux of Khot and Vishnoi’s [KV05] counter-example to the Goemans-Linial conjecture [Goe97, Lin02]).

Let $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ be a balanced, monotone function viewed as a voting scheme. Both candidates can bias the outcome of the election in their favor to 99% probability by bribing a O\big{(}\frac{1}{\log(n)}\big{)} fraction of voters.

3 Dictator versus Quasirandom tests

A few prototypical quasirandom functions are the constants $\pm 1$ (these are $(0,0)$-quasirandom), the majority function (($O(\frac{1}{\sqrt{n}}),0$)-quasirandom), and large parities $\chi_{S}$ ($(1-\delta)^{|S|-1},0)$-quasirandom). Unbiased juntas, and dictators in particular, are prototypical examples of functions far from quasirandom. The next proposition states that even functions far from being quasirandom can only have a small number of variables with large noisy influence:

It remains to check that $|S|\cdot(1-\delta)^{|S|-1}\leq 1/\delta$ for any $S\subseteq[n]$: to see this holds, note that $(1-\delta)^{|S|-1}\leq(1-\delta)^{i-1}$ for any $i\leq|S|$, and so summing over $i$ from $1$ to $|S|$ gives us $|S|\cdot(1-\delta)^{|S|-1}\leq\sum_{i=1}^{|S|}(1-\delta)^{i-1}\leq\sum_{i=1}^{\infty}(1-\delta)^{i-1}=1/\delta$. We have shown that $\varepsilon\cdot|J|\leq(1/\delta)\cdot\operatorname{{\bf Var}}(f)\leq 1/\delta$, and the proof is complete.

Consider the problem of testing dictators: given blackbox access to a boolean function $f$, if $f$ is a dictator the test accepts with probability 1, and if $f$ is $\varepsilon$-far from any of the $n$ dictators it accepts with probability $1-\Omega(\varepsilon)$. Implicit in Kalai’s proof of Arrow’s impossibility theorem (Theorem 35) is a 3-query test that comes close to achieving this:

As we will see on Saturday, for applications to hardness of approximation (UGC-hardness in particular) it suffices to design a test that distinguishes dictators from $(\varepsilon,\varepsilon)$-quasirandom functions, instead of one that distinguishes dictators from functions $\varepsilon$-far from dictators.

Let $0\leq s<c\leq 1$. A $(c,s)$ dictator versus quasirandom test is defined as follows. Given blackbox access to a function $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$,

The test makes $O(1)$ non-adaptive queries to $f$.

If $f$ is a dictator, it accepts with probability at least $c$.

If $f$ is $(\varepsilon,\varepsilon)$-quasirandom, it accepts with probability at most $s+o_{\varepsilon}(1)$.

As we will see, often we will need to assume that $f$ is odd (i.e. $f(-x)=-f(x)$ for all $x\in\{-1,1\}^{n}$, or equivalently, $\hat{f}(S)=0$ for all even $|S|$). Let us consider the $\mathsf{NAE}$ test as a dictator versus quasirandom test, under the promise that $f$ is odd. We have seen that the test has perfect completeness (i.e. $c=1$), and now we determine the value of $s$. First note that since $f$ is odd,

Now let $f$ be a $(\varepsilon,\varepsilon)$-quasirandom function. Applying the Majority Is Stablest theorem (we will need a statement of it for functions with $\varepsilon$-small $\varepsilon$-noisy influences instead of $\varepsilon$-small regular influences), we have

We consider two more examples of dictator versus quasirandom tests and compute their $c$ and $s$ values: the $\rho$-noise test of S. Khot, G. Kindler, E. Mossel and R. O’Donnell [KKMO07], and J. Håstad’s ${\sf 3XOR}_{\delta}$ test [Hås01].

First note the $\rho$-noise test accepts $f=\mathsf{DICT}_{i}$ with probability $\frac{1}{2}+\frac{1}{2}\rho$, the probability that $x_{i}$ is not flipped in $y$. For soundness, let $f$ be an odd $(\varepsilon,\varepsilon)$-quasirandom function and note that

where once again we have used the Majority Is Stablest theorem along with Sheppard’s formula (the assumption that $f$ is odd is used in the application of the Majority Is Stablest theorem, which requires need $\operatorname{{\bf E}}[f]=0$). Different values of $\rho$ result in different $c$ versus $s$ ratios; for example, if $\rho=1/\sqrt{2}$ then $c=0.85$ and $s=0.75$.

Note that this is identical to the $\mathsf{BLR}$ linearity test, except with the noisy $x^{\prime}$ instead of $x$. Once again it is easy to see that dictators pass with probability $\frac{1}{2}+\frac{1}{2}(1-\delta)=1-\frac{\delta}{2}$, and it remains to analyze soundness:

Since the $\mathsf{3XOR}_{\delta}$ test accepts $(\varepsilon,\varepsilon)$-quasirandom functions with probability at most $\frac{1}{2}+\frac{1}{2}\sqrt{\varepsilon}$ (i.e. $s={\textstyle\frac{1}{2}}$), we have shown that it is a $(1-\frac{\delta}{2},{\textstyle\frac{1}{2}})$ dictator versus quasirandom test.

CSPs and hardness of approximation

We begin by noting that function testers can be viewed more generally as string testers: the tester is given blackbox access to a string $w\in\{-1,1\}^{N}$ (i.e. the truth-table of $f$, so $N=2^{n}$), and if $w$ satisfies some property $P_{1}\subseteq\{-1,1\}^{N}$ (e.g. dictatorship) the tester accepts with probability say at least $\frac{2}{3}$, and if $w$ satisfies some other property $P_{2}\subseteq\{-1,1\}^{N}$ (e.g. quasirandomness, far from dictatorship, etc.) it rejects with probability at least $\frac{2}{3}$.

We may view (non-adaptive) string testers simply as a list of instructions. For example,

with probability $p_{1}$ query $w_{1},w_{5},w_{10}$ and accept iff $\phi_{2}(w_{1},w_{5},w_{10})$

with probability $p_{2}$ query $w_{17},w_{4},w_{3}$ and accept iff $\phi_{8}(w_{17},w_{4},w_{3})$

with probability $p_{3}$ query $w_{2},w_{12},w_{7}$ and accept iff $\phi_{4}(w_{2},w_{12},w_{7})$

Here $\phi_{1},\phi_{2},\ldots$ are predicates $\{-1,1\}^{k}\to\left\{{\sf T},{\sf F}\right\}$. From this point-of-view, we see that a string tester naturally defines a weighted constraint satisfaction problem (CSP) over a domain of $N$ boolean variables, with the predicates $\phi_{i}$’s as constraints and the associated $p_{i}$’s as weights. The question of determining which string $w\in\{-1,1\}^{N}$ passes the test with highest probability is then equivalent to the question of finding an optimal assignment that satisfies the largest weighted fraction of predicates.

On Saturday Per will prove the following theorem establishing a formal connection between dictator versus quasirandom tests, the Unique-Label-Cover problem, and the hardness of approximating certain CSPs [Kho02, KR03, KKMO07, Aus08]:

Suppose there is an explicit $(c,s)$ dictator versus quasirandom test that uses predicates $\phi_{1},\ldots,\phi_{r}$. For every $\varepsilon>0$ there exists a polynomial-time reduction where:

The Unique Games Conjecture [Kho02] asserts that approximating the Unique-Label-Cover problem is NP-hard. Theorem 53 therefore says that assuming the UGC, for any constant $\varepsilon>0$ an explicit $(c,s)$ dictator versus quasirandom test implies the NP-hardness of $((s/c)+\varepsilon)$-factor approximating CSPs with constraints corresponding to the predicates used by the test.

Approximating MAX-3NAE-SAT to a factor of $0.91226\ldots+\varepsilon$ is NP-hard.

Approximating MAX-2LIN to a factor of $(1-\frac{1}{\pi}\arccos(\rho))/(\frac{1}{2}+\frac{1}{2}\rho)+\varepsilon$ is NP-hard.

Approximating MAX-3LIN to a factor of $(\frac{1}{2}+\varepsilon)$ is NP-hard.

2 Berry-Esséen

In this section we prove the Berry-Esséen theorem [Ber41, Ess42], a finitary version of the central limit theorem with explicit error bounds. Actually we will give a proof that only yields a polynomially weaker error bound, the upshot being that the proof is relatively simple and can be easily generalized to other settings (as we will see tomorrow, the Mossel-O’Donnell-Olezkiewicz proof of the invariance principle, an extension of the Berry-Esséen theorem to low-degree polynomials, is very similar in spirit). We will need Taylor’s theorem:

Note that if each $X_{i}$ is $B$-reasonable then $\sum_{i=1}^{n}\operatorname{{\bf E}}[X_{i}^{4}]\leq B\cdot\sum_{i=1}^{n}\sigma_{i}^{4}\leq B\cdot\max\left\{\sigma_{i}^{2}\right\}$.

Proof. We will view $\mathcal{G}$ as the sum of independent Gaussians $\mathcal{G}_{1}+\ldots+\mathcal{G}_{n}$, where each $\mathcal{G}_{i}\sim N(0,\sigma_{i}^{2})$. The proof proceeds by a hybrid argument, showing that only a small error is introduced whenever each $X_{i}$ in $\mathbf{X}$ is replaced by the corresponding Gaussian. More precisely, for each $i=0,\ldots,n$, we define the random variable $\mathbf{Z}_{i}:=\mathcal{G}_{1}+\ldots+\mathcal{G}_{i}+X_{i+1}+\ldots+X_{n}$; these $n+1$ random variables interpolate between $\mathbf{Z}_{0}=\mathbf{X}$ and $\mathbf{Z}_{n}=\mathcal{G}$. We will prove the inequality

for all $i\in[n]$, noting that this implies the theorem by the triangle inequality. Fix $i\in[n]$ and define the random variable ${\bf R}:=\mathcal{G}_{1}+\ldots+\mathcal{G}_{i-1}+X_{i+1}+\ldots+X_{n}$, so $\mathbf{Z}_{i-1}={\bf R}+X_{i}$ and $\mathbf{Z}_{i}={\bf R}+\mathcal{G}_{i}$. Our goal is therefore to bound $|\operatorname{{\bf E}}[\psi({\bf R}+\sigma_{i}\cdot X_{i})]-\operatorname{{\bf E}}[\psi({\bf R}+\sigma_{i}\cdot\mathcal{G}_{i})]|$. Applying Taylor’s theorem twice, we get

The same proof can be rewritten to show that if $\mathbf{Y}=Y_{1}+\ldots+Y_{n}$ is the sum of independent random variables satisfying $\operatorname{{\bf E}}[X_{i}]=\operatorname{{\bf E}}[Y_{i}]$, $\operatorname{{\bf E}}[X_{i}^{2}]=\operatorname{{\bf E}}[X_{i}^{2}]$, and $\operatorname{{\bf E}}[X_{i}^{3}]=\operatorname{{\bf E}}[X_{i}^{3}]$ (the matching moments property), then $|\operatorname{{\bf E}}[\psi(\mathbf{X})-\psi(\mathbf{Y})]|\leq\|\psi^{(4)}\|_{\infty}\cdot\sum_{i=1}^{n}\operatorname{{\bf E}}[X_{i}^{4}]+\operatorname{{\bf E}}[Y_{i}^{4}]$.

$\psi_{t,\lambda}(x)=\psi_{t}(x)=1$ if $x<t-\lambda$.

$\psi_{t,\lambda}(x)\in$ if $x\in[t-\lambda,t+\lambda]$.

$\psi_{t,\lambda}(x)=\psi_{t}(x)=0$ if $x>t+\lambda$.

We are now ready to prove a weak version of the Berry-Esséen theorem.

Proof. Since $\psi_{t+\lambda,\lambda}(x)=1$ for all $x<t$ we have $\operatorname{{\bf Pr}}[S\leq t]\leq\operatorname{{\bf E}}[\psi_{t+\lambda,\lambda}(S)].$ Now using the fact that $\|\psi^{(4)}_{t+\lambda,\lambda}\|_{\infty}=O(1/\lambda^{4})$, we apply Proposition 55 to get

Since $\psi_{t+\lambda,\lambda}(x)$ is at most 1 for all $x\leq t+2\lambda$ and 0 otherwise, we have

and so combining both error bounds gives us $\operatorname{{\bf E}}[\psi_{t+\lambda,\lambda}(S)]\leq\operatorname{{\bf Pr}}[\mathcal{G}<t]+O(B\tau/\lambda^{4})+O(\lambda)$. Arguing symmetrically for $\psi_{t-\lambda,\lambda}(x)$ gives us $|\operatorname{{\bf Pr}}[S<t]-\operatorname{{\bf Pr}}[\mathcal{G}<t]|=O(B\tau/\lambda^{4})+O(\lambda)$, and taking $\lambda=(B\tau)^{1/5}$ yields the claim.

Majority Is Stablest

Our definition of $\rho$-correlated Gaussians (Definition 39) extend naturally to higher dimensions: let $\vec{\mathcal{G}}$ and $\vec{\mathcal{G}^{\prime}}$ be independent standard $n$-dimensional Gaussians (i.e. $\vec{\mathcal{G}}=(\mathcal{G}_{1},\ldots,\mathcal{G}_{n})$ where each $\mathcal{G}_{i}\sim N(0,1)$ is an independent standard Gaussian, and similarly for $\vec{\mathcal{G}^{\prime}}$). Then $\vec{\mathcal{G}}$ and $\vec{\mathcal{H}}:=\rho\cdot\vec{\mathcal{G}}+\sqrt{1-\rho^{2}}\cdot\vec{\mathcal{G}^{\prime}}$ are $\rho$-correlated Gaussians. Just like in the one-dimension case, we have $\operatorname{{\bf E}}[\mathcal{G}_{i}\mathcal{H}_{i}]=\rho$ for all $i\in[n]$.

In this section we present Kindler and O’Donnell’s recent simple proof of (a special case of) Borell’s theorem [KO12]. We first introduce a few definitions and give a geometric interpretation of the theorem as an isoperimetric inequality in multidimensional Gaussian space.

2 Proof outline of MIST

In this section we sketch the proof of the Majority Is Stablest theorem (MIST):

Step 1. First consider $T_{1-\gamma}f$ for some small $\gamma>0$. Note that

$T_{1-\gamma}f$ is bounded since $T_{1-\gamma}$ is an averaging operator.

Step 3. We apply the invariance principle (an extension of the Berry-Esséen theorem to low-degree multilinear polynomials, proved in the next section) to $g$ and the test function $\mathsf{sqdist}_{}$ to bound

We are omitting a few details here since the invariance principle requires test functions to have uniformly bounded $4^{th}$ derivatives, just like in Berry-Esséen, so we actually need a smooth approximation of $\mathsf{sqdist}_{}$.

Here (13) holds since $\operatorname{{\bf E}}[g^{\prime}\cdot U_{\rho}g]=\operatorname{{\bf E}}[U_{\rho}g^{\prime}\cdot g]$, (13) is an application of Cauchy-Schwarz, and (14) uses the fact that $U_{\rho}$ is a contraction on $L^{2}$. Finally we note that $\operatorname{{\bf E}}[(g-g^{\prime})^{2}]$ is simply $\operatorname{{\bf E}}[\mathsf{sqdist}_{}(g)]$ and the proof is complete.

3 The invariance principle

In this section we prove (a special case of) the Mossel-O’Donnell-Olezkiewicz invariance principle [MOO10] for multilinear polynomials with low influences and bounded degree; in full generality the principle states that the distribution of such polynomials is essentially invariant for all product spaces. The crux of the proof is a low-degree analogue of Proposition 55; once again we proceed by a hybrid argument, showing that a small error is introduced whenever we replace a Rademacher random variable with a standard Gaussian. This is sometimes known as the Lindeberg replacement trick, first appearing in Lindeberg’s proof of the central limit theorem [Lin22]. There has been other work generalizing Lindeberg’s argument to the non-linear case [Rot75, Rot79, Cha06], but these results either yield weaker error bounds or require stronger conditions (e.g. worst-case influences rather than average-case).

Let $Q$ be a degree-$d$ multilinear polynomial $Q(u)=\sum_{|S|\leq d}c_{S}\prod_{i\in S}u_{i}$ and assume:

$\mathbf{X}=Q(X_{1},\ldots,X_{n})$ and $\mathbf{Y}=Q(\mathcal{G}_{1},\ldots,\mathcal{G}_{n})$ where $X_{1},\ldots,X_{n}$ are independent Rademachers and $\mathcal{G}_{1},\ldots,\mathcal{G}_{n}$ are independent standard Gaussians.

Then $|\operatorname{{\bf E}}[\psi(\mathbf{X})]-\operatorname{{\bf E}}[\psi(\mathbf{Y})]|\leq d\cdot 9^{d}\cdot C\cdot\tau$.

Proof. We first define a sequence of hybrid random variables that interpolate between $\mathbf{X}$ and $\mathbf{Y}$. For each $i=0,\ldots,n$ we define the random variable $\mathbf{Z}_{i}=Q(\mathcal{G}_{1},\ldots,\mathcal{G}_{i},X_{i+1},\ldots,X_{n})$, and note that $\mathbf{Z}_{0}=\mathbf{X}$ and $\mathbf{Z}_{n}=\mathbf{Y}$. As before, it suffices to prove

for all $i\in[n]$. Note that the overall claim follows from the above by telescoping, the triangle inequality, and the fact that

Here in the final inequality we have used our assumption that the coefficients are normalized to satisfy $\sum_{S\neq\emptyset}c_{S}^{2}=\operatorname{{\bf Var}}(\mathbf{X})=\operatorname{{\bf Var}}(\mathbf{Y})=1$. It remains to prove (15). Fix $i\in[n]$ and first express $Q(u_{1},\ldots,u_{n})$ as the sum of two polynomials $R$ and $S$, the former comprising all terms not containing $u_{i}$, and the latter the rest with $u_{i}$ factored out. That is,

where $R$ has degree at most $d$, and $S$ at most $d-1$ (note that if $d=1$ then $S$ is simply the coefficient $\alpha_{i}$ of $u_{i}$ in the linear polynomial $L$). Next define the random variables

and note that $\mathbf{Z}_{i-1}=\mathbf{R}+X_{i}\cdot\mathbf{S}$ and $\mathbf{Z}_{i}=\mathbf{R}+\mathcal{G}_{i}\cdot\mathbf{S}$. We bound $|\operatorname{{\bf E}}[\psi(\mathbf{R}+X_{i}\cdot\mathcal{S})]-\operatorname{{\bf E}}[\psi(\mathbf{R}+\mathcal{G}_{i}\cdot\mathbf{S})]|$ by considering their Taylor expansions:

$|\operatorname{{\bf E}}[\psi(\mathbf{Z}_{i-1})]-\operatorname{{\bf E}}[\psi(\mathbf{Z}_{i})]|$

Note that the first four terms cancel out since $X_{i}$ and $\mathcal{G}_{i}$ are independent of $\mathbf{S}$ and $\mathbf{R}$, and the random variables $X_{i}$ and $\mathcal{G}_{i}$ have matching first, second and third moments. Applying the bounds on the error terms given by Taylor’s theorem, we see that

where each $Y_{j}$ is either a Rademacher or standard Gaussian random variable, depending on whether $j<i$. We have shown that $|\operatorname{{\bf E}}[\psi(\mathbf{Z}_{i-1})]-\operatorname{{\bf E}}[\psi(\mathbf{Z}_{i})]|\leq C\cdot 9^{d}\cdot\tau_{i}^{2}$, and the proof is complete.

There exists a universal constant $C$ such that the following holds. Let $Q$ be a multilinear polynomial of degree $d$ over $\mathcal{G}_{1},\ldots,\mathcal{G}_{n}$, a sequence of independent standard Gaussians, and $\varepsilon>0$. Then

$\Delta_{\lambda,t}$ is smooth and $\|(\Delta_{\lambda,t})^{(r)}\|_{\infty}\leq B_{r}\cdot\lambda^{-r}$.

$\Delta_{\lambda,t}(x)=1$ for all $x\leq t-2\lambda$.

$\Delta_{\lambda,t}(x)\in$ for all $x\in(t-2\lambda,t+2\lambda)$.

$\Delta_{\lambda,t}(x)=0$ for all $x\geq t+2\lambda$.

We are now ready to prove the invariance principle.

Let $Q(u_{1},\ldots,u_{n})=\sum_{S\subseteq[n]}c_{S}\prod_{i\in S}u_{i}$ be a degree-$d$ multilinear polynomial and assume

$\mathbf{X}=Q(X_{1},\ldots,X_{n})$ and $\mathbf{Y}=Q(\mathcal{G}_{1},\ldots,\mathcal{G}_{n})$ where $X_{1},\ldots,X_{n}$ are independent Rademachers and $\mathcal{G}_{1},\ldots,\mathcal{G}_{n}$ are independent standard Gaussians.

Here (5.3) is again by the properties of $\psi$, this time using the fact that $\psi(x)=0$ for all $x\geq(t+2\lambda)+2\lambda$, and (19) is by Carbery-Wright. Choosing $\lambda=(10^{d}\cdot\tau)^{d/(4d+1)}$, we have shown that

A symmetric argument establishes the analogous lower bound on $\operatorname{{\bf E}}[\psi(Q(X))]$, and this completes the proof.

Testing dictators and UGC-hardness

Saturday, 3rd March 2012 Guest lecture by Per Austrin

The Unique-Label-Cover problem is a special case of the Label-Cover problem where the constraints $\pi_{e}:[L]\to[L]$ are not required to be permutations. In particular, in the Unique-Label-Cover problem assigning a label to a vertex necessarily determines the labels of all its neighbors, whereas this is not the case for the Label-Cover problem. Consequently, for Unique-Label-Cover the task of deciding whether there is an assignment that satisfies all the edges (i.e. distinguishing $\mathsf{opt}(\Psi)=1$ versus $\mathsf{opt}(\Psi)<1$) is easy: assume a label for a vertex $v$ and deduce the labels for the remaining vertices in a breadth-first fashion. If there is a conflict at some vertex we choose another label for $v$ and repeat the same process. If no consistent labeling can be found after iterating through all $L$ possible labels for $v$ then $\mathsf{opt}(\Psi)<1$; otherwise $\mathsf{opt}(\Psi)=1$. This is in sharp contrast to the situation for Label-Cover: it is known that for every $\varepsilon>0$ there is an $L$ such that it is NP-hard to distinguish between $\mathsf{opt}(\Psi)=1$ versus $\mathsf{opt}(\Psi)<\varepsilon$ where $\Psi$ is an instance of $L$-Label-Cover; we sometimes refer to this as the $(1,\varepsilon)$-hardness of Label-Cover.

The Unique Games Conjecture of S. Khot [Kho02] asserts that the Unique-Label-Cover problem is nevertheless very hard to approximate as soon as we move to almost-satisfiable instances.

For every $\varepsilon>0$ there exists an $L$ such that the it is NP-hard to distinguish between $\mathsf{opt}(\Psi)\geq 1-\varepsilon$ versus $\mathsf{opt}(\Psi)<\varepsilon$, where $\Psi$ is an instance of $L$-Unique-Label-Cover. Equivalently, for every $\varepsilon>0$ there exists an $L$ such that the $L$-Unique-Label-Cover problem is $(1-\varepsilon,\varepsilon)$-hard.

Today we will prove the following theorem showing how explicit $(c,s)$ dictator versus quasirandom tests yield Unique Games-based hardness results for certain constraint satisfaction problems [Kho02, KR03, KKMO07, Aus08]:

Suppose we have a $(c,s)$ dictator versus quasirandom using predicates from a set $T$. For every $L$ there exist a polynomial time reduction $R$ from $L$-Unique-Label-Cover to $\text{\sf MAX-CSP}(T)$ such that for every instance $\Psi$ of $L$-Unique-Label-Cover and every $\varepsilon>0$, there exists a $\delta>0$ satisfying

(Completeness) If $\mathsf{opt}(\Psi)\geq 1-\delta$ then $\mathsf{opt}(R(\Psi))\geq c-\varepsilon$.

(Soundness) If $\mathsf{opt}(\Psi)<\delta$ then $\mathsf{opt}(R(\Psi))<s+\varepsilon$.

First, a small catch: the dictator versus quasirandom test have to work not only for boolean functions but also for bounded functions $f:\{-1,1\}^{n}\to$. We may view any predicate $\phi:\{-1,1\}^{k}\to\{0,1\}$ as $\phi^{*}:^{k}\to$, where $\phi^{*}(y_{1},\ldots,y_{k}):=\operatorname{{\bf E}}[\phi(\boldsymbol{x_{1}},\ldots,\boldsymbol{x_{k}})]$, the expectation taken with respect to $\{-1,1\}$-valued random variables $\boldsymbol{x_{i}}$ satisfying $\operatorname{{\bf E}}[\boldsymbol{x_{i}}]=y_{i}$. It is easy to check that $\phi^{*}(x)=\phi(x)$ for all $x\in\{-1,1\}^{k}$, and in fact we have $\phi^{*}(y_{1},\ldots,y_{k})=\sum_{S\subseteq[k]}\hat{\phi}(S)\prod_{i\in S}y_{i}$. With this observation any tester for boolean functions using predicate $\phi$ can be extended to one for all bounded functions: instead of accepting iff $\phi(f(x_{1}),\ldots,f(x_{k}))=1$, the tester accepts with probability $\phi^{*}(f(x_{1}),\ldots,f(x_{k}))\in$.

With this caveat out of the way, we are now ready to describe the reduction $R$:

Let $\Psi$ be an instance of $L$-Unique-Label-Cover defined over a graph $G=(V,E)$. Suppose we have a $(c,s)$ dictator versus quasirandom test for functions $\{-1,1\}^{L}\to$ using $k$-ary predicates from a set $T$. Consider the following instance $R(\Psi)$ of $\textsf{MAX-CSP}(T)$: Variables. There will be $|V|\cdot 2^{L}$ variables: for each $u\in V$ we define $2^{L}$ boolean variables $\{Z_{u,x}\,:\,x\in\{-1,1\}^{L}\}$. Constraints. A random constraint will be sampled as follows: 1. Pick $u\in V$ uniformly. 2. Pick $k$ neighbors $v_{1},\ldots,v_{k}\in N(u)$ of $u$ uniformly independently. 3. Define $\widetilde{f_{u,v_{i}}}:=f_{v_{i}}(x\circ\pi_{u,v_{i}})$. 4. Pick $x_{1},\ldots,x_{k}\in\{-1,1\}^{L}$ according to the distribution over $k$-tuples induced by the tester, and set $y_{i}:=\widetilde{f_{u,v_{i}}}(x_{i})$. 5. Return the constraint $\phi(y_{1},\ldots,y_{k})=1$.