Making the long code shorter, with applications to the Unique Games Conjecture

Introduction

Khot’s Unique Games Conjecture [Kho02] (UGC) has been the focus of intense research effort in the last few years. The conjecture posits the hardness of approximation for a certain constraint satisfaction problem, and shows promise to settle many open questions in theory of approximation algorithms. Specifically, an instance $\Gamma$ of the Unique Games problem with $n$ variables and alphabet $\Sigma$ is described by a collection of constraints of the form $(x,y,\pi)$ where $\pi$ is a permutation over $\Sigma$. An assignment to $\Gamma$ is a mapping $f$ from $[n]$ to $\Sigma$, and $f$’s value is the fraction of constraints $(x,y,\pi)$ such that $f(y)=\pi(f(x))$. The Unique Games Conjecture is that for any $\varepsilon>0$, there is some finite $\Sigma$ such that it is NP hard to distinguish between the case that a Unique Games instance $\Gamma$ with alphabet $\Gamma$ has an assignment satisfying $1-\varepsilon$ fraction of the constraints, and the case that every assignment satisfies at most $\varepsilon$ fraction of $\Gamma$’s constraint.

Many works have been devoted to studying the plausibility of the UGC, as well as exploring its implications and obtaining unconditional results motivated by this effort. Tantalizingly, at the moment we have very little evidence for the truth of this conjecture. One obvious reason to believe the UGC is that no algorithm is known to contradict it, though that of course may have more to do with our proof techniques for algorithm analysis than actual computational difficulty. Thus perhaps the strongest evidence for the conjecture comes from results showing particular instances on which certain natural algorithms will fail to solve the problem. However, even those integrality gaps are quantitatively rather weak. For example, while Arora, Barak and Steurer [ABS10] showed a subexponential upper bound on an algorithm for the Unique Games and the related Small-Set Expansion problem, the hardest known instances for their algorithm only required quasipolynomial time [Kol10]. Similarly (and related to this), known integrality gaps for Unique Games and related problems do not rule out their solution by an $O(\log n)$-round semidefinite hierarchy, an algorithm that can be implemented in quasipolynomial (or perhaps even polynomial [BRS11]) time.

The long code has been a central tool in many of these works. This is the set of “dictator” functions mapping $\varmathbb F_{2}^{N}$ to $\varmathbb F_{2}$ that have the form $x_{1}\ldots x_{N}\mapsto x_{i}$ for some $i$. Many hardness reductions (especially from Unique Games) and constructions of integrality gap instances use the long code as a tool. However, this is also the source of their inefficiency, as the long code is indeed quite long. Specifically, it has only $N$ codewords but dimension $2^{N}$, which leads to exponential blowup in many of these applications.In this work, we introduce a different code, which we call the “short code”, that is exponentially more efficient, and can be used in the long code’s place in many of these applications, leading to significant quantitative improvements. In particular, we use our code to show instances on which the [ABS10] algorithm, as well as certain semidefinite hierarchies, require almost sub-exponential time, thus considerably strengthening the known evidence in support of the Unique Games Conjecture. Moreover, our results open up possibilities for qualitative improvements as well, in particular suggesting a new approach to prove the Unique Games Conjecture via an efficient alphabet reduction.

At the heart of the long code’s applications lie its connection with the noisy Hypercube. This is the weighted graph $H_{N,\varepsilon}$ whose vertices are elements in $\varmathbb F_{2}^{N}$ where a random neighbor of $x\in\varmathbb F_{2}^{N}$ is obtained by flipping each bit of $x$ independently with probability $\varepsilon$.This graph is closely related and has similar properties to the unweighted graph where we connect $x$ and $y$ if their Hamming distance is at most $\varepsilon N$. It is not too hard to show that the codewords of the long code correspond to the top eigenvectors of the noisy hypercube which also give the minimal bisections of the graph, cutting only an $\varepsilon$ fraction of edges. In addition, several converse results are known, showing that bisections (and more general functions) cutting few edges are close to these top eigenvectors (or dictatorships) in some sense. (One such result is the “Majority is Stablest” Theorem of [MOO05].) The inefficiency of the longcode is manifested in the fact that the number of vertices of the noisy cube is exponential in the number $N$ of its top eigenvectors.

Another way to describe the long code is that it encodes $x\in\varmathbb F_{2}^{n}$ by a binary vector $v_{x}$ of length $2^{2^{n}}$ where $v_{x}(f)=f(x)$ for every function $f:\varmathbb F_{2}^{n}\rightarrow\varmathbb F_{2}$. This view also accounts for the name “long code”, since one can see that this is the longest possible encoding of $x$ without having repeated coordinates. For every subset $\mathcal{D}$ of functions mapping $\varmathbb F_{2}^{n}$ to $\varmathbb F_{2}$, we define the $\mathcal{D}$-short code to be the code that encodes $x$ by a vector $v_{x}$ of length $|\mathcal{D}|$ where $v_{x}(f)=f(x)$ for every $f\in\mathcal{D}$. Note that this is a very general definition that encapsulates any code without repeated coordinates. For $d\in\varmathbb N$, we define the $d$-short code to be the the $\mathcal{D}$-short code where $\mathcal{D}$ is the set of all polynomials over $\varmathbb F_{2}^{n}$ of degree at most $d$. Note that the $1$-short code is the Hadamard code, while the $n$-short code is the long code. We use the name “short code” to denote the $d$ short code for $d=O(1)$. Note that the short code has $2^{n}$ codewords and dimension roughly $2^{n^{d}}$, and hence only quasipolynomial blowup, as opposed to the exponential blowup of the long code. Our main contribution is a construction of a “derandomized” noisy cube, which is a small subgraph of the noisy cube that enjoys the same relations to the short code (including a “Majority is Stablest” theorem) as the original noisy cube has to the long code. As a result, in many applications one can use the short code and the derandomized cube in place of the long code and the noisy cube, obtaining an exponential advantage. Using this approach we obtain the following results:

Small set expanders with many large eigenvalues

Our first application, and the motivation to this work, is a question of Arora, Barak and Steurer [ABS10]: How many eigenvectors with eigenvalue at least $1-\varepsilon$ can an $n$-vertex small set expander graph have? We say a graph is a small set expander (SSE) if all sufficiently small subsets of vertices have, say, at least $0.9$ fracton of their neighbors outside the set. [ABS10] showed an upper bound of $n^{O(\varepsilon)}$ on the number of large (i.e., greater than $1-\varepsilon$) eigenvalues of a small set expander. Arora et al. then observed that the subspace enumeration algorithm of [KT07, Kol10] for approximating small set expansion in an input graph takes time at most exponential in this number, which they then use to give an algorithm with similar running time for the Unique Games problem. Up to this work, the best lower bound was $\operatorname{polylog}(n)$, with the example being the noisy cube, and hence as far as we knew the algorithm of [ABS10] could solve the small set expansion problem in quasipolynomial time, which in turn might have had significant implications for the Unique Games problem as well. Our derandomized noisy cube yields an example with an almost polynomial number of large eigenvalues:

For every $\varepsilon>0$, there is an $n$-vertex small set expander graph with $2^{(\log n)^{\Omega(1)}}$ eigenvectors with corresponding eigenvalues at least $1-\varepsilon$.

Theorem 1 actually follows from a more general result connecting locally testable codes to small set expanders, which we instantiate with the Reed Muller code. See Section 2 for details.

Efficient integrality gaps

There is a standard semidefinite program (SDP) relaxation for the Unique Games problem, known as the “basic SDP” [KV05, RS09]. Several works have shown upper and lower bounds on the approximation guarantees of this relaxation, and for constant alphabet size, the relation between the alphabet size and approximation guarantee is completely understood [CMM06]. However, for unbounded alphabet, there was still a big gap in our understanding of the relation between the approximation guarantee and the number of variables. Gupta and Talwar [GT06] showed that if the relaxation’s value is $1-\varepsilon$, there is an assignment satisfying $1-O(\varepsilon\log n)$ fraction of constraints. On the other hand, Khot and Vishnoi [KV05] gave an integrality gap instance where the relaxation’s value was $1-1/\operatorname{poly}(\log\log n)$Throughout, for any function $f$, $\operatorname{poly}(f(n))$ denotes a function $g$ satisfying $g(n)=f(n)^{\Omega(1)}$. but the objective value (maximum fraction of constraints satisfied by any assignment) was $o(1)$. It was a natural question whether this could be improved (e.g., see [Lee11]), and indeed our short code allows us to obtain an almost exponential improvement:

There is an $n$-variable instance of Unique Games with objective value $o(1)$ but for which the standard semidefinite programming (SDP) relaxation has value at least $1-1/\operatorname{qpolylog}(n)$.For functions $f,g:\varmathbb N\to[0,\infty)$ we write $f=\operatorname{qpoly}(g)$ if $f=\exp(\operatorname{polylog}(g))$. That is, if there are constants $C>c>0$ such that for all sufficiently large $n$, $\exp((\log g(n))^{c})\leqslant f(n)\leqslant\exp((\log g(n))^{C})$. (Note that we allow $c<1$, and so $f=\operatorname{qpoly}(g)$ does not imply that $f>g$.) Similarly, we define $\operatorname{qpolylog}(g)=\operatorname{qpoly}(\log g)$ and write $f=\operatorname{qqpoly}(g)$ if $f=\exp(\exp(\operatorname{poly}(\log\log g)))$.

Integrality gaps for SDP hierarchies

Barak, Raghavendra and Steurer [BRS11] (see also [GS11]) showed that for every $\varepsilon>0$, $n^{\varepsilon}$ rounds of the $\mathsf{SA}$ hierarchy yields a non-trivial improvement over the basic SDP . The unique games conjecture predicts that this is optimal, in the sense that $n^{o(1)}$ rounds of any hierarchy should not improve the worst-case approximation ratio above the basic SDP.This is under the widely believed assumption that $\mathbf{NP}\nsubseteq\mathbf{Dtime}(\exp(n^{o(1)})$. However, this prediction is far from being verified, with the best lower bounds given by [RS09] (see also [KS09]) who showed instances that require $\log^{\Omega(1)}n$ rounds for the $\mathsf{LH}$ hierarchy, and $(\log\log n)^{\Omega(1)}$ rounds for the $\mathsf{SA}$ hierarchy. Moreover, these instances are known to be solvable in quasipolynomial time [Kol10] and in fact via $\operatorname{polylog}(n)$ rounds of the $\mathsf{SA}$ hierarchy [BRS11] . Thus prior work gave no evidence that the unique games problem cannot be solved in quasipolynomial time. In this work we obtain almost-exponentially more efficient integrality gaps, resisting $\operatorname{qpoly}(\log n)$ rounds of the $\mathsf{SA}$ hierarchy and $\operatorname{qqpoly}(n)$ rounds of the $\mathsf{LH}$ hierarchy. The latter is the first superlogarithmic SDP hierarchy lower bound for Unique Games for any SDP hierarchy considered in the literature.

For every $\varepsilon>0$ there is some $k=k(\varepsilon)$, such that for every $n$ there is an $n$ variable instance $\Gamma$ of Unique Games with alphabet size $k$ such that the objective value of $\Gamma$ is at most $\varepsilon$, but the value on $\Gamma$ of both $\operatorname{qpoly}(\log n)$ rounds of the $\mathsf{SA}$ hierarchy and $\operatorname{qqpoly}(n)$ rounds of the $\mathsf{LH}$ hierarchy is at least $1-\varepsilon$.

Alphabet reduction gadget

Khot, Kindler, Mossel and O’Donnel [KKMO04] used the long code to show an “alphabet reduction” gadget for unique games. They show how to reduce a unique game instance with some large alphabet $K$ to an instance with arbitrarily small alphabet. (In particular, they showed how one can reduce arbitrary unique games instances into binary alphabet instances, which turns out to be equivalent to the Max Cut problem.) However, quantitatively their result was rather inefficient, incurring an exponential in $K$ blowup of the instance. By replacing the long code with our “short code”, we obtain a more efficient gadget, incurring only a qusipolynomial blowup. One caveat is that, because the short code doesn’t support arbitrary permutations, this reduction only works for unique games instances whose constraints are affine functions over $\varmathbb F_{2}^{k}$ where $k=\log K$; however this class of unique games seems sufficiently rich for many applications.For example, because the multiplicative group of the field $\varmathbb F_{2^{n}}$ is cyclic, one can represent constraints of the form $x_{i}-x_{j}=c_{i,j}\pmod{2^{n}-1}$ as linear constraints over $\varmathbb F_{2}^{n}$ (i.e., constraints of the form $x_{i}=C_{i,j}x_{j}$ where $C_{i,j}$ is an invertible linear map over $\varmathbb F_{2}^{n}$).

Once again, our quantitative results are stronger than stated here, and as in [KKMO04], we obtain nearly optimal relation between the alphabet size $k$ and the soundness and completeness thresholds. In particular for $k=2$ our results match the parameters of the Max Cut algorithm of Geomans and Williamson. Our alphabet reduction gadget suggests a new approach to proving the unique games conjecture by using it as an “inner PCP”. For example, one could first show hardness of unique games with very large alphabet (polynomial or even subexponential in the number of variables) and then applying alphabet reduction. At the very least, coming up with plausible hard instances for unique games should be easier with a large alphabet.

The long code is also used as a tool in applications that do not involve the unique games conjecture. On a high level, there are two properties that make the long code useful in hardness of approximation: (i) it has a $2$ query test obtained from the noisy hypercube and (ii) it has many symmetries, and in particular one can read off any function of $x$ from the $x^{th}$ codeword. Our short code preserves property (i) but (as is necessary for a more efficient code) does not preserve property (ii), as one can only read off low degree polynomials of $x$ (also it is only symmetric under affine transformations). We note that if one does not care about property (i) and is happy with a $3$ query test, then it’s often possible to use the Hadamard code which is more efficient than the short code (indeed it’s essentially equal to the $d$-short code for $d=1$). Thus, at least in the context of hardness of approximation, it seems that the applications the short code will be most useful are those where property (i) is the crucial one.

Despite the name “short code”, our code is not the shortest possible code. While in our applications, dimension linear in the number of codewords is necessary (e.g., one can’t have a graph with more eigenvalues than vertices), it’s not clear that the dimension needs to be polynomial. It is a very interesting open question to find shorter codes that can still be used in the above applications.

Our techniques

To explain our techniques we focus on our first application— the construction of a small set expander with many eigenvalues close to $1$. The best way to view this construction is as a derandomization of the noisy hypercube, and so it will be useful to recall why the noisy hypercube itself is a small set expander.

Recall that the $\varepsilon$-noisy hypercube is the graph $H_{N,\varepsilon}$ whose vertex set is $\{\pm 1\}^{N}$ where we sample a neighbor of $x$ by flipping each bit independently with probability $\varepsilon$. The eigenvectors in $H_{N,\varepsilon}$ are given by the parity functions $\chi_{\alpha}(x)=\prod_{i\in\alpha}x_{i}$ for subsets $\alpha\subseteq[N]$ and the corresponding eigenvalues are $\lambda_{\alpha}=(1-2\varepsilon)^{|\alpha|}$. Thus $\lambda_{\alpha}$ only depends on the degree $|\alpha|$ of $\chi_{\alpha}$. In particular, the “dictator” functions $\chi_{\{i\}}(x)=x_{i}$ have eigenvalue $1-2\varepsilon$ and they correspond to balanced cuts (where vertices are partitioned based on the value of $x_{i}$) with edge expansion $\varepsilon$. As $\alpha$ increases, $\lambda_{\alpha}$ decreases, becoming a constant around $|\alpha|=O(1/\varepsilon)$.

Given $f:\{\pm 1\}^{N}\rightarrow\{0,1\}$ which is the indicator of a set $S$, its Fourier expansion $f(x)=\sum_{\alpha}\hat{f}(\alpha)\chi_{\alpha}(x)$ can be viewed as expressing the vector $f$ in the eigenvector basis. The edge expansion of $S$ is determined by the distribution of its Fourier mass; sets where most of the Fourier mass is on large sets will expand well. Given this connection, small-set expansion follows from the fact that the indicator functions of small sets have most of their mass concentrated on large Fourier coefficients. More precisely a set $S$ of measure $\mu$ has most of its Fourier mass on coefficients of degree $\Omega(\log(1/\mu))$. This follows from the so-called (2,4)-hypercontractive inequality for low-degree polynomials— that for every degree $d$ polynomial $f$,

for some $C$ depending only on $d$. (See Section 4.1 for the proof, though some intuition can be obtained by noting that if $f$ is a characteristic function of a set $S$ of measure $\mu=o(1)$ then $\operatorname*{\varmathbb{E}}[f^{2}]^{2}=\mu^{2}$ and $\operatorname*{\varmathbb{E}}[f^{4}]=\mu$ and hence Equation (2.1) shows that $f$ cannot be an $O(1)$-degree polynomial.)

By a “derandomized hypercube” we mean a graph on much fewer vertices that still (approximately) preserves the above properties of the noisy hypercube. Specifically we want to find a very small subset $\mathcal{D}$ of $\{\pm 1\}^{N}$ and a subgraph $G$ of $H_{N,\varepsilon}$ whose vertex set is $\mathcal{D}$ such that (i) $G$ will have similar eigenvalue profile to $H_{N,\varepsilon}$, and in particular have $N$ eigenvalues close to $1$ and (ii) $G$ will be a a small set expander. To get the parameters we are looking for, we’ll need to have the size of $\mathcal{D}$ be at most $\operatorname{qpoly}(N)$.

A natural candidate is to take $\mathcal{D}$ to be a random set, but it is not hard to show that this will not work. A better candidate might be a linear subspace $\mathcal{D}\subseteq\varmathbb F_{2}^{N}$ that looks suitably pseudorandom. We show that in fact it suffices to choose a subspace $\mathcal{D}$ whose dual $\mathcal{C}=\mathcal{D}^{\perp}$ is a sufficiently good locally testable code. (We identify $\varmathbb F_{2}^{N}$ with $\{\pm 1\}^{N}$ via the usual map $(b_{1},\ldots,b_{N})\mapsto((-1)^{b_{1}},\ldots,(-1)^{b_{N}})$.)

Our construction requires an asymptotic family of $[N,K,D]_{2}$ linear codes $\mathcal{C}\subseteq\varmathbb F_{2}^{N}$ where the distance $D$ tends to infinity. The code should have a $\varepsilon N$-query local tester which when given a received word $\alpha\in\varmathbb F_{2}^{N}$ samples a codeword $q$ of weight at most $\varepsilon N$ from a distribution $\mathcal{T}$ on $\mathcal{C}^{\perp}$ and accepts if $\langle\alpha,q\rangle=1$. The test clearly accepts codewords in $\mathcal{C}$, we also require it to reject words that are distance at least $D/10$ from every codeword in $\mathcal{C}$ with probability $0.49$. Given such a locally testable code $\mathcal{C}$, we consider the Cayley graphCayley graph are usually defined to be unweighted graph. However, the definition can be generalized straightforwardly to weighted graphs. $G$ whose vertices are the codewords of the dual code $\mathcal{D}=\mathcal{C}^{\perp}$ while the (appropriately weighted) edges correspond to the distribution $\mathcal{T}$. That is, a vertex of $G$ is a codeword $x\in\mathcal{D}$, while a random neighbor of $x$ is obtained by picking a random $q$ from $\mathcal{T}$ and moving to $x+q$.

Because $\mathcal{D}$ is a subspace, it is easy to show that the eigenvectors of $G$ are linear functions of of the form $\chi_{\alpha}(x)$ for $x,\alpha\in\varmathbb F_{2}^{N}$ (where if $\alpha\oplus\alpha^{\prime}\in\mathcal{C}$ then $\chi_{\alpha}$ and $\chi_{\alpha^{\prime}}$ are identical on $G$’s vertices). Moreover, from the way we designed the graph, for every $\alpha\in\varmathbb F_{2}^{n}$, the corresponding eigenvalue $\lambda_{\alpha}$ is equal to $\operatorname*{\varmathbb{E}}_{q\in\mathcal{T}}[(-1)^{\langle\alpha,q\rangle}]=1-2\operatorname*{\varmathbb{P}}_{\mathcal{T}}[\text{Test rejects }\alpha]$. This connection between the spectrum of $G$ and the local testability of $\mathcal{C}$ allows us to invoke machinery from coding theory in our analysis.

From this one can deduce that the eigenvalue spectrum of $G$ does indeed resemble the hypercube in the range close to $1$. In particular each $\chi_{\{i\}}(x)=x_{i}$ is a distinct eigenvector with eigenvalue $1-2\varepsilon$, and gives a bad cut in $G$ (where vertices are partitioned based on the value of $x_{i}$). On the other hand for any eigenvector $\chi$ of $G$, choose $\alpha$ of minimal weight such that $\chi=\chi_{\alpha}$. Now if $|\alpha|>D/10$ this means that the distance of $\alpha$ from $\mathcal{C}$ is at least $D/10$, which using the testing property implies that $\lambda_{\alpha}\leqslant 1-2\cdot 0.49=0.02$.

If we can show that indicator functions of small sets have most of their Fourier mass on such eigenvectors (with small eigenvalue), that will imply that small sets have good expansion. For small subsets of the hypercube, recall that this is proved using (2,4)-hpercontractivity for low-degree polynomials. The key observation is that the inequality

still holds for all polynomials $f$ of degree $d<D/4$. This is because the distance of $\mathcal{C}$ is $D$, hence the distribution of a random $x$ in $\mathcal{D}$ is $D$-wise independent, which means that the expectation of any polynomial of degree at most $D$ is equal over such $x$ and over a uniform $x$ in $\{\pm 1\}^{N}$. Thus (2.2) follows from (2.1), completing our proof.

We instantiate this approach with using for $\mathcal{C}$ the Reed Muller code consisting of polynomials in $n$ variables over $\varmathbb F_{2}$ of degree $n-d-1$. This is a code of distance $D=2^{d-1}$. We note that the degree $n-d-1$ and hence the rate of the code $\mathcal{C}$ are very high. The graph is over the codewords of $\mathcal{D}=\mathcal{C}^{\perp}$ that is itself the Reed Muller code of polynomials over $\varmathbb F_{2}^{n}$ of degree $d$. Our basic tester consists of selecting a random minimum weight codeword of $\mathcal{D}$.For many applications we amplify the success of this tester by selecting a sum of $t$ random such words, this corresponds to taking some power of the basic graph $\mathcal{G}$ described. Thus our graph $\mathcal{G}$ has as its vertices the $d$ degree polynomials over $\varmathbb F_{2}^{n}$ with an edge between every polynomials $p,q$ such that $p-q$ is a product of $d$ linearly-independent affine functions (as those are the minimal weight codewords in the Reed Muller code). We use the optimal analysis of Bhattacharyya, Kopparty, Schoenebeck, Sudan and Zuckerman [BKS+10] to argue about the local testability of $\mathcal{C}$ which is a high degree Reed Muller code. We should note that this test is very closely related to the Gowers uniformity test that was first analyzed in the work of Kaufman et al. [AKK+05], but our application requires the stronger result from [BKS+10].

We now briefly outline how we use the above tools to obtain more efficient versions of several other constructions such as alphabet reduction gadgets and integrality gaps for unique games and other problems.

To beign with, the graph we construct can be used to prove Theorem 2. That is, a construction of an $M$ variable instance $\Gamma$ of unique games where every assignment can satisfy at most a very small (say $1/100$) fraction of the constraints, but for which the standard semidefinite programming (SDP) relaxation has value of at least $1-1/\operatorname{qpoly}(\log M)$. The basic idea is to simply take the graph $\mathcal{G}$ we constructed above, and turn it into an instance of unique games by considering it to be the label extended graph of some unique games instance. We now elaborate a bit below, leaving the full details to Section 7. Recall that a Unique Games instance $\Gamma$ with $M$ variables and alphabet $\Sigma$ is described by a collection of constraints of the form $(x,y,\pi)$ where $\pi$ is a permutation over $\Sigma$. An assignment to $\Gamma$ is a mapping $f$ from $[M]$ to $\Sigma$, and $f$’s value is the fraction of constraints $(x,y,\pi)$ such that $f(y)=\pi(f(x))$. The label extended graph corresponding to $\Gamma$ is the graph $G_{\Gamma}$ over vertices $[M]\times\Sigma$ where for every constraint of the form $(x,y,\pi)$ and $\sigma\in\Sigma$ we add an edge between $(x,\sigma)$ and $(y,\pi(\sigma))$. It is not hard to see that an assignment of value $1-\varepsilon$ corresponds to a subset $S$ containing exactly $M$ of $G_{\Gamma}$’s vertices with small expansion (i.e., $\varepsilon$ fraction of the edges from $S$ leave the set). Thus if $G_{\Gamma}$ is an expander for sets of measure $1/|\Sigma|$ in $G_{\Gamma}$ then there is no nearly satisfying assignment for the unique games instance $\Gamma$. In our case, our graph $\mathcal{G}$ has the degree $d$ polynomials over $\varmathbb F_{2}^{n}$ as its vertices, and we transform it into a unique game instance whose variables correspond to degree $d$ polynomials without linear terms. The alphabet $\Sigma$ consists of all linear functions over $\varmathbb F_{2}^{n}$. We ensure that the graph $\mathcal{G}$ is the label extended graph of $\Gamma$ by setting the permutations accordingly: given a polynomial $p$ without a linear term, and a function $q$ that is a product of $d$ affine functions,Actually, to get better parameters, we take some power $t$ of $\mathcal{G}$, meaning that we consider $q$ that is a sum of $t$ functions that are products of $d$ affine functions. if we write $q=q^{\prime}+q^{\prime\prime}$ where $q^{\prime\prime}$ is the linear part of $q$, then we add a constraint of the form $(p,p+q^{\prime},\pi)$ where $\pi$ is the permutation that maps a linear function $r$ into $r+q^{\prime\prime}$. Some not too difficult calculations show that the top eigenvectors of our graph $\mathcal{G}$ yield a solution for the semidefinite program for $\Gamma$ (if the top eigenvectors are $f^{1},\ldots,f^{K}$, our vector solution will associate with each vertex $x$ the vector $(f^{1}(x),\ldots,f^{K}(x)$). By choosing carefully the parameters of the graph $\mathcal{G}$, the instance $\Gamma$ will have SDP value $1-1/\operatorname{qpoly}(\log M)$ where $M$ is the number of variables.

Derandomized Invariance Principle

While hypercontractivity of low degree polynomials suffices for some applications of the long code, other applications require other theorems, and in particular the invariance principle, shown for the hypercube by Mossel, O’Donnel and Oleszkiewicz [MOO05].Roughly speaking their invariance principle says that for “nice” functions $f$ on the vertices of the $N$-dimensional noisy hypercube, the distribution of $f(x)$ where $x$ is a random vertex is close to the distribution of $f(y)$ where $y$ consists of $N$ independent standard Gaussian random variables (appropriately extending $f$ to act on $\varmathbb R^{N}$). To obtain more efficient version of these applications, we first show that the same holds even when $x$ is a random vertex in our smaller subset of $N$-dimensional strings – the Reed–Muller codewords. Our central tool is a recent result by Meka and Zuckerman [MZ10] which derandomizes the invariance principle of Mossel et al. Our key insight is that taking a random Reed–Muller codeword can in fact be viewed as an instantiation of the Meka-Zuckerman generator, which involves splitting the input into blocks via a pairwise independent hash function, and using independent $k$-wise independent distributions in each block. This allows us to obtain a version of the “Majority is Stablest” theorem for our graph, which is the main corollary of the invariance principle that is used in applications of the longcode. See Section 5 for more details.

Efficient alphabet reduction

With the “Majority of Stablest” theorem in hand, proving Theorem 4 (efficient alphabet reduction for unique games), is fairly straightforward. The idea is to simply replace the noisy hypercube gadget used by [KKMO04] with our derandomized hypercube. This is essentially immediate in the case of alphabet reduction to binary alphabet (i.e., reduction to Max Cut) but requires a bit more work when reducing to a larger alphabet. See Section 6 for more details.

Efficient hierarchy integrality gaps

Our proof Theorem 3 again works by plugging in our short code / derandomized noisy hypercube in place of the long code in the previous integrality gap constructions [KV05, KS09, RS09]. Specifically, these constructions worked by starting with an integrality gap for unique games where the basic SDP yields $1-1/r$, and then composing it with an alphabet reduction gadget to obtain a new instance; Raghavendra and Steurer [RS09] showed that the composed instances resist $\operatorname{poly}(r)$ rounds of the $\mathsf{SA}$ hierarchy and $\exp(\operatorname{poly}(r))$ rounds of the $\mathsf{LH}$ hierarchy. These constructions used the noisy cube twice— both to obtain the basic unique games gap instance, and to obtain the alphabet reduction gadget. We simply plug in our short code in both usages— using for the basic unique games instance the efficient version obtained in Theorem 2, and for the alphabet reduction gadget the efficient version obtained in Theorem 4. (Luckily, our unique games instance has affine constraints and so is compatible with our alphabet reduction gadget.) The result essentially follows in a blackbox way from the analysis of [RS09]. See Section 8 for details.

Preliminaries

Let $G$ be a regular graph with vertex set $V$. For a subset $S\subseteq V$ we define the volume of $S$, denoted $\mu(S)$, to be $|S|/|V|$. We define the expansion of $S$, denoted $\operatorname{\Phi}(S)$, to be the probability over a random edge $(u,v)$, conditioned on $u\in S$ that $v\not\in S$. Equivalently (since $G$ is regular), $\operatorname{\Phi}(S)=G(S,V\setminus S)/(\deg_{G}\lvert S\rvert)$ where $\deg_{G}$ is the degree of the graph $G$ and $G(S,V\setminus S)$ is the number of edges going from $S$ to $V\setminus S$. Throughout, we denote the normalized adjacency matrix of a graph $G$ also by $G$, and refer to the spectrum of the adjacency matrix as the spectrum of the graph $G$. Note that by definition, every regular graph has maximum eigenvalue $1$. In this paper, we use expectation norms for real-valued functions. That is, for a function $f\colon S\to\varmathbb R$ and $p\geqslant 1$, we let $\lVert f\rVert_{p}\mathrel{\mathop{:}}=(\operatorname*{\varmathbb{E}}_{x\in S}|f(x)|^{p})^{1/p}$.

Many of the unique games instances that appear in this work belong to a special subclass of unique games, namely $\varmathbb F_{2}^{n}\textsc{-Max-2Lin}$ instances defined below.

Given a group $\mathcal{H}$, an $\mathcal{H}\textsc{-Max-2Lin}$ instance consists of a system of linear equations over the group $\mathcal{H}$ where each equation is of the form $x_{i}-x_{j}=c_{ij}$ for some $c_{ij}\in\mathcal{H}$.

Let $\mathcal{C}$ be an $[N,K,D]_{2}$ code, that is, $\mathcal{C}$ is a $K$-dimensional linear subspace of $\varmathbb F_{2}^{N}$ with minimum distance $D$ ($=\min\{{\sf wt}(x):x\in\mathcal{C}\}$). (In this paper, we are mostly interested in the extremely high rate regime when $H=N-K$ is very small compared to $N$ and are happy with $D$ being some large constant.) Let $\Delta(x,y)\in\{0,\ldots,N\}$ denote Hamming distance between $x,y\in\varmathbb F_{2}^{N}$. For $\alpha\in\varmathbb F_{2}^{N}$ and a code $\mathcal{C}$ we define

We say a distribution $\mathcal{T}$ over $\varmathbb F_{2}^{N}$ is a canonical tester for $\mathcal{C}$ if every vector in the support of the distribution $\mathcal{T}$ is a codeword $q\in C^{\bot}$. The query complexity of $\mathcal{T}$ is the maximum weight of a vector in its support. The tester’s soundness curve $s_{\mathcal{T}}\colon\varmathbb N\to$ is defined as

Similarly, we denote the rejection probability of $\mathcal{T}$ for a vector $\alpha\in\varmathbb F_{2}^{N}$ by $s_{\mathcal{T}}(\alpha)=\operatorname*{\varmathbb{P}}_{{q\sim\mathcal{T}}}\left\{\langle\alpha,q\rangle=1\right\}$. We let the query probability $\tau\in$ of a tester be the expected fraction of queried coordinates, that is, $\tau=\operatorname*{\varmathbb{E}}_{q\sim\mathcal{T}}{\sf wt}(q)/N$. We say that a tester $\mathcal{T}$ with query probability $\tau$ is smooth if for any coordinate $i\in[N]$, $\operatorname*{\varmathbb{P}}_{{q\sim\mathcal{T}}}\left\{q_{i}=1\right\}=\tau$ and we say it is $2$-smooth if in addition, for any two distinct coordinates $i\neq j$, $\operatorname*{\varmathbb{P}}_{{q\sim\mathcal{T}}}\left\{q_{i}=q_{j}=1\right\}=\tau^{2}$.

Finally, the following simple lemma gives some estimates for rejection probabilities of vectors for smooth testers.

If $\mathcal{T}$ is a smooth canonical tester with query probability $\tau$, then $s_{\mathcal{T}}(\alpha)\leqslant\Delta(\alpha,\mathcal{C})\cdot\tau$ for every vector $\alpha\in\varmathbb F_{2}^{N}$. Furthermore, if $\mathcal{T}$ is $2$-smooth, then $s_{\mathcal{T}}(\alpha)\geqslant(1-\gamma)\cdot\Delta(\alpha,\mathcal{C})\cdot\tau$ for every vector $\alpha\in\varmathbb F_{2}^{N}$ with $\Delta(\alpha,\mathcal{C})\tau\leqslant\gamma$.

Fix $\alpha\in\varmathbb F_{2}^{N}$ and let $k=\Delta(\alpha,\mathcal{C})$. Without loss of generality, we may assume ${\sf wt}(\alpha)=k$. By renaming coordinates, we may assume $\alpha_{1}=\ldots=\alpha_{k}=1$ and $\alpha_{k+1}=\ldots=\alpha_{N}=0$. Then, $s_{\mathcal{T}}(\alpha)\leqslant\operatorname*{\varmathbb{P}}_{{q\sim\mathcal{T}}}\left\{q_{1}=1\right\}+\ldots+\operatorname*{\varmathbb{P}}_{{q\sim\mathcal{T}}}\left\{q_{k}=1\right\}=k\cdot\tau$. On the other hand,

We review the prerequisites for Majority is Stablest and Unique Games related results in the corresponding sections.

Small Set Expanders from Locally Testable Codes

In this section we first use some known properties of hypercontractive norms to give a sufficient condition for graphs to be small set expanders. We then describe a generic way to construct graphs satisfying this condition from locally testable codes, proving Theorem 1.

Let $\mathcal{V}$ be a subspace of the set of functions from $V$ to $\varmathbb R$ for some finite set $V$. We denote by $P_{\mathcal{V}}$ the projection operator to the space $\mathcal{V}$. For $p,q\geqslant 1$, we define

We now relate this notion to small set expansion. We first show that a subspace $\mathcal{V}$ with bounded $(4/3)\to 2$ norm cannot contain the characteristic function of a small set:

Let $f:V\to\{0,1\}$ such that $\mu=\operatorname*{\varmathbb{E}}_{x\in V}[f(x)]$ then $\lVert P_{\mathcal{V}}f\rVert_{2}^{2}\leqslant\lVert\mathcal{V}\rVert_{4/3\to 2}^{2}\mu^{3/2}$.

Note that if $\lVert\mathcal{V}\rVert_{4/3\to 2}=O(1)$ and $\mu=o(1)$, then $\lVert P_{\mathcal{V}}f\rVert_{2}^{2}=o(\lVert f\rVert_{2}^{2})$, meaning the projection of $f$ onto $V$ is small. It is often easier to work with the $2\to 4$ norm instead of the $4/3\to 2$ norm. The following lemma allows us to use a bound on the former to bound the latter:

Let $f:V\to\varmathbb R$ and let $f^{\prime}=P_{V}f$. We know that

Dividing by $\lVert f\rVert_{2}=\operatorname*{\varmathbb{E}}[f^{2}]^{1/2}$ yields the result. ∎

We now conclude that graphs for which the top eigenspace has bounded $2\to 4$ norm are small set expanders. The lemma can be viewed qualitatively as a generalization of one direction of the classical Cheeger’s inequality relating combinatorial expansion to eigenvalue gap [Che70].

Let $G=(V,E)$ be regular graph, and $\mathcal{V}$ be the span of the eigenvectors of $G$ with eigenvalue larger than $\lambda$. Then, for every $S\subseteq V$,

Let $f$ be the characteristic function of $S$, and write $f=f^{\prime}+f^{\prime\prime}$ where $f^{\prime}=P_{\mathcal{V}}f$ (and so $f^{\prime\prime}=f-f^{\prime}$ is the projection to the eigenvectors with value at most $\lambda$). Let $\mu=\mu(S)$. We know that

Plugging this into (4.1) yields the result. ∎

2 Cayley graphs on codes

Motivated by the previous section, we now construct a graph for which the projection operator on to the top eigenspace is hypercontractive, i.e., has small $2\to 4$ norm, while also having high rank.

By Xoring the results of mulitple tests, one can let the soundness $s(k)$ tend to $\nicefrac{{1}}{{2}}$. Hence, if $s(k)$ is significantly larger than $\varepsilon$ (for appropriate $k$), one can obtain a graph with many large eigenvalues such that small enough sets have near-perfect expansion.

Note that if $\deg(\chi_{\alpha})<D/2$, then the minimum weight representative in $\alpha+\mathcal{C}$ is unique. (This uniqueness will allow us later to define low-degree influences of functions, see Section 5.)

We let $\lambda_{\alpha}$ denote the eigenvalue corresponding to character $\chi_{\alpha}$. The following observation connects the soundness of the canonical tester to the spectrum of $G$:

For any $\alpha\in\varmathbb F_{2}^{N}$, $\lambda_{\alpha}=1-2s(\alpha)$.

From standard facts about Cayley graphs, it follows that

We use this to show that many dictator cuts in $G$ which correspond to characters with degree $1$ have eigenvalues close to $1$. We let $\lambda_{i},\chi_{i}$ denote $\lambda_{\{i\}},\chi_{\{i\}}$. As noted before, for $D>2$ these are distinct characters.

We have $\lambda_{i}\geqslant 1-4\varepsilon$ for at least $N/2$ coordinates $[i]\in N$.

We have $\lambda_{i}=1-2\operatorname*{\varmathbb{P}}_{q\in\mathcal{T}}[q_{i}=1]$. Since ${\sf wt}(q)\leqslant\varepsilon N$ for every $q\in\mathcal{T}$,

So we can have $\operatorname*{\varmathbb{P}}_{q\in\mathcal{T}}[q_{i}=1]\geqslant 2\varepsilon$ for at most $N/2$ coordinates. ∎

Another immediate conseuqence of Lemma 4.5 is that large degree characters have small eigenvalues.

If $\deg(\chi_{\alpha})\geqslant k$, then $\lambda_{\alpha}\leqslant 1-2s(k)$.

Subspace Hypercontractivity

Given a function $f\colon\mathcal{C}^{\perp}\to\varmathbb R$ we can write it (uniquely) as a linear combination of the characters $\{\chi_{\alpha}\}_{\alpha\in\varmathbb F_{2}^{N}/\mathcal{C}}$

where $\hat{f}(\alpha)=\langle\chi_{\alpha},f\rangle$ is the Fourier transform of $f$ (over the abelian group $\mathcal{C}^{\bot}$).

We define the degree of $f$, denoted $\deg(f)$ to be $\max_{\alpha:\hat{f}(\alpha)\neq 0}\deg(\chi_{\alpha}).$ Note that $\deg(f+g)\leqslant\max\{\deg(f),\deg(g)\}$ and $\deg(fg)\leqslant\deg(f)+\deg(g)$. The following crucial observation follows immediately from the fact that $\mathcal{C}$ has minimum distance $D$.

The uniform distribution on $\mathcal{C}^{\perp}$ is $(D-1)$ wise independent. That is, for any $\alpha\in\varmathbb F_{2}^{N}$ such that $1\leqslant{\sf wt}(\alpha)<D$ we have $\operatorname*{\varmathbb{E}}_{p\in\mathcal{C}^{\perp}}[\chi_{\alpha}(p)]=0$.

The proof follows from the following two facts:

This bound on the $2\to 4$ norm is known to hold for true low degree polynomials under the uniform distribution on the hypercube by the Bonami-Beckner-Gross inequality [O’D08].

Combining the above bound with Lemma 4.3 we get that, if the local tester rejects sufficiently far codewords with high probability, then the resulting graph is a small set expander:

In particular, as $s(k)$ tends to $1/2$, the expansion of small sets tends to $1$. This corollary together with Corollary 4.6 completes the proof of Theorem 4.4.

3 A Canonical Tester for Reed Muller codes

There exists a constant $\eta_{0}>0$ such that for all $n,d$, and $k<\eta_{0}2^{d}$ the tester $\mathcal{T}_{\text{\sf RM}}$ described above has soundness $s(k)\geqslant(k/2)\cdot 2^{-d}$.

For a graph $G$ the continuous-time random walk on $G$ with parameter $t$ is described by the (stochastic) matrix $G(t)=e^{-t(I-G)}$. $G(t)$ and $G$ have the same eigenvectors and the eigenvalues of $G(t)$ are $\{e^{-t(1-\mu_{i})}\}$, where $\{\mu_{i}\}$ is the spectrum of $G$.

If $\deg(\chi_{\alpha})=k$, $\lambda_{\alpha}\leqslant\max(\rho^{k/2},\rho^{\mu_{0}2^{d}})$ where $\mu_{0}$ is an absolute constant.

For all $\delta<\delta_{0}$ for some constant $\delta_{0}$, if $\deg(\chi_{\alpha})=k<\delta^{2}2^{d+1}$, $\lvert\lambda_{\alpha}-\rho^{k}\rvert\leqslant\delta$.

For $k\leqslant 2^{d}$, $1-\mu_{\alpha}=k\tau\pm k^{2}\tau^{2}\geqslant k\tau/2$. Therefore, if $\deg(\chi_{\alpha})\leqslant 2^{d}$, $\lambda_{\alpha}=e^{-\varepsilon 2^{d+1}(1-\mu_{\alpha})}\leqslant e^{-\varepsilon 2^{d+1}k\tau/2}=\rho^{k/2}$. For $k>2^{d}$, by Corollary 4.7, $\mu_{\alpha}<1-2s(k)<C_{0}$ for a universal constant $C_{0}<1$. Therefore, $|\lambda_{\alpha}|<e^{-\varepsilon 2^{d+1}(1-C_{0})}=\rho^{(1-C_{0})2^{d+1}}<\rho^{\mu_{0}2^{d}}$ for $\mu_{0}<(1-C_{0})/2$.

We now prove the second bound. If $\varepsilon k^{2}\tau<\delta/10$, we have $\lambda_{\alpha}=\rho^{-k}(1\pm\delta)$ which implies $\lvert\lambda_{\alpha}-\rho^{k}\rvert\leqslant\delta$. Otherwise, if $\varepsilon k^{2}\tau\geqslant\delta/10$, our assumption $k<\delta^{2}2^{d+1}$ implies $\varepsilon k>1/(10\delta)$, hence $\varepsilon^{-\varepsilon k}\leqslant e^{-\frac{1}{10\delta}}\leqslant\delta/4$ for all $\delta<\delta_{0}$. For $k\leqslant 2^{d}$, $(1-\mu_{\alpha})=k\tau\pm k^{2}\tau^{2}\geqslant k\tau/2$. Hence $\lambda_{\alpha}\leqslant e^{-tk\tau/2}\leqslant e^{-\frac{1}{20\delta}}\leqslant\delta/4$ for all $\delta<\delta_{0}$. In this case, we get $\lvert\lambda_{\alpha}-\rho^{k}\rvert\leqslant|\lambda_{\alpha}|+|\rho^{k}|\leqslant\delta/2$.

For any $\varepsilon,\eta>0$, there exists a graph $G$ with $2^{(\log|G|)^{\frac{1}{d}}}$ eigenvalues larger than $1-\varepsilon$ for $d=\log(1/\varepsilon)+\log\log(1/\eta)+O(1)$ and where every set $S\subseteq G$ has expansion

Then, for every $\alpha\in\varmathbb F_{2}^{N}/\mathcal{C}$, $\deg(\chi_{\alpha})=1$, we have $s_{\tau}(\alpha)\geqslant 2^{-d}$. Hence $\mu_{\alpha}\geqslant 1-2^{-d+1}$, $\lambda_{\alpha}\geqslant e^{-t2^{-d+1}}=e^{-4\varepsilon}$. Therefore, there are at least $N=2^{(\log|G|)^{1/d}}$ eigenvalues which are larger than $1-4\varepsilon$.

The fact that our graph is a Cayley graph over $\varmathbb F_{2}^{n}$ has a potentially interesting implication for coding theory. By looking at the set of edge labels as the rows of a generating matrix for a code, we know that large Fourier coefficients corresponds to low weight codewords, and hence we get a code of dimension $m=\binom{n}{d}$ that has an almost exponential (i.e. $2^{n}$) number of codewords of low weight, but yet has small generalized Hamming distance in the sense that every subspace of codimension $\omega(1)$ contains a codeword of fractional Hamming weight $1-o(1)$. In particular by setting $d$ to be a function slowly tending to infinity we can get a linear code for which correcting from an $o(1)$ fraction of corruption errors requires an almost exponential list size, but for which one can correct a fraction approaching $1$ of erasure errors using a list of constant size. (The code obtained by taking all edges of our graph has an almost exponential blowup, but this can be reduced by subsampling the edges.)

Majority is Stablest over Codes

In this section we show an analogue of the “Majority is Stablest” result of Mossel et al. for the RM graph we constructed in the previous section; this will help us replace the noisy cube with the RM graph in various unique games gadgets.

For $\rho>0$, let $\Gamma_{\rho}:\to$ be the Gaussian noise stability curve defined as follows. For $\mu\in$, let $t\in\varmathbb R$ be such that $\operatorname*{\varmathbb{P}}_{g\leftarrow\mathcal{N}(0,1}[g<t]=\mu$. Then, $\Gamma_{\rho}(\mu)=\operatorname*{\varmathbb{P}}_{X,Y}[X\leqslant t,Y\leqslant t]$, where $(X,Y)\in\varmathbb R^{2}$ is a two-dimensional mean zero Gaussian random vector with covariance matrix \left(\begin{array}[]{cc}1&\rho\\ \rho&1\end{array}\right). We refer the reader to Appendix B in Mossel et al. [MOO05] for a more detailed discussion on $\Gamma_{\rho}$.

Let $P(x)=\sum_{I\subseteq[N]}a_{I}\prod_{i\in I}x_{i}$ be a $N$-variate multilinear polynomial $P:\varmathbb R^{N}\to\varmathbb R$. Define $\|P\|^{2}=\sum_{I}a_{I}^{2}$ and we say $P$ is $\varepsilon$-regular if for every $i\in[N]$, $\sum_{i\ni I}a_{I}^{2}\leqslant\varepsilon^{2}\cdot\|P\|^{2}$.

Throught this section, we let $T_{\rho,N}$ (we omit $N$ when the dimension is clear) denote the noisy hypercube graph with second largest eigenvalue $\rho$.

The following theorem shows that, in the context of noise stability, a regular function on the hypercube behaves like a function on Gaussian space.

Let $f\colon\{\pm 1\}^{N}\to$ be a function with $\operatorname*{\varmathbb{E}}f=\mu$. Suppose $\operatorname{Inf}_{i}^{\leqslant 10\log(1/\tau)}(f)\leqslant\tau$ for all $i\in[N]$. Then,

where $T_{\rho}$ is the Boolean noise graph with second largest eigenvalue $\rho$ and $\Gamma_{\rho}$ is the Gaussian noise stability curve.

We will need the following ingredient of the proof of Theorem 5.1 from [MOO05]. For $a,b\in\varmathbb R$, let $\zeta_{[a,b]}\colon\varmathbb R\to\varmathbb R_{+}$ be the functional $\zeta_{[a,b]}(x)=\max\{a-x,x-b,0\}^{2}$. For a real-valued random variable $X$, the expectation $\operatorname*{\varmathbb{E}}\zeta(X)$ is the $L_{2}^{2}$-distance of $X$ to the set of $[a,b]$-valued random variables (over the same probability space as $X$). We will be interested in the case $a=0$ and $b=1$. For this case, we abbreviate $\zeta=\zeta_{}$.

We will need the following corollary of that can handle functions that are not $$-valued as in the theorem but just close to$$-valued functions.

Let $f\colon\{\pm 1\}^{N}\to\varmathbb R$ be a function with $\operatorname*{\varmathbb{E}}f=\mu$ and $\operatorname*{\varmathbb{E}}\zeta\circ f\leqslant\tau$. Suppose $\operatorname{Inf}_{i}f^{\leqslant 30\log(1/\tau)}\leqslant\tau$ for all $i\in[N]$. Then,

where $T_{\rho}$ is the Boolean noise graph with second largest eigenvalue $\rho$ and $\Gamma_{\rho}$ is the Gaussian noise stability curve. (Here, we assume that $\tau$ is small enough.)

Let $f^{\prime}$ be the closest $$-valued function to$f$. Since$\lVert f-f^{\prime}\rVert\leqslant\sqrt{\tau}$, it follows that$\operatorname{Inf}^{\leqslant 20\log(1/\tau)}_{i}f^{\prime}\leqslant\tau+O(\sqrt{\tau})\ll\tau^{1/3}$and$\operatorname*{\varmathbb{E}}f^{\prime}\leqslant\operatorname*{\varmathbb{E}}f+\sqrt{\tau}$. Since$\langle f,T_{\rho}f\rangle\leqslant\langle f^{\prime},T_{\rho}f^{\prime}\rangle+O(\sqrt{\tau})$, the corollary follows by applying Theorem 5.1 to the function$f^{\prime}$. (Here, we also use that fact that$\Gamma_{\rho}(\mu+\sqrt{\tau})\leqslant\Gamma_{\rho}(\mu)+2\sqrt{\tau}$. See Lemma B.3 in [MOO05].) ∎

We remark that although we specialize to Reed–Muller codes in this section, most of the arguments generalize appropriately to arbitrary codes with good canonical testers modulo a conjecture about bounded independence distributions fooling low-degree polynomial threshold functions. We briefly discuss this in Section 5.3.

To state our version of “Majority is Stablest” we first extend the notion of influences to functions over Reed–Muller codes. For $n,d\in\varmathbb N$, $N=2^{n}$, let $\mathcal{C}\subseteq\varmathbb F_{2}^{N}$ be the Reed–Muller code $\text{\sf RM}(n,n-d-1)$ and let $\mathcal{C}^{\bot}\subseteq\varmathbb F_{2}^{N}$ be its dual $\text{\sf RM}(n,d)$. For the rest of this section we assume that a set of representatives corresponding to the minimum weight codeword in each coset is chosen for the coset space $\varmathbb F_{2}^{N}/\mathcal{C}$.