# Low degree almost Boolean functions are sparse juntas

Irit Dinur Weizmann Institute of Science, ISRAEL. email:
<EMAIL_ADDRESS>Yuval Filmus Technion — Israel Institute of
Technology, ISRAEL. email<EMAIL_ADDRESS>Prahladh Harsha Tata
Institute of Fundamental Research, INDIA. email<EMAIL_ADDRESS>
Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler
and Safra showed that low degree functions which are _almost_ Boolean are
close to juntas. Their result holds with respect to $\mu_{p}$ for every
_constant_ $p$. When $p$ is allowed to be very small, new phenomena emerge.
For example, the function $y_{1}+\cdots+y_{\varepsilon/p}$ (where
$y_{i}\in\\{0,1\\}$) is close to Boolean but not close to a junta.

We show that low degree functions which are almost Boolean are close to a new
class of functions which we call _sparse juntas_. Roughly speaking, these are
functions which on a random input look like juntas, in the sense that only a
finite number of their monomials are non-zero. This extends a result of the
second author for the degree 1 case.

As applications of our result, we show that low degree almost Boolean
functions must be very biased, and satisfy a large deviation bound.

An interesting aspect of our proof is that it relies on a local-to-global
agreement theorem. We cover the $p$-biased hypercube by many smaller
dimensional copies of the uniform hypercube, and approximate our function
locally via the Kindler–Safra theorem for constant $p$. We then stitch the
local approximations together into one global function that is a sparse junta.

##  1 Introduction

We study the structure of “simple” Boolean functions in the $p$-biased
hypercube, for all values of $p$, and in particular when $p(n)\to 0$. We
introduce a new class of functions that we call _sparse juntas_ which
generalize the standard juntas. Our main result is that every Boolean function
that has at most $\varepsilon$ of its $\ell_{2}^{2}$ mass above degree $d$, is
$O(\varepsilon)$ close to a degree $d$ sparse junta. Throughout the paper we
say that $f$ is $\varepsilon$-close to $g$ if
$\|{f-g}\|^{2}_{\mu_{p}}:=\operatorname*{\mathbb{E}}_{x\sim\mu_{p}}[(f(x)-g(x))^{2}]\leq\varepsilon$.

Nisan and Szegedy showed that Boolean functions that are exactly low degree
must be juntas [NS94], namely functions that depend on a constant number of
coordinates. Classical theorems in the analysis of Boolean functions describe
the structure of Boolean functions that are close to being “simple” functions,
where closeness is measured with respect to the uniform measure. Notions of
“simple” include functions that are noise-stable, or nearly low degree, or
have low total-influence [Fri98, FKN02, Bou02, KS02]. These results invariably
prove that the function depends on a few coordinates (a dictator or a junta).
For example, Friedgut, Kalai and Naor [FKN02] prove that a function whose
$\ell_{2}$ mass is almost all on Fourier levels $0,1$ must be a function that
depends on at most one variable (dictator, anti-dictator or constant).
Bourgain [Bou02] and Kindler and Safra [KS02] studied Boolean functions with
small mass on the Fourier levels above $d$. Kindler and Safra proved that such
functions are close to juntas.

######  Theorem 1.1 (Kindler–Safra [KS02, Kin03]).

Fix $d\geq 0$. For every $0<p<1$ there exists
$\varepsilon_{0}=\varepsilon_{0}(p,d)$ such that for every
$\varepsilon<\varepsilon_{0}$, if $f\colon\\{\pm 1\\}^{n}\to\\{\pm 1\\}$
satisfies $\|f^{>d}\|_{\mu_{p}}^{2}=\varepsilon$ then there exists a degree
$d$ function $g\colon\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ (which necessarily depends
on $O_{d}(1)$ coordinates) satisfying
$\|f-g\|_{\mu_{p}}^{2}\leq\varepsilon(1+O(\varepsilon^{1/4}(1/p)^{d}))$. In
particular, when $\varepsilon=o(p^{4d})$ and $\varepsilon\leq\varepsilon_{0}$,
$\|f-g\|^{2}=\varepsilon+o(\varepsilon)$.

The term junta was actually coined in an earlier paper of Friedgut who proved
that any Boolean function with small total influence is close to a junta
[Fri98].

Theorem 1.1 is a generalization to degree $d$ of the earlier theorem of
Friedgut, Kalai and Naor [FKN02] mentioned above, which states that functions
which are close to degree $1$ are close to dictators or constants. An
alternative way of saying this is that given a function $f$ with only
$\varepsilon$ fraction of its $\ell^{2}_{2}$-mass outside levels $0,1$, if
$f(x)\in\\{\pm 1\\}$ for all $x\in\\{\pm 1\\}^{n}$, then it must be
$O(\varepsilon)$-close to a function $g$ such that $\hat{g}(S)\in\\{0,-1,1\\}$
for all $S\subseteq[n]$ (it is easy to verify that such Boolean functions are
exactly the dictators, anti-dictators or the constant functions).

It is natural to wonder if the condition that the range is Boolean, namely
$f(x)\in\\{\pm 1\\}$ for all $x$, can be replaced by $f(x)\in A$ for all $x$,
for any arbitrary finite set $A\subset\mathbb{R}$. What can be said about such
a function that has $\varepsilon$ of its mass outside levels $0,1$? The answer
becomes more complicated as the size of $A$ grows, and the function need not
depend on just one variable, as can be seen by the function $f(x)=x_{1}+x_{2}$
that takes only three distinct values but depends on more than one variable.
Nevertheless, we show that a similarly flavored statement is true: if the
function $f$ takes values in a finite set $A\subset\mathbb{R}$ and has only
$\varepsilon$ mass outside levels $0,\ldots,d$, then there is a finite set
$A^{\prime}\subset\mathbb{R}$ such that $f$ is close to a function whose
Fourier coefficients belong to the set $A^{\prime}$.

######  Theorem 1.2 (A-valued functions with low degree).

Let $A\subset\mathbb{R}$ be a finite set, let $d\in\mathbb{N}$, and let
$f\colon\\{\pm 1\\}^{n}\to A$ be a function that has at most $\varepsilon$
fraction of its $\ell^{2}_{2}$-mass outside levels $0,\ldots,d$, that is,
$\|f^{>d}\|_{\mu_{1/2}}^{2}<\varepsilon$. Then $f$ is
$O_{A,d}(\varepsilon)$-close to a function $g$ of degree $d$ with Fourier
coefficients in a finite set $A^{\prime}\subset\mathbb{R}$.

This theorem is not difficult to prove given Theorem 1.1, but it turns out to
be quite useful. In fact, generalizing from Boolean to $A$-valued allows us to
give an new proof of Theorem 1.1 that proceeds by induction on the degree $d$
(see Section 8).

Having warmed up, we turn to the main focus of this paper, which is
understanding the structure of Boolean (or $A$-valued) functions that are
nearly degree $d$ in the $p$-biased hypercube. The $p$-biased hypercube is the
set $\\{\pm 1\\}^{n}$ equipped with the $\mu_{p}$ measure (given by
$\mu_{p}(x)=p^{(n+\sum_{i}x_{i})/2}(1-p)^{(n-\sum_{i}x_{i})/2}$). We think of
$p$ as being possibly very small, for example $p=1/\sqrt{n}$.

The theorem of Kindler and Safra [KS02] continues to hold under the $\mu_{p}$
measure, but the quality of the approximation deteriorates with $p$. Indeed,
the class of junta functions does not seem to be the correct class of
functions for approximating low degree functions that are $\mu_{p}$-almost
Boolean. This is demonstrated by the following simple example: Let
$f(x)=\sum_{i\in S}\frac{1-x_{i}}{2}$ be a degree $1$ function, and let $g$ be
the Boolean function closest to $f$. If $|S|=O(\sqrt{\varepsilon}/p)$ then $g$
is $\varepsilon$-close to $f$, and yet it depends on many coordinates. It
turns out that this example is canonical: in previous work [Fil16], the second
named author has proved that all functions that are nearly degree one, in
$\mu_{p}$, essentially look like this one.

The function $f$ considered above is very biased: with probability roughly
$1-\sqrt{\varepsilon}$, it is equal to zero. More generally, the result of
[Fil16] implies that if $\varphi$ is a degree 1 function which is
$\varepsilon$-close to Boolean then $\varphi$ is $O(\sqrt{\varepsilon})$-close
to a constant function. Still, one can hope for an even better approximation,
with error of $O(\varepsilon)$, and indeed this is possible: $\varphi$ is
$O(\varepsilon)$-close to a linear function similar to the function $f$
considered above (or its negation).

Generalizing this theorem to higher degrees requires coming up with a new
syntactic class of simple functions that are the good approximators for low
degree Boolean functions. As before, constants give an
$O(\varepsilon^{C})$-approximation for some $C<1$, a fact which comes as a
consequence of our main theorem (see Lemma 1.7), but our goal here will be to
find an even better approximation, on the order of $O(\varepsilon)$. The first
step is to move away from the Fourier basis whose basis functions depend on
$p$ and are thus non-canonical. Instead, we will rely on the _$y$ -expansion_
of $f$:

######  Definition 1.3 ($y$-expansion).

The _$y$ -expansion_ of a function $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ is
the unique expansion $f(x)=\sum_{S}\tilde{f}(S)y_{S}(x)$ where
$\\{y_{S}\\}_{S}$ is a basis of functions given by $y_{i}=\frac{1-x_{i}}{2}$
and for $S\subseteq[n]$, we define $y_{S}=\prod_{i\in S}y_{i}$.

The $y$-expansion is the standard expansion of $f$ as a multilinear polynomial
in $\\{0,1\\}$ variables instead of $\\{\pm 1\\}$ variables. We stress that
this is _not_ the Fourier expansion of $f$ (under $\mu_{1/2}$), which is its
expansion as a multilinear polynomial in $\\{\pm 1\\}$ input variables. The
$y$-expansion is better suited for working with $\mu_{p}$ for small $p$. The
result mentioned above [Fil16] states that any degree $1$ function that is
close to being Boolean in the $p$-biased hypercube can be approximated by a
function whose $y$-expansion coefficients are all in $\\{-1,0,1\\}$.

This motivates the following generalization:

######  Definition 1.4 (quantized polynomial).

Given a finite set $A\subset\mathbb{R}$, a function $f\colon\\{\pm
1\\}^{n}\to\mathbb{R}$ is said to be an _$A$ -quantized_ polynomial of degree
$d$ if all coefficients of the $y$-expansion of $f$ belong to $A$.

As part of our main result, stated below as Theorem 1.5, we show that for all
$p\leq 1/2$, a low degree function that is $\varepsilon$-close under $\mu_{p}$
to being $A$-valued, is close to an $A^{\prime}$-quantized polynomial for some
finite set $A^{\prime}=A^{\prime}(d,A)$. This can be nicely rephrased as
follows: For all $d\geq 0$ and sets $A$, there exists
$A^{\prime}=A^{\prime}(d,A)$ such that for all $p\leq 1/2$:

> _If a function has degree $\leq d$ and is $\varepsilon$-close under
> $\mu_{p}$ to an $A$-valued function, then its $y$-expansion is
> $O(\varepsilon)$-close to being $A^{\prime}$-quantized._

Observe that the $y$-expansion is important for making such a statement. It
could not be made for the Fourier expansion since the coefficients would have
to depend on $p$.

This generalizes Theorem 1.2 above since in the uniform $\mu_{\frac{1}{2}}$
setting a quantized polynomial that has bounded norm _must_ be a junta.
Indeed, substituting $y_{i}=\frac{1-x_{i}}{2}$ shows that if $|S|=d$ then
$\hat{f}(S)=(-1)^{d}2^{-d}\tilde{f}(S)$ (where $\tilde{f}(S)$ is the
coefficient of $y_{S}$ in the $y$-expansion of $f$), and so Parseval’s
identity shows that there is a constant number of non-zero $\tilde{f}(S)$ with
$|S|=d$. Removing them can only increase the $\ell_{2}$ norm by a constant,
and so applying the same reasoning inductively shows that $f$ is a junta.

Our main theorem gives a somewhat stronger syntactic characterization, showing
that $A$-valued functions with nearly low degree are close to being sparse
juntas. These are quantized polynomials that have an additional structural
property which we call bounded _branching factor_. The branching factor of a
quantized polynomial $g$ is best explained by considering the hypergraph whose
edges correspond to all non-zero coefficients in the $y$-expansion of $g$.
This hypergraph has branching factor $\rho=O(1/p)$ if for all subsets
$A\subseteq[n]$ and integers $r\geq 0$, there are at most $\rho^{r}$
hyperedges in $H$ of cardinality $|A|+r$ containing $A$.

While this is the syntactic definition, the meaning of having small branching
factor is that the function is “empirically” a junta, because a typical input
only leaves a constant number of monomials non-zero. This is why we call these
functions sparse juntas. Finally, we can state our main theorem:

######  Theorem 1.5 (Main).

For every positive integer $d$ and finite set $A\subset\mathbb{R}$, there
exists a finite set $A^{\prime}=A^{\prime}(d,A)$ such that the following
holds. For every $p\leq 1/2$ and $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ of
degree $d$ there exists a function $g\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ of
degree $d$ that satisfies the following properties for
$\varepsilon:=\operatorname*{\mathbb{E}}_{\mu_{p}}[\operatorname{dist}(f,A)^{2}]$:

  1. 1.

$\|f-g\|^{2}=O(\varepsilon)$.

  2. 2.

$\Pr[g\notin A]=O(\varepsilon)$

  3. 3.

$g$ is an $A^{\prime}$-sparse junta, that is, it is an $A^{\prime}$-quantized
polynomial of degree $d$ with branching factor $O(1/p)$.

  4. 4.

If $x\sim\mu_{p}$ then $g(x)$ is the sum of $O(1)$ coefficients of $g$ with
probability $1-O(\varepsilon)$.

We also show a converse to the above theorem (see Lemma 6.1) in the sense that
the second and third properties are a complete characterization of degree $d$
functions that are $O(\varepsilon)$-close to $A$ (i.e.,
$\mathbb{E}_{\mu_{p}}[\operatorname{dist}(f,A)^{2}]=O(\varepsilon)$).

As applications of our theorem we show a large deviation bound for degree $d$
functions close to a finite set $A$:

######  Lemma 1.6 (Large deviation bound).

Fix an integer $d$ and a finite set $A$. Suppose that
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$ with
respect to $\mu_{p}$ for some $p\leq 1/2$. For large $t$,

$\Pr[|f|\geq t]\leq\exp\left(-\Omega(t^{1/d})+O(\varepsilon/t^{2})\right).$

We also prove that such functions must by very biased:

######  Lemma 1.7 (Sparse juntas are very biased).

Fix a constant $d\geq 0$ and a finite set $A$. There exist constants
$C,\varepsilon_{0}>0$ such that for all $p\leq 1/2$ and
$\varepsilon\leq\varepsilon_{0}$, the following holds.

Suppose that $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function with
branching factor $O(1/p)$ such that $\Pr[g\notin A]=\varepsilon$. Then there
exists $a\in A$ such that $\Pr[g\neq a]=O(\varepsilon^{C}+p)$.

Combining this with our main theorem implies that if an $A$-valued function is
$\varepsilon$ close to degree $d$, it must be very biased.

#### A local-to-global aspect of the proof

Let us highlight an interesting aspect of the proof of our main theorem.
Previous works analyzing the structure of Boolean functions rely on
hypercontractivity. When $p\to 0$ the hypercontractive behavior breaks down,
and this is responsible for the deterioration of the approximation in Theorem
1.1. Our proof doesn’t go down this path, and instead proceeds by breaking up
the $p$-biased hypercube into many small sub-cubes that are obtained by
setting many variables to $0$ (using the $\\{0,1\\}$ convention for the
inputs). The measure on these sub-cubes becomes the uniform measure, and so we
are able to approximate $f$ locally on them using the classical Kindler-Safra
theorem, Theorem 1.2. This gives us a separate junta function $f_{S}$ on each
sub-cube $S$. Moving from local to global, we rely on a recent so-called
agreement theorem proven by the authors [DFH17] that gives us a single global
function $g$ that agrees with most of the local approximations (after ensuring
that the local pieces typically agree with each other).

To complete the proof of our main theorem, we use a crucial feature of the
agreement theorem proven in [DFH17], namely that _agreement is reached by
consensus_. This means that each coefficient of the $y$-expansion of $g$ is
chosen by picking the most “popular” value appearing in all relevant $f_{S}$.
In turns out that this feature guarantees that $g$ has branching factor
$O(1/p)$.

#### A new proof of the Kindler–Safra theorem

Our new proof of Theorem 1.1 demonstrates the power of our view of the theorem
as stating that if a low degree function is close to being quantized, then its
Fourier expansion is close to being quantized. Our inductive proof also makes
essential use of the generalization to $A$-valued, rather than just Boolean,
functions: even when starting with a Boolean function, $A$-valued functions
arise in the proof.

Given a function $f$ of degree $d$ which is close to a finite set $A$, we use
the theorem for degree $d-1$ (assumed to hold by induction) together with the
$A$-valued FKN theorem to show that the degree $d-1$ and degree $d$
coefficients are almost quantized (this is the heart of the proof). This
allows us to replace the two highest levels of $f$ with a quantized
polynomial, which must be a junta. Removing these two levels altogether, we
get an $A^{\prime}$-valued function for some $A^{\prime}$ depending on $A,d$.
Applying the theorem for degree $d-2$ completes the proof.

### Related work

Understanding the structure of Boolean functions that are simple according to
some measure such as being nearly low degree is a basic complexity goal.
Similar structure theorems such as the KKL theorem [KKL88], Friedgut’s junta
theorem [Fri98], and the FKN theorem [FKN02], have found numerous
applications. The analogous questions for the $p$-biased hypercube are
understood only to some extent, yet the questions are natural and play an
important role in several areas in combinatorics and the theory of
computation.

  * •

A major motivation for studying Boolean functions under the $\mu_{p}$ measure
comes from trying to understand the sharp threshold behavior of graph
properties, and of satisfiability of random $k$-CNF formulae.

A large area of combinatorics is concerned with understanding properties of
graphs selected from the random graph model of Erdős and Rényi, $G(n,p)$. A
graph property is described via a Boolean function $f$ whose $N=\binom{n}{2}$
input variables describe the edges of a graph and the function is $1$ iff the
property is satisfied. Selecting a graph at random from the $G(n,p)$
distribution is equivalent to selecting a random input to $f$ with
distribution $\mu_{p}$. The density of this function is the probability that
the property holds, and so its fine behavior as $p$ increases from $0$ to $1$
is the business of sharp threshold theorems. For many of the most interesting
graph properties, such as connectivity and appearance of a triangle, a phase
transition occurs for very small values of $p$ (corresponding to $p\approx
1/\sqrt{N}$). Friedgut and Kalai [FK96] used the theorem of Kahn, Kalai and
Linial [KKL88] to prove that _every_ monotone graph property has a narrow
threshold.

A famous theorem of Friedgut [Fri99] characterizes which graph and hypergraph
properties have sharp threshold. As an application, Friedgut establishes the
existence of a sharp threshold for the satisfiability of random $k$-CNF
formulae. This is done through analyzing the structure of $p$-biased Boolean
functions with low total influence, which corresponds to _not_ having a sharp
threshold. The same question was also studied by Bourgain [Bou99] and
subsequently by Hatami [Hat12], who proved that such functions must be
“pseudo-juntas” (see [O’D14, Chapter 10] for a discussion of these results).
We recommend the nice recent survey [BK17, Section 3] for a description of
some related questions and conjectures.

Our condition of having nearly degree $d$ is a strictly stronger condition
than having low total influence, and indeed our sparse juntas are in
particular pseudo-juntas. Unlike sparse juntas, the pseudo-junta property is
not syntactic (it does not define a class of functions, but rather a property
of the given function), and it is interesting to understand the relation
between pseudo-juntas and sparse juntas.

Friedgut conjectured that every monotone function that has a coarse threshold
is approximable by a narrow DNF, which is a function that can be written as
$f(x)=\max_{S:|S|\leq d}\tilde{f}(S)y_{S}(x)$. This is quite similar to our
class of sparse juntas (in fact, they coincide for degree $d=1$), except that
our functions are expressed as a sum of monomials rather than their maximum,
and thus we must restrict ourselves to functions with bounded branching
factor. The assumption of having a coarse threshold is weaker than having
nearly degree $d$, yet it is interesting whether our techniques can be applied
toward resolution of this conjecture.

  * •

Hardness of approximation: The $p$-biased hypercube has been used as a gadget
for proving hardness of approximation of vertex cover, where the relevant
regime is some constant $p<1/2$. Other variants of the hypercube have been
used or suggested as gadgets for proving inapproximability, including the
short code [BGH+15], the real code [KM13], and the Grassmann code [KMS17]. In
all of these, understanding the structure of Boolean functions with nearly low
degree seems crucial. In the Grassmann code, one considers subspaces of small
dimension inside a large-dimensional vector space. Some conjectures were made
in [DKK+16, DKK+17] regarding the structure of Boolean functions whose domain
is the set of subspaces and that have non-negligible mass on the space of
functions that corresponds to having low degree. Thinking of subspaces as
subsets of points, this is analogous to the $p$-biased case, when $p$ is very
small, on the order of $O(1/n)$. Toward understanding that question, it is
natural to first pursue such a study on the simpler model of the $p$-biased
hypercube for very small $p$, where the analysis is potentially easier since
the space is a product space.

  * •

Relatively recent work [KKM+17] proves that Reed–Muller codes achieve capacity
on the erasure channel, using the Bourgain–Kalai sharp threshold theorem for
affine-invariant functions [BourgainKalai]. The regime of this result is only
for codes with constant rate, and it seems that extending it to lower rates
would require understanding the structure of affine-invariant functions under
the $p$-biased measure for small $p$.

### Organization

The rest of the paper is organized as follows. We begin with a few
preliminaries in Section 2, which includes the agreement testing results. In
Section 3, we define the branching factor and discuss some of its properties.
We generalize the classical Kindler-Safra theorem to $A$-valued functions in
Section 4. We then prove the main result of the paper (Theorem 1.5) in Section
5. In Section 6, we prove the converse to our main result. We discuss some
applications in Section 7 and give an alternate proof to the classical
Kindler-Safra theorem in Section 8.

##  2 Preliminaries

We will need the following definitions:

  * •

We define $\operatorname{dist}(x,A)=\min_{y\in A}|x-y|$.

  * •

We define $\operatorname{round}(x,A)$ as an element in $A$ whose distance from
$x$ is $\operatorname{dist}(x,A)$.

  * •

For a function $f\colon\\{0,1\\}^{n}\to\mathbb{R}$ and a set $S\subseteq[n]$,
the function $f|_{S}\colon\\{0,1\\}^{S}\to\mathbb{R}$ results from
substituting zero to all coordinates outside of $S$.

  * •

For a function $f\colon\\{0,1\\}^{n}\to\mathbb{R}$, the support of its
$y$-expansion naturals corresponds to a hypergraph $H_{f}\subset 2^{[n]}$
which we sometimes refer to as the support of $g$.

  * •

For a set $S$, $\mu_{p}(S)$ is a distribution over subsets of $S$ in which
each element of $S$ is chosen independently with probability $p$.

  * •

The $L_{2}^{2}$ triangle inequality states that $(a+b)^{2}\leq
2(a^{2}+b^{2})$. It implies that

$\operatorname{dist}(x+y,A)^{2}=\min_{a\in A}(x+y-a)^{2}\leq\min_{a\in
A}[2(x-a)^{2}+2y^{2}]\leq 2\operatorname{dist}(x,A)^{2}+2y^{2}.$

  * •

For any $p,q\in(0,1)$ satisfying $2p-pq\leq 1$, the distribution $\mu_{p,q}$
is defined to be the distribution on pairs $S_{1},S_{2}$ in which each element
belongs only to $S_{1}$ with probability $p(1-q)$, only to $S_{2}$ with
probability $p(1-q)$, and to both $S_{1}$ and $S_{2}$ with probability $pq$.

We will need the following theorems.

######  Theorem 2.1 (Nisan–Szegedy).

If $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a degree $k$ function, then $f$ is a
$k2^{k-1}$-junta.

######  Theorem 2.2 ($(2,p)$ hypercontractivity).

Let $p\geq 2$, then for any function $f\colon\\{0,1\\}^{n}\to\mathbb{R}$ of
degree at most $k$, we have $\|f\|_{p}\leq(p-1)^{k/2}\cdot\|f\|_{2}$.

We also need the following result about quantization.

######  Lemma 2.3.

For every finite set $V$ and integer $d$ there exists a finite set $U$ such
that the following holds. Suppose that $\deg g_{1},\deg g_{2}\leq d$. If all
coefficients of the $y$-expansion of $g_{1},g_{2}$ belong to $V$, then all
coefficients of the $y$-expansion of $g_{1}g_{2}$ belong to $U$.

###### Proof.

Let $g:=g_{1}g_{2}$, and let $|A|\leq 2d$ (otherwise $\tilde{g}(A)=0$). Since
$y_{A_{1}}y_{A_{2}}=y_{A_{1}\cup A_{2}}$, we have

$\tilde{g}(A)=\bigcup_{A_{1}\cup
A_{2}=A}\tilde{g_{1}}(A_{1})\tilde{g_{2}}(A_{2}).$

The lemma follows from the fact that the sum contains at most $3^{2d}$ terms.
∎

###  2.1 Agreement testing

Agreement tests are a type of PCP tests that capture local-to-global
phenomena. Our proof of the main result uses an agreement test recently
analyzed by the authors [DFH17], which is an extension of the direct product
test to higher dimensions. In the standard direct product test, one is given a
ground set $[n]$ and an ensemble of local functions
$\\{f_{S}\\}_{S\subset[n]}$ containing a local function $f_{S}\colon
S\to\\{0,1\\}$ for each subset $S\subset[n]$. The direct product test is
specified by the distribution $\mu_{p,q}$ over pairs of sets $(S_{1},S_{2})$,
in which each element $i\in[n]$ is independently added to $S_{1}\cap S_{2}$
with probability $pq$, to $S_{1}\setminus S_{2}$ with probability $p(1-q)$, to
$S_{2}\setminus S_{1}$ with probability $p(1-q)$, and to neither set with
probability $1-(2p-pq)$. Here, we assume $p\leq 1/2$ and $q\in(0,1)$. The
direct product testing results [DG08, IKW12, DS14] state that if the local
functions agree most of the time, ie.,

$\Pr_{(S_{1},S_{2})\sim\mu_{p,q}}[f_{S_{1}}|_{S_{1}\cap
S_{2}}=f_{S_{2}}|_{S_{1}\cap S_{2}}]=1-\varepsilon,$

then there must exist a global function $G\colon[n]\to\\{0,1\\}$ that explains
most of the local functions:

$\Pr_{S\sim\mu_{p}}[f_{S}=G|_{S}]=1-O(\varepsilon).$

In recent work [DFH17], the authors extended this direct product to higher
dimensions, wherein the local functions are functions not only on the vertices
of $S$ but also on hyperedges supported by $S$, i.e.,
$f_{S}\colon\binom{S}{\leq d}\to\\{0,1\\}$ instead of $f_{S}\colon
S\to\\{0,1\\}$. Furthermore, they demonstrated that the function obtained by
majority decoding serves as a good candidate for the global function.
Formally:

######  Theorem 2.4 (Agreement theorem via majority decoding).

For every positive integer $d$ and alphabet $\Sigma$, there exists a constant
$p_{0}\in(0,1/2)$ such that for all $p\in(0,p_{0})$ and $q\in(0,1)$ and
sufficiently large $n$, the following holds. Let $\\{f_{S}\colon\binom{S}{\leq
d}\to\Sigma\mid S\in\\{0,1\\}^{n}\\}$ be an ensemble of functions satisfying

$\Pr_{S_{1},S_{2}\sim\mu_{p,q}}\left[f_{S_{1}}|_{S_{1}\cap S_{2}}\neq
f_{S_{2}}|_{S_{1}\cap S_{2}}\right]\leq\varepsilon.$

Then the global function $G\colon\binom{[n]}{\leq d}\to\Sigma$ defined by
plurality decoding (ie., $G(T)$ is the most popular value of $f_{S}(T)$ over
all $S$ containing $T$, chosen according to the distribution $\mu_{p}([n])$,
i.e.,
$\Pr_{S\sim\mu_{p}}[f_{S}(T)=G(T)]=\max_{\sigma}\Pr_{S\sim\mu_{p}}[f_{S}(T)=\sigma]$)
satisfies

$\Pr_{S\sim\mu_{p}}[f_{S}\neq G|_{S}]=O_{d,q}(\varepsilon).$

##  3 Branching factor

The analog of juntas for small $p$ are quantized functions with branching
factor $O(1/p)$. Let us start by formally defining this concept,

######  Definition 3.1 (branching factor).

For any $\rho\geq 1$, a hypergraph $H$ over a vertex set $V$ is said to have
_branching factor_ $\rho$ if for all subsets $A\subset V$ and integers $k\geq
0$, there are at most $\rho^{k}$ hyperedges in $H$ of cardinality $|A|+k$
containing $A$.

A function $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ is said to have branching
factor $\rho$ if the corresponding hypergraph $H_{g}$ (given by the support of
the $y$-expansion of $g$) has branching factor $\rho$.

In what sense is a function with branching factor $O(1/p)$ similar to a junta?
If $f$ is a junta and $y\sim\mu_{1/2}$, then $f(y)$ is the sum of a bounded
number of coefficients of the $y$-expansion of $f$. Let us call such a
coefficient _live_. In other words, the coefficients left alive by $S$ are all
$\tilde{f}(S)$ for which $y_{S}=1$.

We want a similar property to hold for a function $f$ with respect to an input
$y\sim\mu_{p}$ for small $p$. As a first approximation, we need the _expected_
number of live coefficients to be bounded. If $\deg f=d$ then the expected
number of live coefficients is

$\sum_{e=0}^{d}p^{e}N_{e},\text{ where }N_{e}=|\\{|S|=e:\tilde{f}(S)\neq
0\\}|.$

This sum is bounded if $N_{e}=O(1/p^{e})$ for all $e$. A drawback of this
definition is that it is not closed under substitution: if the expected number
of live coefficients of $f$ is bounded, this doesn’t guarantee the same
property for $f|_{y_{i}=1}$. For example, consider the function

$f=y_{0}(y_{1}+\cdots+y_{1/p^{2}}).$

While the expected number of live coefficients is $p^{2}/p^{2}=1$, if we
substitute $y_{0}=1$ then the expected number of live coefficients jumps to
$p/p^{2}=1/p$. The recursive nature of the definition of branching factor
guarantees that this cannot happen.

Functions with branching factor $O(1/p)$ also have several other desirable
properties, such as the large deviation bound proved in Section 7, and Lemma
3.4 below.

In the rest of this section we prove several elementary properties of the
branching factor. We start by estimating the branching factor of a sum or
product of functions.

######  Lemma 3.2.

Suppose that $\varphi_{1},\varphi_{2}$ have degree $d$ and branching factor
$\rho$. Then $\varphi_{1}\varphi_{2}$ and $\varphi_{1}+\varphi_{2}$ have
branching factor $O(\rho)$, where the hidden constant depends on $d$.

###### Proof.

The claim about $\varphi_{1}+\varphi_{2}$ is obvious, so let us consider
$\varphi=\varphi_{1}\varphi_{2}$. Given $A,e$, we have to show that the number
of non-zero coefficients in $\varphi$ which extend $A$ by $e$ elements is
$O(\rho^{e})$.

If $\tilde{\varphi}(B)\neq 0$ then $B=B_{1}\cup B_{2}$ for some $B_{1},B_{2}$
such that $\tilde{\varphi}_{i}(B_{i})\neq 0$. Let $B_{1}=A_{1}\cup C_{1}\cup
F$ and $B_{2}=A_{2}\cup C_{2}\cup F$, where $A_{1}\cup A_{2}=A$, and
$C_{1},C_{2},F$ are disjoint and disjoint from $A$, so that $|C_{1}\cup
C_{2}\cup F|=e$. Denote the sizes of $C_{1},C_{2},F$ by $c_{1},c_{2},f$.

There are $O(1)$ options for $A_{1},A_{2}$. Given $A_{1}$, there are at most
$\rho^{c_{1}+f}$ non-zero coefficients in $\varphi_{1}$ extending $A_{1}$ by
$c_{1}+f$ elements, and for each such extension, there are $O(1)$ options for
$F$. Given $A_{2},F$, there are at most $\rho^{c_{2}}$ non-zero coefficients
in $\varphi_{2}$ extending $A_{2}\cup F$ by $c_{2}$ elements. In total, we
deduce that for each of the $O(1)$ choices of $c_{1},c_{2},f$, the number of
non-zero coefficients extending $A$ by $e$ elements is
$O(1)\cdot\rho^{c_{1}+f}\cdot O(1)\cdot\rho^{c_{2}}=O(\rho^{e})$. ∎

As mentioned above, substitution has a bounded effect on the branching factor.

######  Lemma 3.3.

If $H$ has branching factor $\rho$ then $H|_{A=\emptyset}$ has branching
factor $2^{|A|}\rho$.

###### Proof.

It’s enough to prove the theorem when $A=\\{i\\}$. Let $B,k$ be given. We will
show that the number of hyperedges in $H|_{i=\emptyset}$ extending $B$ by $k$
elements is at most $(2\rho)^{k}$. If $k=0$ then this is clear. Otherwise, for
each such hyperedge $e$, either $e$ or $e+i$ belongs in $H$. The former case
includes all hyperedges of $H$ extending $B$ by $k$ elements, and the latter
all hyperedges of $H$ extending $B+i$ by $k$ elements. Since $H$ has branching
factor $\rho$, we can upper bound the number of hyperedges by
$2\rho^{k}\leq(2\rho)^{k}$. ∎

One of the crucial properties of functions with branching factor $O(1/p)$ is
that given that a certain $y$-coefficient is live, there is constant
probability that no other $y$-coefficient is live.

######  Lemma 3.4 (Uniqueness).

Suppose that $\varphi$ has branching factor $O(1/p)$ and degree $d=O(1)$,
where $p\leq 1/2$. For every $B$, the probability that $y_{B}=1$ and $y_{A}=0$
for all $A\nsubseteq B$ in the support of $\varphi$ is $\Omega(p^{|B|})$.

###### Proof.

Let $H$ be the hypergraph formed by the support of $\varphi$ (that is, $C$ is
a hyperedge if $\tilde{\varphi}(C)\neq 0$). Given that $y_{B}=1$, the
probability that $y_{A}=0$ for all $A\nsubseteq B$ is exactly equal to
$\Pr_{S\sim\mu_{p}}[(H|_{B=1}\setminus\\{\emptyset\\})|_{S}=\emptyset]$. Lemma
3.3 shows that $H|_{B=1}$ has branching factor $O(1/p)$, and so it has
$O(p^{-e})$ hyperedges of size $e$. The probability that each such edge
survives is $1-p^{e}$, and so the FKG lemma shows that given that $y_{B}=1$,
the probability that $y_{A}=0$ for all $A\nsubseteq B$ is at least

$\prod_{e=1}^{d}(1-p^{e})^{O(p^{-e})}=\Omega(1).$

This completes the proof, since $\Pr[y_{B}=1]=p^{|B|}$. ∎

##  4 Generalized Kindler–Safra theorem to A-valued functions

In this section, we prove the following generalization of Kindler-Safra to
quantized function (i.e, $A$-valued functions for some finite set $A$).
Everything that follows holds with respect to $\mu_{p}$ for _fixed_
$p\in(0,1)$. All hidden constants depend continuously on $p$.

######  Theorem 4.1.

For all integers $d$ and finite sets $A$ the following holds. If
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ and
$\varepsilon:=\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]$ then
$f$ is $O(\varepsilon)$-close to a degree $d$ function
$g\colon\\{0,1\\}^{n}\to A$.

We start with the following easy claim which is an easy consequence of the
Nisan-Szegedy theorem (Theorem 2.1).

######  Claim 4.2.

For all integers $d$ and finite sets $A$ there exists $M$ such that the
following holds. If $f\colon\\{0,1\\}^{n}\to A$ has degree $d$ then $f$
depends on at most $M$ coordinates.

###### Proof.

For all $a\in A$, define

$f_{a}=\prod_{b\neq a}\frac{f-b}{a-b}.$

The function $f_{a}$ has degree at most $d(|A|-1)$ and is Boolean, and so it
depends on at most $M_{0}$ coordinates. Since

$f=\sum_{a\in A}af_{a},$

we see that $f$ depends on at most $M_{0}|A|$ coordinates. ∎

Suppose we are dealing with degree $d$ functions which are close to some
finite set $A$ (ie.,
$\operatorname*{\mathbb{E}}[\operatorname{dist}(h,A)^{2}]=O(\varepsilon)$) and
we wish to show that $\|h\|^{2}=O(\varepsilon)$. The following trick (using
hypercontractivity Theorem 2.2) shows that is suffices to show
$\|h\|^{2}=O(\varepsilon^{\alpha})$ for some $\alpha<1$.

######  Claim 4.3.

Fix an integer $d$, a finite set $A$, and an exponent $\alpha<1$. If
$h\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(h,A)^{2}]=O(\varepsilon)$ and
$\|h\|^{2}=O(\varepsilon^{\alpha})$ then $\|h\|^{2}=O(\varepsilon)$.

###### Proof.

We can assume that $\varepsilon\leq 1$, since otherwise the theorem is
trivial. Similarly, we can assume that $0\in A$, since adding $0$ can only
decrease $\operatorname*{\mathbb{E}}[\operatorname{dist}(h,A)^{2}]$.

Let $z\in A$ denote the element of $A$ closest to $h$. Then

$O(\varepsilon)\geq\operatorname*{\mathbb{E}}[\operatorname{dist}(h,A)^{2}]\geq\operatorname*{\mathbb{E}}[h^{2}1_{z=0}]=\operatorname*{\mathbb{E}}[h^{2}]-\operatorname*{\mathbb{E}}[h^{2}1_{z\neq
0}].$

If $z\neq 0$ then $z=\Omega(1)$, and so $h^{2}=O(h^{k})$ for any integer
$k\geq 2$. In particular, for $k=\lceil 2/\alpha\rceil$, this shows that

$\operatorname*{\mathbb{E}}[h^{2}1_{z\neq
0}]=O(\operatorname*{\mathbb{E}}[h^{k}])=O(\|h\|_{k}^{k})=O(\|h\|_{2}^{k})=O(\varepsilon^{k(\alpha/2)})=O(\varepsilon),$

using hypercontractivity and $\varepsilon\leq 1$. It follows that
$\operatorname*{\mathbb{E}}[h^{2}]=O(\varepsilon)$. ∎

######  Corollary 4.4.

Fix an integer $d$, finite sets $A,B$, and an exponent $\alpha<1$. If
$f,g\colon\\{0,1\\}^{n}\to\mathbb{R}$ are degree $d$ functions satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=O(\varepsilon)$,
$\operatorname*{\mathbb{E}}[\operatorname{dist}(g,B)^{2}]=O(\varepsilon)$, and
$\|f-g\|^{2}=O(\varepsilon^{\alpha})$, then $\|f-g\|^{2}=O(\varepsilon)$.

###### Proof.

Let $h=f-g$. The $L_{2}^{2}$ triangle inequality shows that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(h,A-B)^{2}]=O(\varepsilon)$.
Also, $\|h\|^{2}=O(\varepsilon^{\alpha})$. The lemma therefore shows that
$\|h\|^{2}=O(\varepsilon)$. ∎

We now generalize the Kindler–Safra theorem to the $A$-valued setting, using
the decomposition of 4.2 and thus prove Theorem 4.1

###### Proof of Theorem 4.1.

Pick some arbitrary $a\in A$ and arbitrary constant $\varepsilon_{0}>0$. The
$L_{2}^{2}$ triangle inequality shows that $\|f-a\|^{2}=O(1+\varepsilon)$. If
$\varepsilon>\varepsilon_{0}$, the conclusion of the theorem is trivially
satisfied with $g=a$. Therefore from now on we assume that
$\varepsilon\leq\varepsilon_{0}$.

For $a\in A$, define

$f_{a}(x)=\prod_{b\neq a}\frac{f(x)-b}{a-b}.$

Also, let $y(x)\in A$ be the element in $A$ closest to $f(x)$, and let
$\delta(x):=(f(x)-y(x))$. Note $\operatorname{dist}(f(x),A)=|\delta(x)|$. We
will usually drop the argument $x$ from all these functions. Finally, define
$m=|A|-1$.

Our first goal is to bound $\operatorname{dist}(f_{a},\\{0,1\\})$ in terms of
$\delta$. Let $\delta_{0}>0$ be a small constant. We consider two cases. If
$y\neq a$ then

$\operatorname{dist}(f_{a},\\{0,1\\})\leq|f_{a}|=\frac{|\delta|}{|y-b|}\prod_{b\neq
a,y}\frac{|y-b+\delta|}{|a-b|}.$

If $|\delta|\leq\delta_{0}$ then
$\operatorname{dist}(f_{a},\\{0,1\\})=O(|\delta|)$, and otherwise
$\operatorname{dist}(f_{a},\\{0,1\\})=O(|\delta|^{m})$. If $y=a$ then

$\operatorname{dist}(f_{a},\\{0,1\\})\leq|f_{a}-1|=\left|\prod_{b\neq
a}\left|1+\frac{\delta}{a-b}\right|-1\right|.$

Once again, if $|\delta|\leq\delta_{0}$ then
$\operatorname{dist}(f_{a},\\{0,1\\})=O(|\delta|)$, and otherwise
$\operatorname{dist}(f_{a},\\{0,1\\})=O(|\delta|^{m})$.

We can now obtain a rough bound on
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{a},\\{0,1\\})^{2}]$ by
considering separately the cases $|\delta|\leq\delta_{0}$ and
$|\delta|>\delta_{0}$. The first case is simple:

$\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{a},\\{0,1\\})^{2}1_{|\delta|\leq\delta_{0}}]\leq
O(\operatorname*{\mathbb{E}}[\delta^{2}])=O(\varepsilon).$

For the second case, we use Cauchy–Schwartz and the bound
$\Pr[\delta^{2}\geq\delta_{0}^{2}]=O(\varepsilon)$ (recall $\delta_{0}$ is a
constant):

$\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{a},\\{0,1\\})^{2}1_{|\delta|\geq\delta_{0}}]\leq\sqrt{\operatorname*{\mathbb{E}}[\delta^{2m}]}O(\sqrt{\varepsilon}).$

Let $C:=2\max_{a\in A}|a|$. If $|f|\geq\max_{a\in A}|a|$ then clearly
$|\delta|\leq|f|$, and otherwise $|\delta|\leq|f|+\max_{a\in A}|A|\leq C$.
Therefore it always holds that $|\delta|\leq\max(C,|f|)$. This shows that

$\operatorname*{\mathbb{E}}[\delta^{2m}]\leq
C^{2m}+\operatorname*{\mathbb{E}}[f^{2m}]=O(1)+\|f\|_{2m}^{2m}.$

Since $\deg f=d$, we have $\|f\|_{2m}=O(\|f\|_{2})$. The $L_{2}^{2}$ triangle
inequality shows that $\|f\|_{2}^{2}=O(\max_{a\in A}|a|+\varepsilon)=O(1)$,
and in total this case contributes $O(\sqrt{\varepsilon})$. We conclude that

$\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{a},\\{0,1\\})^{2}]=O(\sqrt{\varepsilon}).$

The $L_{2}^{2}$ triangle inequality also allows us to bound
$\|f_{a}\|_{2}^{2}$ by $O(1)$, by writing it as a polynomial in $f$ and
bounding separately all the summands.

The Kindler–Safra theorem shows that $f_{a}$ is $O(\sqrt{\varepsilon})$-close
to a Boolean junta $g_{a}$ depending on the variables $J_{a}$. If $\deg
g_{a}>d$ then $\|f_{a}-g_{a}\|^{2}\geq\|g_{a}^{>d}\|^{2}=\Omega(1)$ (since
there are finitely many options for $g_{a}$, up to the choice of $J_{a}$), and
so $\varepsilon=\Omega(1)$. Choosing $\varepsilon_{0}$ appropriately, we can
assume that $\deg g_{a}\leq d$.

Define now $g=\sum_{a\in A}ag_{a}$, and note that this is an $A$-valued junta
of degree at most $d$. The $L_{2}^{2}$ inequality shows that

$\|f-g\|^{2}=\left\|\sum_{a\in A}a(f_{a}-g_{a})\right\|^{2}=O\left(\sum_{a\in
A}\|f_{a}-g_{a}\|^{2}\right)=O(\sqrt{\varepsilon}).$

The theorem now follows directly from Corollary 4.4 (with $\alpha=1/2$). ∎

##  5 Main result: sparse juntas

In this section, we prove our main result, an analog of the Kindler-Safra
theorem for all $p\in(0,1/2)$.

######  Theorem 5.1 (Restatement of Theorem 1.5).

For every $p\leq 1/2$ and $f\colon\\{0,1\\}^{n}\to\mathbb{R}$ of degree $d$
there exists a function $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ of degree $d$ that
satisfies the following properties for
$\varepsilon:=\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]$:

  1. 1.

$\|f-g\|^{2}=O(\varepsilon)$.

  2. 2.

$\Pr[g\notin A]=O(\varepsilon)$

  3. 3.

The coefficients of the $y$-expansion of $g$ belong to a finite set (depending
only on $d,A$).

  4. 4.

The support of $g$ has branching factor $O(1/p)$.

  5. 5.

If $x\sim\mu_{p}$ then $g(x)$ is the sum of $O(1)$ coefficients of $g$ with
probability $1-O(\varepsilon)$.

The following corollary (proved at the end of this section) for $A$-valued
functions which have light Fourier tails follows from the above the theorem.

######  Corollary 5.2.

Let $d\geq 0$ be any positive integer and $A\subseteq\mathbb{R}$ any finite
set. For every $p\leq 1/2$ and $F\colon\\{0,1\\}^{n}\to A$ there exists a
function $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ of degree $d$ that satisfies the
following properties for $\varepsilon:=\|F^{>d}\|^{2}$:

  1. 1.

$\|F-g\|^{2}=O(\varepsilon)$.

  2. 2.

$\Pr[F\neq g]=O(\varepsilon)$.

  3. 3.

All other properties of $g$ (alone) stated in the theorem.

Given $d$ and alphabet $A$, let $p_{0}$ be the constant given by the agreement
theorem Theorem 2.4. For the rest of this section, we fix the constant $d$,
set $A$ and $p_{0}$. All hidden constants will depend only on $d$ and $A$. For
all the prelimary claims till the proof of Theorem 5.1, we further assume that
$p\leq p_{0}$. Finally, as in the hypothesis of the theorem, we assume $f$ is
a function from $\\{0,1\\}^{n}$ to $\mathbb{R}$ of degree $d$ satisfying
$\operatorname*{\mathbb{E}}_{\mu_{p}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$

The main result of this section extends the generalized Kindler-Safra theorem
Theorem 4.1, which holds only for constant $p$, to all values of $p$ via the
agreement theorem Theorem 2.4. The idea is to consider, for each subset
$S\subset[n]$, a “restriction” of $f$ obtained by fixing the inputs outside
$S$ to be $0$. Namely, we define $f|_{S}:\\{0,1\\}^{S}\to\mathbb{R}$ by
$f|_{S}(x)=f(x\circ 0_{\bar{S}})$ where $x\circ 0_{\bar{S}}\in\\{0,1\\}^{n}$
is the input that agrees with $x$ on the coordinates of $S$ and is zero
outside of $S$. We will find an approximate structure for each $f|_{S}$, and
then stitch them together using the agreement theorem Theorem 2.4. We start by
applying the generalized Kindler-Safra theorem to $f|_{S}$ for subsets $S$
selected according to two constant values of $p$ (namely, $p=1/2$ and
$p=1/4$).

######  Claim 5.3.

For every set $S\subseteq[n]$, let

$\displaystyle\varepsilon_{S}:=\operatorname*{\mathbb{E}}_{\mu_{1/4}}[\operatorname{dist}(f|_{S},A)^{2}],$
$\displaystyle\delta_{S}:=\operatorname*{\mathbb{E}}_{\mu_{1/2}}[\operatorname{dist}(f|_{S},A)^{2}]$

Then
$\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}[\varepsilon_{S}]=\operatorname*{\mathbb{E}}_{S\sim\mu_{2p}}[\delta_{S}]=\varepsilon$,
and for every $S$ there exist $A$-valued degree $d$ juntas
$g_{S}\colon\\{0,1\\}^{S}\to A$ and $h_{S}\colon\\{0,1\\}^{S}\to A$ such that
$\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(f|_{S}-g_{S})^{2}]=O(\varepsilon_{S})$
and
$\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(f|_{S}-h_{S})^{2}]=O(\delta_{S})$.

###### Proof.

If $S\sim\mu_{4p}$ and $x\sim\mu_{1/4}(S)$ then $x\sim\mu_{p}$, and this
explains why
$\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}[\varepsilon_{S}]=\varepsilon$. The
fact that
$\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(f|_{S}-g_{S})^{2}]=O(\varepsilon_{S})$
follows from the generalized Kindler-Safra theorem Theorem 4.1. The proof of
$\operatorname*{\mathbb{E}}_{S\sim\mu_{2p}}[\delta_{S}]=\varepsilon$ and
$\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(f|_{S}-h_{S})^{2}]=O(\delta_{S})$. ∎

Towards applying the agreement theorem Theorem 2.4, we need to prove that the
collection of local juntas $\\{g_{S}\\}_{S}$ typically agree with each other.
We do so by showing that typically $g_{S_{1}}$ and $g_{S_{2}}$ agree on the
intersection of their domains with $h_{S_{1}\cap S_{2}}$. In the next claim,
we show that if the pair of sets $(S_{1},S_{2})$ are chosen according to the
distribution $\mu_{4p,1/2}$, then the two juntas $g_{S_{1}}$ and $g_{S_{2}}$
agree with $h_{S_{1}\cap S_{2}}$ with probability $1-O(\varepsilon)$. We will
then apply the agreement theorem using majority decoding to obtain a single
degree $d$ function $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ that explains most of
the juntas $g_{S}$.

######  Claim 5.4.

For every set $S\subseteq[n]$, let the $y$-expansion of the junta $g_{S}$
given in 5.3 be as follows:

$g_{S}=\sum_{\begin{subarray}{c}T\subseteq S\\\
|T|=d\end{subarray}}d_{S,T}y_{T}.$

For every $|T|\leq d$, let $d_{T}$ be the plurality value of $d_{S,T}$ among
all $S\supseteq T$ (measured according to $\mu_{4p}$), and define

$g:=\sum_{|T|\leq d}d_{T}y_{T}.$

Then $\Pr_{S\sim\mu_{4p}}[g_{S}=g|_{S}]=1-O(\varepsilon)$, and so
$\Pr_{\mu_{p}}[g\in A]=1-O(\varepsilon)$.

###### Proof.

To apply the agreement theorem we would like to first bound the probability
$\Pr_{S_{1},S_{2}\sim\mu_{4p,1/2}}[g_{S_{1}}|_{S_{1}\cap S_{2}}\neq
g_{S_{2}}|_{S_{1}\cap S_{2}}]$ when the pair of sets $(S_{1},S_{2})$ are
chosen according to $\mu_{4p,1/2}$. Now for $(S_{1},S_{2})\sim\mu_{4p,1/2}$,
let $T:=S_{1}\cap S_{2}$. Notice that $S_{1},S_{2}\sim\mu_{4p}$, while
$T\sim\mu_{1/2}(S_{1})$. Consider the three juntas $g_{S_{1}},g_{S_{2}}$ and
$h_{T}$. Clearly, if $g_{S_{1}}|_{T}\neq g_{S_{2}}|_{T}$ then one of
$g_{S_{1}}|_{T}\neq h_{T}$ or $g_{S_{2}}|_{T}\neq h_{T}$ must hold. Thus,

$\Pr_{S_{1},S_{2}\sim\mu_{4p,1/2}}[g_{S_{1}}|_{S_{1}\cap S_{2}}\neq
g_{S_{2}}|_{S_{1}\cap S_{2}}]\leq 2\Pr_{\begin{subarray}{c}S\sim\mu_{4p}\\\
T\sim\mu_{1/2}(S)\end{subarray}}[g_{S}|_{T}\neq h_{T}]$ (1)

Thus, it suffices to bound the probability $\Pr_{S,T}[g_{S}|_{T}\neq h_{T}]$
where $S\sim\mu_{4p}$ and $T\sim\mu_{1/2}(S)$.

For any $T\subseteq S\subseteq[n]$, the $L_{2}^{2}$ triangle inequality shows
that,

$\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(g_{S}|_{T}-h_{T})^{2}]\leq
2\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(g_{S}|_{T}-f|_{T})^{2}]+2\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(f|_{T}-h_{T})^{2}]=2\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(g_{S}|_{T}-f|_{T})^{2}]+O(\operatorname*{\mathbb{E}}_{\mu_{1/2}}[\operatorname{dist}(f|_{T},A)^{2}]).$

Taking expectation over $T\sim\mu_{1/2}(S)$, we see that

$\operatorname*{\mathbb{E}}_{T\sim\mu_{1/2}(S)}\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(g_{S}|_{T}-h_{T})^{2}]\leq
2\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(g_{S}-f|_{S})^{2}]+O(\operatorname*{\mathbb{E}}_{\mu_{1/4}}[\operatorname{dist}(f|_{S},A)^{2}])=O(\operatorname*{\mathbb{E}}_{\mu_{1/4}}[\operatorname{dist}(f|_{S},A)^{2}]).$

Here we used the fact that if $T\sim\mu_{1/2}(S)$ and $x\sim\mu_{1/2}(T)$ then
$x\sim\mu_{1/4}(S)$.

Both $g_{S}|_{T}$ and $h_{T}$ are $A$-valued degree $d$ juntas (see 4.2).
Hence either they agree, or
$\operatorname*{\mathbb{E}}_{\mu_{1/2}}[(g_{S}|_{T}-h_{T})^{2}]=\Omega(1)$.
Therefore

$\Pr_{T\sim\mu_{1/2}(S)}[g_{S}|_{T}\neq
h_{T}]=O(\operatorname*{\mathbb{E}}_{\mu_{1/4}}[\operatorname{dist}(f|_{S},A)^{2}])=O(\varepsilon_{S}).$

Now, taking expectation over $S\sim\mu_{4p}$, we obtain via 5.3

$\Pr_{\begin{subarray}{c}S\sim\mu_{4p}\\\
T\sim\mu_{1/2}(S)\end{subarray}}[g_{S}|_{T}\neq
h_{T}]=\mathbb{E}_{S\sim\mu_{4p}}[O(\varepsilon_{S})]=O(\varepsilon).$

We now return to (1), to conclude that

$\Pr_{S_{1},S_{2}\sim\mu_{4p,1/2}}[g_{S_{1}}|_{S_{1}\cap S_{2}}\neq
g_{S_{2}}|_{S_{1}\cap S_{2}}]=O(\varepsilon).$

We have thus satisfied the hypothesis of the agreement theorem (Theorem 2.4).
Invoking the agreement theorem, we deduce that
$\Pr_{S\sim\mu_{4p}}[g_{S}=g|_{S}]=1-O(\varepsilon)$. Since $g_{S}$ is
$A$-valued,

$\Pr_{\mu_{p}}[g\in A]\geq\Pr_{\begin{subarray}{c}S\sim\mu_{4p}\\\
x\sim\mu_{1/4}(S)\end{subarray}}[g(x)=g_{S}(x)]\geq\Pr_{S\sim\mu_{4p}}[g|_{S}=g_{S}]=1-O(\varepsilon).\qed$

We have thus constructed the function $g$ indicated in the Theorem 5.1 and
shown that $\Pr_{\mu_{p}}[g\notin A]=O(\varepsilon)$. In the remaining claims,
we show the other properties of $g$ mentioned in Theorem 5.1.

First, we observe that since the $g_{S}$ are juntas, the coefficients
$d_{S,T}$, and so $d_{T}$, belong to a finite set depending only on $d,A$. We
can easily deduce an upper bound on the support of $g$.

######  Claim 5.5.

The function $g$ from 5.4 has branching factor $O(1/p)$.

###### Proof.

Let $R,e$ be given. We want to show that the number of $B\supseteq R$ such
that $|B|=|R|+e$ and $d_{B}\neq 0$ is $O(p^{-e})$. Let us denote by
$\mathcal{B}=\\{B\supseteq R:|B\setminus R|=e\\}$ the collection of all such
potential $B$.

Let $g_{S}$ be the functions from 5.3. Recall that
$g_{S}=\sum_{B}d_{S,B}y_{B}$. Since $g_{S}$ is a junta (by 4.2),
$\sum_{B}d_{S,B}^{2}=O(1)$. Therefore

$\operatorname*{\mathbb{E}}_{\begin{subarray}{c}S\sim\mu_{4p}\\\ S\supseteq
R\end{subarray}}\left[\sum_{\begin{subarray}{c}B\in\mathcal{B}\\\ B\subseteq
S\end{subarray}}d_{S,B}^{2}\right]=O(1).$

Given that $S$ contains $R$, the probability that it also contains a specific
$B\in\mathcal{B}$ is $(4p)^{|B|-|S|}=(4p)^{e}$, and so

$\sum_{B\in\mathcal{B}}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}S\sim\mu_{4p}\\\
S\supseteq B\end{subarray}}[d_{S,B}^{2}]=O(p^{-e}).$

Since there are only finitely many possible values for $d_{S,B}$ (since
$g_{S}$ is an $A$-valued junta) and we chose $d_{B}$ as the plurality value,
the inner expectation is $\Omega(d_{B}^{2})$, and so

$\sum_{B\in\mathcal{B}}d_{B}^{2}=O(p^{-e}).$

Again due to the finitely many possible values for $d_{B}$, each non-zero
$d_{B}^{2}$ is $\Omega(1)$. We conclude that the number of non-zero $d_{B}$
for $B\in\mathcal{B}$ is $O(p^{-e})$, as needed. ∎

Our next step is to consider an auxiliary function derived from $g$.

######  Lemma 5.6.

Let $g$ be the function from 5.4, and define

$G=\prod_{a\in A}(g-a).$

Then $G$ satisfies the following properties:

  1. 1.

$G$ has branching factor $O(1/p)$.

  2. 2.

$\Pr_{\mu_{p}}[G=0]=1-O(\varepsilon)$.

  3. 3.

The number of sets $B$ of size $e$ such that $\tilde{G}(B)\neq 0$ is
$O(p^{-e}\varepsilon)$.

  4. 4.

$\operatorname*{\mathbb{E}}_{\mu_{p}}[G^{2}]=O(\varepsilon)$.

###### Proof.

The first property follows from 5.5 via Lemma 3.2, and the second from 5.4.

For the third property, we start by bounding the number $N_{e}$ of sets $B$ of
size $e$ such that $\tilde{G}(B)\neq 0$ but $\tilde{G}(R)=0$ for all
$R\subsetneq B$. For each such $B$, Lemma 3.4 shows that the probability that
$y_{B}=1$ and $y_{C}=0$ for all other $C$ in the support of $G$ is
$\Omega(p^{e})$. If this event happens, then $G=\tilde{G}(B)\neq 0$. Since
these events are disjoint, we deduce that $\Pr[G\neq 0]=\Omega(p^{e}N_{e})$,
which implies that $N_{e}=O(p^{-e}\varepsilon)$.

We can associate with each $B$ of size $e$ such that $\tilde{G}(B)\neq 0$ a
subset $B^{\prime}\subseteq B$ such that $\tilde{G}(B^{\prime})\neq 0$ but
$\tilde{G}(R)=0$ for all $R\subsetneq B$. For each $e^{\prime}\leq e$, there
are $N_{e^{\prime}}=O(p^{-e^{\prime}}\varepsilon)$ options for the set
$B^{\prime}$. Since $G$ has branching factor $O(1/p)$, the set $B^{\prime}$
has $O(p^{-(e-e^{\prime})})$ extensions of size $e$ in the support of $G$. In
total, for each $e^{\prime}$ there are $O(p^{-e^{\prime}}\varepsilon)\cdot
O(p^{-(e-e^{\prime})})=O(p^{-e}\varepsilon)$ sets $B$ with
$|B^{\prime}|=e^{\prime}$. Considering the $e+1$ possible values of
$e^{\prime}$, we deduce the third property.

For the fourth property, write

$G^{2}=\sum_{B}y_{B}\sum_{B_{1}\cup B_{2}=B}\tilde{G}(B_{1})\tilde{G}(B_{2}).$

Lemma 2.3 implies that $|\tilde{G}(B)|=O(1)$ (recalling that the coefficients
$d_{B}$ of $g$ belong to a finite set depending only on $d,A$, due to 4.2).
Denoting by $M_{e}$ the number of pairs $B_{1},B_{2}$ such that
$\tilde{G}(B_{1}),\tilde{G}(B_{2})\neq 0$ and $|B_{1}\cup B_{2}|=e$, it
follows that $\operatorname*{\mathbb{E}}[G^{2}]=O(\sum_{e}p^{e}M_{e})$. Since
the sum contains finitely many terms ($\deg G\leq d|A|$), the fourth property
will follow if we show that $M_{e}=O(p^{-e}\varepsilon)$.

Given $e$, it remains to bound the number of pairs $B_{1},B_{2}$ such that
$\tilde{G}(B_{1}),\tilde{G}(B_{2})\neq 0$ and $|B_{1}\cup B_{2}|=e$. For each
$e_{1},e_{2},e_{\cap}$, we will count the number of such pairs with
$|B_{i}|=e_{i}$ and $|B_{1}\cap B_{2}|=e_{\cap}$. The third property shows
that there are $O(p^{-e_{1}}\varepsilon)$ many choices for $B_{1}$. For each
such $B_{1}$, there are $O(1)$ many choices for $B_{1}\cap B_{2}$, and given
$B_{1}\cap B_{2}$, the first property shows that there are
$O(p^{-(e_{2}-e_{\cap})})$ choices for $B$. In total, there are
$O(p^{-e_{1}}\varepsilon)\cdot O(1)\cdot
O(p^{-(e_{2}-e_{\cap})})=O(p^{-(e_{1}+e_{2}-e_{\cap})}\varepsilon)=O(p^{-e}\varepsilon)$
choices for $B_{1},B_{2}$. The fourth property follows since there are $O(1)$
many choices for $e_{1},e_{2},e_{\cap}$. ∎

Using the function $G$, we can finally compare $f$ and $g$.

######  Lemma 5.7.

Let $g$ be the function from 5.4. Then
$\|f-g\|^{2}=\operatorname*{\mathbb{E}}_{\mu_{p}}[(f-g)^{2}]=O(\varepsilon)$.

###### Proof.

Let $F=\operatorname{round}(f,A)$, and let $g_{S},g,G$ be the functions
defined in 5.3, 5.4, and Lemma 5.6. We have

$\operatorname*{\mathbb{E}}_{\mu_{p}}[(F-g)^{2}]=\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-g|_{S})^{2}]=\\\
\underbrace{\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-g|_{S})^{2}1_{g|_{S}=g_{S}}]}_{\varepsilon_{1}}+\underbrace{\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-g|_{S})^{2}1_{g|_{S}\neq
g_{S}}]}_{\varepsilon_{2}}.$

5.3 allows us to estimate $\varepsilon_{1}$, using the $L_{2}^{2}$ triangle
inequality:

$\varepsilon_{1}=\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-g_{S})^{2}]\leq
2\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-f|_{S})^{2}]+2\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(f|_{S}-g_{S})^{2}]=\\\
2\operatorname*{\mathbb{E}}_{\mu_{p}}[(F-f)^{2}]+2\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}[\varepsilon_{S}]=O(\varepsilon)+O(\varepsilon)=O(\varepsilon).$

We estimate $\varepsilon_{2}$ by truncation. Since $x^{2}=O(\prod_{a\in
A}(x-a)^{2})$ as $x\to\infty$, we can find constants $M,C>0$ (depending only
on $A$) such that if $|x|\geq M$ then $x^{2}\leq C\prod_{a\in A}(x-a)^{2}$.
Let $g=g_{\leq M}+g_{>M}$, where $g_{\leq M}=g1_{|g|\leq M}$. The $L_{2}^{2}$
triangle inequality shows that

$\varepsilon_{2}\leq
2\underbrace{\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[(F|_{S}-g_{\leq
M}|_{S})^{2}1_{g|_{S}\neq
g_{S}}]}_{\varepsilon_{2,1}}+2\underbrace{\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[g_{>M}|_{S}^{2}1_{g|_{S}\neq
g_{S}}]}_{\varepsilon_{2,2}}.$

Because both $F$ and $g_{\leq M}$ are bounded, we can estimate
$\varepsilon_{2,1}$ by

$\varepsilon_{2,1}=O(\Pr_{S\sim\mu_{4p}}[g|_{S}\neq g_{S}])=O(\varepsilon),$

using 5.4. The defining property of $M$ shows that

$\varepsilon_{2,2}\leq
C\operatorname*{\mathbb{E}}_{S\sim\mu_{4p}}\operatorname*{\mathbb{E}}_{\mu_{1/4}}[G|_{S}^{2}]=O(\operatorname*{\mathbb{E}}_{\mu_{p}}[G^{2}])=O(\varepsilon),$

using the fourth property of Lemma 5.6. Altogether, we deduce that
$\operatorname*{\mathbb{E}}_{\mu_{p}}[(F-g)^{2}]=O(\varepsilon)$. Since
$\operatorname*{\mathbb{E}}_{\mu_{p}}[(F-f)^{2}]=\varepsilon$ by definition,
the $L_{2}^{2}$ triangle inequality completes the proof. ∎

We can now prove our main theorem. Recall that the statement of the theorem
does not make any assumptions on $p$ though all the above claims use the fact
that $p\leq p_{0}$.

###### Proof of Theorem 5.1.

Suppose that $p\leq p_{0}$, and let $g$ be the function constructed in 5.4.
The first property follows from Lemma 5.7. The second property follows from
5.4. The third property follows from the definition of $g$. The fourth
property follows from 5.5. Finally, 5.4 shows that
$\Pr_{S\sim\mu_{4p}}[g|_{S}=g_{S}]=1-O(\varepsilon)$. Hence if we choose
$S\sim\mu_{4p}$ and $x\sim\mu_{1/4}(S)$ (so that $x\sim\mu_{p}$), we get that
$g(x)=g_{S}(x)$ with probability $1-O(\varepsilon)$, implying the fifth
property since $g_{S}$ is a junta.

When $p\in[p_{0},1/2]$, we choose $g$ using the generalized Kindler–Safra
theorem, Theorem 4.1, guaranteeing the first property (we use the fact that
the big O constant varies continuously with $p$). 4.2 shows that $g$ is an
$A$-valued junta, implying all the other properties. ∎

Corollary 5.2 is proved along similar lines.

###### Proof of Corollary 5.2.

Apply the theorem to $f:=F^{\leq d}$, which satisfies
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. The
$L_{2}^{2}$ triangle inequality shows that $\|F-g\|^{2}\leq
2\|F-f\|^{2}+2\|f-g\|^{2}=O(\varepsilon)$. For the second property,

$\Pr[F\neq g]\leq\Pr[g\notin A]+\Pr[F\neq g\text{ and }g\in A]=\Pr[F\neq
g\text{ and }g\in A]+O(\varepsilon).$

When $g(x)\in A$, if $F(x)\neq g(x)$ then $(F(x)-g(x))^{2}=\Omega(1)$.
Therefore

$\Pr[F\neq g\text{ and }g\in A]=\operatorname*{\mathbb{E}}_{\mu_{p}}[1_{F\neq
g\text{ and }g\in
A}]\leq\operatorname*{\mathbb{E}}_{\mu_{p}}[(F-g)^{2}]=O(\varepsilon).$

Altogether we get that $\Pr[F\neq g]=O(\varepsilon)$. All other properties are
inherited from the theorem. ∎

##  6 A converse to the main result

Given a degree $d$ function $f$ such that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$,
Theorem 5.1 gives a function $g$ such that $\|f-g\|^{2}=O(\varepsilon)$ and:

  * •

$\deg g\leq d$

  * •

$g$ has branching factor $O(1/p)$.

  * •

$\Pr[g\notin A]=O(\varepsilon)$.

  * •

The coefficients of the $y$-expansion of $g$ belong to some finite set
depending only on $d,A$.

In this short section, we show that a function $g$ satisfying these properties
also satisfies
$\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}]=\varepsilon$, and in
this sense Theorem 5.1 is a complete characterization of degree $d$ functions
close (in $L_{2}$) to $A$.

######  Lemma 6.1.

Fix $d\geq 0$ and finite sets $A,B$. Suppose that $g$ satisfies the following
properties, for some small enough $p$:

  * •

$\deg g\leq d$

  * •

$g$ has branching factor $O(1/p)$.

  * •

$\Pr[g\notin A]=\varepsilon$.

  * •

The coefficients of the $y$-expansion of $g$ belong to $B$.

Then
$\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}]=O(\varepsilon)$.

###### Proof.

The first step is to apply the argument of Lemma 5.6. This lemma defines

$G=\prod_{a\in A}(g-a),$

and proves that $\operatorname*{\mathbb{E}}[G^{2}]=O(\varepsilon)$, using only
the listed properties.

Since $\operatorname{dist}(x,A)^{2}=O(\prod_{a\in A}(x-a)^{2})$, there exists
$M$ such that $\operatorname{dist}(g,A)^{2}\leq G^{2}$ whenever $|g|\geq M$.
For an arbitrary $a\in A$ we have

$\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}]=\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}1_{g\notin
A,|g|\leq
M}]+\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}1_{g\notin
A,|g|\geq M}]\leq\\\ (M+|a|)^{2}\Pr[g\notin
A]+\operatorname*{\mathbb{E}}[G^{2}]=O(\varepsilon).\qed$

##  7 Applications

Our main theorem, Theorem 5.1, describes the approximate structure of degree
$d$ functions which are close in $L_{2}^{2}$ to a fixed finite set (“almost
quantized functions”): all such functions are close to sparse juntas. This
allows us to deduce properties of bounded degree almost quantized functions
from properties of sparse juntas.

We give two examples of applications of this sort in this section: we prove a
large deviation bound, and we show that when $p$ is small, every bounded
degree almost quantized function must be very biased.

###  7.1 Large deviation

Our first application is a large deviation bound, proved via estimating
moments. We start by analyzing the simpler case of hypergraphs.

######  Lemma 7.1.

Let $H$ be a $d$-uniform hypergraph with branching factor $C/p$. For
$S\sim\mu_{p}$, let $X$ be the number of hyperedges in $H|_{S}$. For all
integer $k$,

$\operatorname*{\mathbb{E}}[X^{k}]\leq(Ckd)^{kd}.$

###### Proof.

Let $e_{1},\ldots,e_{k}$ be a $k$-tuple of hyperedges. We can consider the
hypergraph whose vertices are $e_{1}\cup\cdots\cup e_{k}$ and whose hyperedges
are $e_{1},\ldots,e_{k}$. This is a hypergraph on at most $kd$ vertices which
we call a _pattern_. We can crudely upper bound the number of patterns by
$(kd)^{kd}$.

Let $P$ be a pattern on $m=m(P)$ vertices. Our goal is to show that the number
of $k$-tuples of hyperedges conforming to this pattern is at most $(C/p)^{m}$.
Suppose that we have already chosen $e_{1},\ldots,e_{i-1}$, and suppose that
$t_{i}=|e_{i}\setminus(e_{1}\cup\cdots\cup e_{i-1})|$. Since $H$ has branching
factor $C/p$, there are at most $(C/p)^{t_{i}}$ choices for $e_{i}$. In total,
the number of $k$-tuples is at most $(C/p)^{t_{1}+\cdots+t_{k}}=(C/p)^{m}$.

We can estimate the $k$th moment by

$\operatorname*{\mathbb{E}}[X^{k}]=\sum_{e_{1},\ldots,e_{k}}\Pr[e_{1}\cup\cdots\cup
e_{k}\subseteq S]=\sum_{e_{1},\ldots,e_{k}}p^{|e_{1}\cup\cdots\cup
e_{k}|}\leq\sum_{P}p^{m(P)}(C/p)^{m(P)}\leq(Ckd)^{kd}.\qed$

This implies a large deviation bound for hypergraphs.

######  Lemma 7.2.

Let $H$ be a $d$-uniform hypergraph with branching factor $C/p$. For
$S\sim\mu_{p}$, let $X$ be the number of edges in $H|_{S}$. For large enough
$t$,

$\Pr[X\geq t]=\exp-\Omega(t^{1/d}/C).$

###### Proof.

Let $k=t^{1/d}/(eCd)$. We perform the calculation under the assumption that
$k$ is an integer; in general $k$ should be taken to be $\lfloor
t^{1/d}/(eCd)\rfloor$, but the difference disappears for large $t$.

Lemma 7.1 shows that
$\operatorname*{\mathbb{E}}[X^{k}]\leq(t^{1/d}/e)^{kd}=t^{k}/e^{kd}$, and so
Markov’s inequality shows that $\Pr[X^{k}\geq t^{k}]\leq
t^{k}/\operatorname*{\mathbb{E}}[X^{k}]=e^{-kd}$. The lemma follows since
$kd=t^{1/d}/(eC)$. ∎

These two results also apply, with minor changes, to functions with bounded
coefficients.

######  Lemma 7.3.

Let $f$ be a degree $d$ function with branching factor $C/p$, the coefficients
of whose $y$-expansion are bounded in magnitude by $M$. For all integer $k\geq
1$,

$\operatorname*{\mathbb{E}}[|f|^{k}]\leq M^{k}(2Ckd)^{kd}.$

###### Proof.

Let $H$ be the support of $f$. The triangle inequality shows that at a given
point $S$, the value of $|f|^{k}$ is bounded by $M^{k}$ times the number of
$k$-tuples $e_{1},\ldots,e_{k}\in H$ such that $e_{1},\ldots,e_{k}\subseteq
S$. We can then run the argument of Lemma 7.1 as written, the only difference
being that now the hyperedges have _at most_ $d$ vertices. This increases the
number of patterns to at most (say) $(kd+1)^{kd}\leq(2kd)^{kd}$. ∎

######  Lemma 7.4.

Let $f$ be a degree $d$ function with branching factor $C/p$, the coefficients
of whose $y$-expansion are bounded in magnitude by $M$. For large enough $t$,

$\Pr[|f|\geq Mt]=\exp-\Omega(t^{1/d}/C).$

###### Proof.

This lemma follows from Lemma 7.3 just as Lemma 7.2 follows from Lemma 7.1. ∎

Applying our main theorem, we deduce a large deviation bound for bounded
degree almost quantized functions.

######  Corollary 7.5 (Restatement of Lemma 1.6).

Fix an integer $d$ and a finite set $A$. Suppose that
$f\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$ with
respect to $\mu_{p}$ for some $p\leq 1/2$. For large enough $t$,

$\Pr[|f|\geq t]\leq\exp-\Omega(t^{1/d})+O(\varepsilon/t^{2}).$

###### Proof.

Theorem 5.1 shows that there exists a function $g$ satisfying the conditions
of the lemma such that $\|f-g\|^{2}=O(\varepsilon)$. If $|f|\geq t$ then
either $|f-g|\geq t/2$ or $|g|\geq t/2$. The corollary follows from Markov’s
inequality and the lemma. ∎

###  7.2 Distance from being constant

Suppose that $f$ is a bounded degree $A$-valued function. How does the
empirical distribution of $f$ under $\mu_{p}$ look like, for small $p$? 4.2
shows that $f$ is a junta. All coordinates it depends upon are zero with
probability $(1-p)^{O(1)}=1-O(p)$, and so for small $p$ the empirical
distribution of $f$ is very biased.

What happens when $f$ is just _close_ to being $A$-valued? Consider for
example the function $f=y_{1}+\cdots+y_{c/p}$, for some small $c$. The
empirical distribution of $f$ is close to Poisson with expectation $c$, and so
$\Pr[f=0]\approx e^{-c}\approx 1-c$, $\Pr[f=1]\approx e^{-c}c\approx c-c^{2}$,
and so $\Pr[f\notin\\{0,1\\}]\approx c^{2}$. Taking $c=\sqrt{\varepsilon}$, we
see that $f$ is $\varepsilon$-close to $\\{0,1\\}$, but only
$\sqrt{\varepsilon}$-biased (that is, the most probable element in the range
is attained with probability roughly $1-\sqrt{\varepsilon}$). We think of
$\varepsilon$ as a “small constant” much larger than $p$, and this shows that
almost $\\{0,1\\}$-valued functions can be much less biased than truly
$\\{0,1\\}$-valued functions.

In this section our goal is to estimate how biased can bounded degree almost
quantized functions be. We start by analyzing the situation for sparse juntas.

######  Lemma 7.6 (Restatement of Lemma 1.7).

Fix a constant $d\geq 0$ and a finite set $A$. There exist constants
$C,\varepsilon_{0}>0$ such that for all $p\leq 1/4$111This constant is
arbitrary. Any constant less than 1 can be used. and
$\varepsilon\leq\varepsilon_{0}$, the following holds.

Suppose that $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function with
branching factor $O(1/p)$ such that $\Pr[g\notin A]=\varepsilon$. Then there
exists $a\in A$ such that $\Pr[g\neq a]=O(\varepsilon^{C}+p)$.

###### Proof.

Lemma 3.4 shows that $\Pr[g=\tilde{g}(\emptyset)]=\Omega(1)$. Choosing
$\varepsilon_{0}$ small enough, we can guarantee that $\tilde{g}(\emptyset)\in
A$.

Denote $a:=\tilde{g}(\emptyset)$ and $\delta:=\Pr[g\neq a]$. Let
$S_{e}=\\{|B|=e:\tilde{g}(B)\neq 0\\}$. If $g\neq a$ then $y_{B}\neq 0$ for
some $B$ such that $\tilde{g}(B)\neq 0$, and this shows that
$\delta\leq\sum_{e=1}^{d}p^{e}|S_{e}|$. Therefore there exists $1\leq e\leq d$
such that $|S_{e}|\geq\delta p^{-e}/d$.

Let $M$ be the constant from 4.2. We will show that either there exist
constants $L,C>0$ such that either $\delta=O(p)$ or

$\Pr_{S\sim\mu_{2p}}[g|_{y_{S}=1}\text{ depends on more than $M$ and at most
$L$ coordinates}]=\Omega(\delta^{C}).$

If $g|_{y_{S}=1}$ depends on more than $M$ coordinates then it cannot be
$A$-valued. If it also depends on at most $L$ coordinates, the probability
(with respect to $\mu_{1/2}$) that it is not $A$-valued is $\Omega(1)$. Hence

$\Pr[g\notin A]=\Pr_{\begin{subarray}{c}S\sim\mu_{2p}\\\
x\sim\mu_{1/2}(S)\end{subarray}}[g(x)\notin
A]\geq\Omega\bigl{(}\Pr_{S\sim\mu_{2p}}[g|_{y_{S}=1}\text{ depends on $>M$ and
$\leq L$ coordinates}]\bigr{)}=\Omega(\delta^{C}),$

as claimed.

Let $M_{0}$ be a constant such that $M_{0}$ distinct hyperedges of cardinality
at most $d$ span more than $M$ vertices. Note that $M_{0}$ such hyperedges
also span at most $L:=dM_{0}$ vertices. If $|S_{e}|<M_{0}$ then
$\delta=O(p^{e})=O(p)$, so we can assume that $|S_{e}|\geq M_{0}$.

Consider the collection $\mathcal{S}$ of all $M_{0}$-tuples of hyperedges from
$|S_{e}|$. Since $|S_{e}|\geq M_{0}$, we have
$|\mathcal{S}|=\Omega(|S_{e}|^{M_{0}})=\Omega(\delta^{M_{0}}p^{-eM_{0}})$. For
each $M_{0}$-tuple of hyperedges, we can consider the set of vertices
contained in these hyperedges. Let $\mathcal{V}$ denote the collection of all
such sets of vertices formed from $\mathcal{S}$. Since every set in
$\mathcal{S}$ can be obtained from $O(1)$ tuples of $\mathcal{V}$, we have
$|\mathcal{V}|=\Omega(\delta^{M_{0}}p^{-eM_{0}})$. Every set in $\mathcal{V}$
contains at most $eM_{0}$ vertices.

For every $U\in\mathcal{V}$, Lemma 3.3 shows that $g|_{y_{U}=1}$ has branching
factor $O(1/p)$. Hence Lemma 3.4 shows that when $S\sim\mu_{2p}$, with
probability $\Omega((2p)^{|U|})=\Omega(p^{eM_{0}})$ the vertex support of
$g|_{y_{S}=1}$ contains no vertex outside of $U$. In fact, since $U$ is the
set of vertices contained in an $M_{0}$-tuple of hyperedges, the vertex
support of $g|_{y_{S}=1}$ is exactly $U$, and so $g|_{y_{S}=1}$ depends on
more than $M$ and at most $L$ coordinates. The corresponding events for
different $U$ are disjoint, and we conclude that

$\Pr_{S\sim\mu_{2p}}[g|_{y_{S}=1}\text{ depends on $>M$ and $\leq L$
coordinates}]=\Omega(p^{eM_{0}})|\mathcal{V}|=\Omega(p^{eM_{0}})\cdot\Omega(\delta^{M_{0}}p^{-eM_{0}})=\Omega(\delta^{M_{0}}),$

completing the proof. ∎

Applying Corollary 5.2, we obtain a similar result for bounded degree almost
quantized functions.

######  Corollary 7.7.

Fix a constant $d\geq 0$ and a finite set $A$. There exists constant
$C,\varepsilon_{0}>0$ such that for all $p\leq 1/4$ and
$\varepsilon\leq\varepsilon_{0}$, the following holds.

Suppose that $f\colon\\{0,1\\}^{n}\to\mathbb{R}$ is a degree $d$ function
satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. Then
there exists $a\in A$ such that $\Pr[\operatorname{round}(f,A)\neq
a]=O(\varepsilon^{C})$.

###### Proof.

Let $F=\operatorname{round}(f,A)$. Corollary 5.2 shows that there exists a
degree $d$ function $g\colon\\{0,1\\}^{n}\to\mathbb{R}$ which has branching
factor $O(1/p)$ and satisfies $\Pr[g\notin A]=O(\varepsilon)$ and $\Pr[F\neq
g]=O(\varepsilon)$. The lemma shows that $\Pr[g\neq a]=O(\varepsilon^{C})$ for
some $a\in A$, and the corollary follows. ∎

##### Discussion

What is the correct exponent of $\varepsilon$? Let us focus on $A=\\{0,1\\}$.
Let $n=\delta/p$, and consider the function

$f_{d}=\sum_{i_{1}}y_{i_{1}}-\sum_{i_{1}<i_{2}}y_{i_{1}}y_{i_{2}}+\cdots\pm\sum_{i_{1}<\cdots<i_{d}}y_{i_{1}}\ldots
y_{i_{d}}.$

When exactly $m$ of the coordinates are 1, we have

$f_{d}=\sum_{e=1}^{d}(-1)^{e-1}\binom{m}{e}=1-\sum_{e=0}^{d}(-1)^{e}\binom{m}{e}.$

When $m\leq d$, we have

$f_{d}=1-\sum_{e=0}^{m}(-1)^{e}\binom{m}{e}=1-(1-1)^{m}=\begin{cases}0&\text{if
}m=0,\\\ 1&\text{otherwise}.\end{cases}$

When $m=d+1$, we have

$f_{d}=1-\sum_{e=0}^{m}(-1)^{e}\binom{m}{e}+(-1)^{m}\binom{m}{m}=1-(1-1)^{m}+(-1)^{m}=\begin{cases}0&\text{if
$d$ is even},\\\ 2&\text{if $d$ is odd}.\end{cases}$

For small $p$, the distribution of $m$ is roughly Poisson with expectation
$\delta$, and so for small $\delta$:

  * •

$\Pr[f_{d}=0]\geq\Pr[m=0]\approx e^{-\delta}\approx 1-\delta$.

  * •

When $d$ is odd,
$\Pr[f_{d}\notin\\{0,1\\}]\leq\Pr[m>d]\approx\Pr[m=d+1]\approx
e^{-\delta}\frac{\delta^{d+1}}{(d+1)!}\approx\frac{\delta^{d+1}}{(d+1)!}$.

  * •

When $d$ is even,
$\Pr[f_{d}\notin\\{0,1\\}]\leq\Pr[m>d+1]\approx\Pr[m=d+2]\approx
e^{-\delta}\frac{\delta^{d+2}}{(d+2)!}\approx\frac{\delta^{d+2}}{(d+2)!}$.

This shows that a degree $d$ function which is $\varepsilon$-close to $A$ can
be $\Omega(\varepsilon^{1/(d+1)})$-far from constant, and even
$\Omega(\varepsilon^{1/(d+2)})$-far when $d$ is even. When $d=1$, the sparse
FKN theorem [Fil16] shows that the exponent $1/2$ is tight.

##  8 New proof of classical Kindler–Safra theorem

In this section we give a self-contained proof of the Kindler–Safra theorem in
the $\mu_{1/2}$ setting. The proof can easily be extended to the $\mu_{p}$
setting for any constant $p$. Our functions are on the domain $\\{\pm
1\\}^{n}$, and we denote their inputs by $x_{1},\ldots,x_{n}\in\\{\pm 1\\}$.

When we write $x\sim\\{\pm 1\\}^{n}$, we always mean that $x$ is chosen
according to the uniform distribution over $\\{\pm 1\\}^{n}$.

###  8.1 A-valued FKN theorem

As a prerequisite for our proof of the Kindler–Safra theorem, we need to
extend the FKN theorem to the $A$-valued setting. Our proof closely follows
the proof in Kindler’s thesis [Kin03]. In contrast to the classical FKN
theorem, in which the approximating functions are dictators, in the $A$-valued
setting we only get juntas. Indeed, if $A=\\{0,1,\ldots,a\\}$ then the
function $\sum_{i=1}^{a}\frac{1+x_{i}}{2}$ is $A$-valued.

We start by identifying the junta variables.

######  Lemma 8.1.

Fix a finite set $A$. Let $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ be a degree 1
function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. There
exists a constant $m>0$ (depending on $A$) such that $\hat{f}(i)^{2}\geq
m\varepsilon$ for at most $|A|-1$ many coefficients $\hat{f}(i)$.

###### Proof.

Let $m=2^{|A|+1}$, and let $J_{0}=\\{i:\hat{f}(i)^{2}\geq m\varepsilon\\}$.
Our goal is to show that $|J_{0}|<|A|$. If not, we can choose a subset
$J\subseteq J_{0}$ of size exactly $|A|$. There is an assignment $\alpha$ to
the coordinates outside $J$ such that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f|_{\alpha},A)^{2}]\leq\varepsilon$.
This implies that for some $c$,

$\operatorname*{\mathbb{E}}[\operatorname{dist}(\sum_{i\in
J}\hat{f}(i)x_{i}+c,A)^{2}]\leq\varepsilon.$

We can assume, without loss of generality, that $\hat{f}(i)>0$ for all $i\in
J$ (otherwise, we can define a new function obtained from $f$ by flipping the
appropriate inputs). Assume also, for simplicity, that $J=\\{1,\ldots,|A|\\}$.
For $0\leq i\leq|A|$, define

$v_{i}=c+\sum_{j=0}^{i-1}\hat{f}(j)-\sum_{j=i}^{|A|}\hat{f}(j).$

For every $0\leq i\leq|A|$, let $a_{i}=\operatorname{round}(v_{i},A)$. Since
$v_{i}-v_{i-1}=2\hat{f}(i)>0$, we can assume that $a_{i}\geq a_{i-1}$. By
assumption, $|v_{i}-a_{i}|^{2}\leq 2^{|J|}\varepsilon=2^{|A|}\varepsilon$ for
all $i$. If $a_{i}=a_{i-1}$, then this implies that $(v_{i}-v_{i-1})^{2}\leq
2^{|A|+2}\varepsilon$ (using the $L_{2}^{2}$ triangle inequality), which
contradicts the upper bound, $(v_{i}-v_{i-1})^{2}=4\hat{f}(i)^{2}\geq
4m\varepsilon=2^{|A|+3}\varepsilon$. We conclude that $a_{i}>a_{i-1}$, and so
$a_{0}<a_{1}<\cdots<a_{|A|}$. However, this is impossible, since $A$ contains
only $|A|$ elements. This contradiction shows that $|J_{0}|<|A|$. ∎

The idea now is to truncate $f$ to its junta part, and to show that the noisy
part has small norm. We do this in an inductive fashion, using the following
lemma.

######  Lemma 8.2.

Fix a finite set $A$, and let $m$ be the constant from Lemma 8.1. There exists
a constant $\varepsilon_{0}>0$ (depending on $A$) such the following holds for
all $\varepsilon\leq\varepsilon_{0}$.

If $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ is a degree 1 function satisfying
$\operatorname*{\mathbb{V}}[f]\leq(2+m)\varepsilon$ and
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$, then
in fact $\operatorname*{\mathbb{V}}[f]\leq 2\varepsilon$.

###### Proof.

Markov’s inequality shows that each of the events
$(f-\operatorname*{\mathbb{E}}[f])^{2}\leq 3(2+m)\varepsilon$ and
$\operatorname{dist}(f,A)^{2}\leq 3\varepsilon$ occurs with probability $2/3$,
and so there is a point at which both occur simultaneously. The $L_{2}^{2}$
triangle inequality implies that for some $a\in A$,

$(\operatorname*{\mathbb{E}}[f]-a)^{2}\leq
6(2+m)\varepsilon+6\varepsilon=(18+6m)\varepsilon.$

Let $\mathcal{E}$ denote the event that $\operatorname{round}(f,A)=a$. Then

$\varepsilon\geq\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}1_{\mathcal{E}}]=\operatorname*{\mathbb{E}}[(f-a)^{2}1_{\mathcal{E}}]=\operatorname*{\mathbb{E}}[(f-a)^{2}]-\underbrace{\operatorname*{\mathbb{E}}[(f-a)^{2}1_{\overline{\mathcal{E}}}]}_{\delta}.$

When $\operatorname{round}(f,A)\neq a$, necessarily $(f-a)^{2}=\Omega_{A}(1)$,
and so $(f-a)^{2}=O_{A}((f-a)^{4})$. This shows that

$\delta\leq
O_{A}(\operatorname*{\mathbb{E}}[(f-a)^{4}])=O_{A}(\|f-a\|_{4}^{4})\stackrel{{\scriptstyle(\ast)}}{{=}}O_{A}(\|f-a\|_{2}^{4})=O_{A}(\operatorname*{\mathbb{E}}[(f-a)^{2}]^{2}),$

using hypercontractivity in $(\ast)$. The $L_{2}^{2}$ triangle inequality
shows that

$\operatorname*{\mathbb{E}}[(f-a)^{2}]\leq
2\operatorname*{\mathbb{V}}[f]+2(\operatorname*{\mathbb{E}}[f]-a)^{2}\leq
2(2+m)\varepsilon+2(18+6m)\varepsilon=(40+14m)\varepsilon.$

Choosing $\varepsilon_{0}$ small enough (as a function of $A$), we can
guarantee that

$\varepsilon\geq\operatorname*{\mathbb{E}}[(f-a)^{2}](1-O_{A}(40+14m)\varepsilon)\geq\frac{1}{2}\operatorname*{\mathbb{E}}[(f-a)^{2}],$

and so $\operatorname*{\mathbb{E}}[(f-a)^{2}]\leq 2\varepsilon$. The lemma
follows from the well-known inequality
$\operatorname*{\mathbb{V}}[f]\leq\operatorname*{\mathbb{E}}[(f-a)^{2}]$. ∎

We now carry out the induction.

######  Lemma 8.3.

Fix a finite set $A$, and let $m,\varepsilon_{0}$ be the constants from Lemma
8.2. The following holds for all $\varepsilon\leq\varepsilon_{0}$.

Let $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ be a degree 1 function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$, let
$J=\\{i:\hat{f}(i)^{2}\geq m\varepsilon\\}$, and define
$g=\hat{f}(\emptyset)+\sum_{i\in J}\hat{f}(i)x_{i}$. Then $\|f-g\|^{2}\leq
2\varepsilon$.

###### Proof.

Assume without loss of generality that $J=\\{1,\ldots,N\\}$ for some $N<|A|$.
We will prove by reverse induction on $i\geq N$ that
$\sum_{j>i}\hat{f}(j)^{2}\leq 2\varepsilon$. The lemma will follow since
$\|f-g\|^{2}=\sum_{j>N}\hat{f}(j)^{2}$.

The base case $i=n$ is obvious, so assume that $\sum_{j>i+1}\hat{f}(j)^{2}\leq
2\varepsilon$ for some $i\geq N$. The definition of $J$ guarantees that
$\sum_{j>i}\hat{f}(j)^{2}\leq(2+m)\varepsilon$. Since
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$, there
must exist an assignment $\alpha$ to $x_{1},\ldots,x_{i}$ such that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f|_{\alpha},A)^{2}]\leq\varepsilon$.
Then $g=f|_{\alpha}$ satisfies
$\operatorname*{\mathbb{E}}[\operatorname{dist}(g,A)^{2}]\leq\varepsilon$ and
$\operatorname*{\mathbb{V}}[g]\leq(2+m)\varepsilon$. Lemma 8.2 shows that
$\operatorname*{\mathbb{V}}[g]\leq 2\varepsilon$, and so
$\sum_{j>i}\hat{f}(j)^{2}\leq 2\varepsilon$. ∎

To complete the proof, we need the following simple lemma.

######  Lemma 8.4.

For every finite set $A$ and every $x,y$ we have
$(x-\operatorname{round}(y,A))^{2}=O((x-y)^{2}+\operatorname{dist}(x,A)^{2})$.

###### Proof.

Let $a=\operatorname{round}(x,A)$ and $b=\operatorname{round}(y,A)$. If $a=b$
then $(x-b)^{2}=(x-a)^{2}=\operatorname{dist}(x,A)^{2}$. Otherwise, without
loss of generality $a<b$. Note that $x\leq\frac{a+b}{2}\leq y$. If
$|x-a|\leq\frac{b-a}{4}$ then $|x-y|\geq|x-\frac{a+b}{2}|\geq\frac{b-a}{4}$.
Therefore $(x-b)^{2}\leq 2(x-a)^{2}+2(a-b)^{2}\leq 2(x-a)^{2}+32(x-y)^{2}$. If
$|x-a|\geq\frac{b-a}{4}$ then $(x-b)^{2}\leq 2(x-a)^{2}+2(a-b)^{2}\leq
34(x-a)^{2}$. (In both cases, we used the $L_{2}^{2}$ triangle inequality.) ∎

The main theorem easily follows.

######  Theorem 8.5.

Fix a finite set $A$, and let $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ be a
degree 1 function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. There
exists a degree 1 function $g\colon\\{\pm 1\\}^{n}\to A$, depending on at most
$|A|-1$ coordinates, such that $\|f-g\|^{2}=O_{A}(\varepsilon)$.

###### Proof.

Let $\varepsilon_{0}$ be the constant from Lemma 8.3. Suppose first that
$\varepsilon\leq\varepsilon_{0}$. The lemma defines a set $J$ of size at most
$|A|-1$ (according to Lemma 8.1) such that $h:=\hat{f}(\emptyset)+\sum_{i\in
J}\hat{f}(i)x_{i}$ satisfies $\|f-h\|^{2}\leq 2\varepsilon$. Let
$g=\operatorname{round}(h,A)$, which also depends only on the coordinates in
$J$. Lemma 8.4 shows that
$\|f-g\|^{2}=O(\|f-h\|^{2}+\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}])=O(\varepsilon)$.

It remains to show that $\deg g\leq 1$. There are finitely many $A$-valued
functions on $|A|-1$ coordinates. Hence if $g^{>1}\neq 0$ then
$g^{>1}=\Omega_{A}(1)$, and so
$\|f-g\|^{2}\geq\|(f-g)^{>1}\|^{2}=\|g^{>1}\|^{2}=\Omega_{A}(1)$. By possibly
reducing $\varepsilon_{0}$, we can rule out this case, and so $\deg g\leq 1$.

If $\varepsilon>\varepsilon_{0}$ then we take $g=a$ for an arbitrary $a\in A$.
The $L_{2}^{2}$ triangle inequality shows that
$\operatorname*{\mathbb{E}}[f^{2}]\leq
2\operatorname*{\mathbb{E}}[\operatorname{round}(f,A)^{2}]+2\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=O_{A}(1+\varepsilon)$.
Another application of the triangle inequality shows that
$\operatorname*{\mathbb{E}}[(f-g)^{2}]\leq
2\operatorname*{\mathbb{E}}[f^{2}]+2a^{2}=O_{A}(1+\varepsilon)$. Since
$\varepsilon\geq\varepsilon_{0}$, in fact
$\operatorname*{\mathbb{E}}[(f-g)^{2}]=O_{A}(1+\varepsilon)=O_{A}(\varepsilon)$.
∎

######  Corollary 8.6.

Fix a finite set $A$, and let $F\colon\\{\pm 1\\}^{n}\to A$ satisfy
$\|F^{>1}\|^{2}=\varepsilon$. There exists a degree 1 function $g\colon\\{\pm
1\\}^{n}\to A$, depending on at most $|A|-1$ coordinates, such that
$\|F-g\|^{2}=O_{A}(\varepsilon)$ and $\Pr[F\neq g]=O_{A}(\varepsilon)$.

###### Proof.

Let $f=F^{\leq 1}$, which satisfies
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]\leq\operatorname*{\mathbb{E}}[(f-F)^{2}]=\varepsilon$.
The theorem gives an $A$-valued function $g$ which depends on at most $|A|-1$
coordinates and satisfies $\|f-g\|^{2}=O_{A}(\varepsilon)$. The $L_{2}^{2}$
triangle inequality shows that $\|F-g\|^{2}\leq
2\|f-g\|^{2}+2\|f-F\|^{2}=O_{A}(\varepsilon)$. If $F(x)\neq g(x)$ then
$(F(x)-g(x))^{2}=\Omega_{A}(1)$, and so $\Pr[F\neq
g]=\operatorname*{\mathbb{E}}[1_{F\neq
g}]=O_{A}(\operatorname*{\mathbb{E}}[(F-g)^{2}])=O_{A}(\varepsilon)$. ∎

###  8.2 A-valued Kindler–Safra theorem

We now prove the $A$-valued Kindler–Safra theorem by induction on the degree.
We start by stating the theorem.

######  Theorem 8.7.

Fix a finite set $A$ and a degree $d$. Let $f\colon\\{\pm
1\\}^{n}\to\mathbb{R}$ be a degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. There
exists a degree $d$ function $g\colon\\{\pm 1\\}^{n}\to A$, depending on
$O_{A,d}(1)$ coordinates, such that $\|f-g\|^{2}=O_{A,d}(\varepsilon)$.

We also get a corollary whose omitted proof is the same as that of Corollary
8.6.

######  Corollary 8.8.

Fix a finite set $A$ and a degree $d$. Let $F\colon\\{\pm 1\\}^{n}\to A$ be a
degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. There
exists a degree $d$ function $g\colon\\{\pm 1\\}^{n}\to A$, depending on
$O_{A,d}(1)$ coordinates, such that $\|F-g\|^{2}=O_{A,d}(\varepsilon)$ and
$\Pr[F\neq g]=O_{A,d}(\varepsilon)$.

The theorem clearly holds when $d=0$ (take $g=\operatorname{round}(f,A)$), and
it holds for $d=1$ due to Theorem 8.5. Consider now $d>1$. Assuming Theorem
8.7 for smaller $d$, we will prove it for the given $d$.

Let $f\colon\\{\pm 1\\}^{n}\to\mathbb{R}$ be a degree $d$ function satisfying
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$. As in
the proof of Theorem 8.5, if $\varepsilon>2^{-d}$ then
$\|f-a\|^{2}=O_{A}(\varepsilon)$ for any $a\in A$, allowing us to take $g=a$,
so assume that $\varepsilon\leq 2^{-d}$. This has the following implication:

######  Claim 8.9.

We have $\|f\|^{2}=O_{A}(1)$.

###### Proof.

The $L_{2}^{2}$ triangle inequality shows that

$\|f\|^{2}\leq
2\operatorname*{\mathbb{E}}[\operatorname{round}(f,A)^{2}]+2\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=O_{A}(1+\varepsilon)=O_{A}(1).\qed$

For a set $S\subseteq[n]$ and an assignment $y\in\\{\pm 1\\}^{\overline{S}}$,
let $f_{S,y}\colon\\{\pm 1\\}^{S}\to\mathbb{R}$ be the function obtained by
restricting the variables in $\overline{S}$ to the values in $y$, and define

$\varepsilon_{S,y}=\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{S,y},A)^{2}].$

######  Claim 8.10.

For all $S$,

$\operatorname*{\mathbb{E}}_{y\sim\\{\pm
1\\}^{\overline{S}}}[\varepsilon_{S,y}]=\varepsilon.$

###### Proof.

We have

$\operatorname*{\mathbb{E}}_{y\sim\\{\pm
1\\}^{\overline{S}}}[\varepsilon_{S,y}]=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}y\sim\\{\pm
1\\}^{\overline{S}}\\\ z\sim\\{\pm
1\\}^{S}\end{subarray}}[\operatorname{dist}(f(y,z),A)^{2}]=\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon.\qed$

For all $S$ and $y\in\\{\pm 1\\}^{\overline{S}}$, define

$\gamma_{S,y}=\|f_{S,y}^{=d}\|^{2},$

and let $\gamma_{S}=\operatorname*{\mathbb{E}}_{y}[\gamma_{S,y}]$.

######  Claim 8.11.

The value $\gamma_{S,y}$ doesn’t depend on $y$, and

$\operatorname*{\mathbb{E}}_{S\sim\mu_{\varepsilon^{1/d}}([n])}[\gamma_{S}]=\varepsilon\|f^{=d}\|^{2}=O_{A}(\varepsilon).$

###### Proof.

Note first that for all $y$,

$f_{S,y}^{=d}=\sum_{\begin{subarray}{c}|T|=d\\\ T\subseteq
S\end{subarray}}\hat{f}(T)x_{T}.$

Therefore $\gamma_{S,y}$ doesn’t depend on $y$, and

$\operatorname*{\mathbb{E}}_{S\sim\mu_{\varepsilon^{1/d}}([n])}[\gamma_{S}]=\sum_{|T|=d}\Pr_{S\sim\mu_{\varepsilon^{1/d}}([n])}[T\subseteq
S]\hat{f}(T)^{2}=\sum_{|T|=d}(\varepsilon^{1/d})^{d}\hat{f}(T)^{2}=\varepsilon\|f^{=d}\|^{2}.$

We complete the proof using 8.9. ∎

For each $S,y$, we apply Theorem 8.7 to the degree $d-1$ function
$f_{S,y}^{<d}$ which satisfies

$\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{S,y}^{<d},A)^{2}]\leq
2\operatorname*{\mathbb{E}}[\operatorname{dist}(f_{S,y},A)^{2}]+2\|f_{S,y}^{=d}\|^{2}=2\varepsilon_{S,y}+2\gamma_{S}.$

The theorem gives us an $A$-valued function $g_{S,y}$ which depends on
$O_{A,d}(1)$ coordinates and satisfies

$\|f_{S,y}^{<d}-g_{S,y}\|^{2}=O_{A,d}(\varepsilon_{S,y}+\gamma_{S}).$

Since $g_{S,y}$ is an $A$-valued junta, there exists a finite set $B$
(depending only on $A,d$) such that all Fourier coefficients of $g_{S,y}$
belong to $B$.

A simple calculation shows that for all $T\subseteq S$ of size $d-1$,

$h_{S,T}(y):=\hat{f}_{S,y}(T)=\hat{f}(T)+\sum_{i\notin S}\hat{f}(T+i)y_{i}.$

We think of this as a degree 1 function $h_{S,T}\colon\\{\pm
1\\}^{\overline{S}}\to\mathbb{R}$.

######  Claim 8.12.

For all $S\subseteq[n]$ we have

$\sum_{T\in\binom{S}{d-1}}\operatorname*{\mathbb{E}}[\operatorname{dist}(h_{S,T},B)^{2}]=O_{A,d}(\varepsilon+\gamma_{S}).$

###### Proof.

For each $y\in\\{\pm 1\\}^{\overline{S}}$ we have

$\sum_{T\in\binom{S}{d-1}}\operatorname{dist}(h_{S,T}(y),B)^{2}\leq\sum_{T\in\binom{S}{d-1}}(\hat{f}_{S,y}(T)-\hat{g}_{S,y}(T))^{2}\leq\|f_{S,y}^{<d}-g_{S,y}\|^{2}=O_{A,d}(\varepsilon_{S,y}+\gamma_{S}).$

Taking expectation over $y$, we complete the proof using 8.10. ∎

On the other hand, an application of the generalized FKN theorem gives the
following:

######  Claim 8.13.

There exists a finite set $C$ (depending only on $A,d$) such that for all
$S\subseteq[n]$ and $T\in\binom{S}{d-1}$,

$\operatorname{dist}(\hat{f}(T),C)^{2}+\sum_{i\notin
S}\operatorname{dist}(\hat{f}(T+i),C)^{2}=O_{A,d}(\operatorname*{\mathbb{E}}[\operatorname{dist}(h_{S,T},B)^{2}]).$

###### Proof.

Theorem 8.5, applied to $f:=h_{S,T}$ and $A:=B$, gives a $B$-valued function
$u_{S,T}$ depending on at most $|B|-1$ coordinates such that
$\|h_{S,T}-u_{S,T}\|^{2}=O_{A,d}(\operatorname*{\mathbb{E}}[\operatorname{dist}(h_{S,T},B)^{2}])$.
All the Fourier coefficients of $u_{S,T}$ belong to some finite set $C$, and
so the claim follows from Parseval’s identity since the coefficients of the
Fourier expansion of $h_{S,T}$ are $\hat{h}_{S,T}(\emptyset)=\hat{f}(T)$ and
$\hat{h}_{S,T}(i)=\hat{f}(T+i)$ for all $i\notin S$. ∎

Putting both claims together, we deduce:

######  Claim 8.14.

We have

$\sum_{d-1\leq|T|\leq
d}\operatorname{dist}(\hat{f}(T),C)^{2}=O_{A,d}(\varepsilon^{1/d}).$

###### Proof.

Summing over $T$ in 8.13 and using 8.12, we get that for all $S\subseteq[n]$,

$\sum_{T\in\binom{S}{d-1}}\left[\operatorname{dist}(\hat{f}(T),C)^{2}+\sum_{i\notin
S}\operatorname{dist}(\hat{f}(T+i),C)^{2}\right]=\sum_{T\in\binom{S}{d-1}}O_{A,d}(\operatorname*{\mathbb{E}}[\operatorname{dist}(h_{S,T},B)^{2}])=O_{A,d}(\varepsilon+\gamma_{S}).$

Taking expectation with respect to $S\sim\mu_{\delta}$, where
$\delta=\varepsilon^{1/d}$, 8.11 shows that

$\operatorname*{\mathbb{E}}_{S\sim\mu_{\delta}}\left[\sum_{T\in\binom{S}{d-1}}\operatorname{dist}(\hat{f}(T),C)^{2}+\sum_{i\notin
S}\operatorname{dist}(\hat{f}(T+i),C)^{2}\right]=O_{A,d}(\varepsilon).$

A set $T$ of size $d-1$ appears in the sum with probability $\delta^{d-1}$,
and a set of size $d$ appears with probability $d\delta^{d-1}(1-\delta)$.
Since $\delta\leq(2^{-d})^{1/d}=1/2$ by assumption, we deduce that

$\sum_{d-1\leq|T|\leq
d}\operatorname{dist}(\hat{f}(T),C)^{2}=O_{A,d}(\varepsilon/\delta^{d-1})=O_{A,d}(\varepsilon^{1/d}).\qed$

This claim prompts defining

$h=\sum_{d-1\leq|T|\leq d}\operatorname{round}(\hat{f}(T),C)x_{T}.$

######  Claim 8.15.

There exists a finite set $D$ (depending only on $A,d$) such that $h$ is a
$D$-valued function depending on $O_{A,d}(1)$ coordinates and satisfying
$\|h\|^{2}=O_{A,d}(1)$.

###### Proof.

8.14 shows that $\|h-f^{\geq
d-1}\|^{2}=O_{A,d}(\varepsilon^{1/d})=O_{A,d}(1)$. Since
$\|f\|^{2}=O_{A,d}(1)$ by 8.9, it follows that $\|h\|^{2}=O_{A,d}(1)$ and so
$\sum_{S}\hat{h}(S)^{2}=O_{A,d}(1)$. As all Fourier coefficients of $h$ belong
to $C$, we deduce that $h$ has $O_{A,d}(1)$ non-zero coefficients. Since all
of them involve at most $d$ coordinates, it follows that $h$ depends on
$O_{A,d}(1)$ coordinates. Each value of $h$ is a signed sum of $O_{A,d}(1)$
elements of $C$, and so $h$ is $D$-valued for some finite set $D$. ∎

The next step is an application of Theorem 8.7 for degree $d-2$.

######  Claim 8.16.

There exists a finite set $E$ (depending only on $A,d$) and an $E$-valued
degree $d-2$ function $g$ depending on $O_{A,d}(1)$ coordinates such that
$\|f-(g+h)\|^{2}=O_{A,d}(\varepsilon^{1/d})$.

###### Proof.

Let $\tilde{f}=f^{<d-1}+h$. Then $\|f-\tilde{f}\|^{2}=\|f^{\geq
d-1}-h\|^{2}=O_{A,d}(\varepsilon^{1/d})$ by 8.14, and so the $L_{2}^{2}$
triangle inequality shows that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(\tilde{f},A)^{2}]\leq
2\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]+2\|f-\tilde{f}\|^{2}=O_{A,d}(\varepsilon+\varepsilon^{1/d})=O_{A,d}(\varepsilon^{1/d})$
(using $\varepsilon\leq 2^{-d}$). Setting $E$ to be the Minkowski difference
$A-D$ and using the fact that $h$ is $D$-valued, we deduce that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f^{<d-1},E)^{2}]=O_{A,d}(\varepsilon^{1/d})$.

Applying Theorem 8.7 to the degree $d-2$ function $f^{<d-1}$, we obtain an
$E$-valued degree $d-2$ function $g$ depending on $O_{A,d}(1)$ coordinates
such that $\|f^{<d-1}-g\|^{2}=O_{A,d}(\varepsilon^{1/d})$. Together with
$\|f^{\geq d-1}-h\|^{2}=O_{A,d}(\varepsilon^{1/d})$ and the $L_{2}^{2}$
triangle inequality, this shows that
$\|f-(g+h)\|^{2}=O_{A,d}(\varepsilon^{1/d})$. ∎

Using the fact that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$, we can
improve the bound on $\|f-(g+h)\|^{2}$.

######  Claim 8.17.

We have $\|f-(g+h)\|^{2}=O_{A,d}(\varepsilon)$.

###### Proof.

Let $s:=f-(g+h)$. Since
$\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}]=\varepsilon$ and
$g+h$ is $(D+E)$-valued (where $D+E$ is the Minkowski sum), we see that
$\operatorname*{\mathbb{E}}[\operatorname{dist}(s,V)^{2}]\leq\varepsilon$,
where $V=A-(D+E)$ is a finite set. We can assume without loss of generality
that $0\in V$ (this can only decrease the distance). At any point in the
domain, either $\operatorname{round}(s,V)=0$ or
$\operatorname{round}(s,V)=\Omega_{A}(1)$. Hence

$\varepsilon\geq\operatorname*{\mathbb{E}}[\operatorname{dist}(s,V)^{2}1_{\operatorname{round}(s,V)=0}]=\operatorname*{\mathbb{E}}[s^{2}1_{\operatorname{round}(s,V)=0}]=\operatorname*{\mathbb{E}}[s^{2}]-\operatorname*{\mathbb{E}}[s^{2}1_{\operatorname{round}(s,V)\neq
0}]\geq\operatorname*{\mathbb{E}}[s^{2}]-O_{A}(\operatorname*{\mathbb{E}}[s^{2d}]).$

Since $\deg(s^{2d})\leq 2d^{2}$, hypercontractivity shows that
$\operatorname*{\mathbb{E}}[s^{2d}]=\|s\|_{2d}^{2d}=O_{d}(\|s\|_{2}^{2d})$,
and so 8.16, which states that
$\operatorname*{\mathbb{E}}[s^{2}]=O_{A,d}(\varepsilon^{1/d})$, implies that

$\operatorname*{\mathbb{E}}[s^{2}]\leq\varepsilon+O_{A,d}(\operatorname*{\mathbb{E}}[s^{2}]^{d})=O_{A,d}(\varepsilon).\qed$

We can now complete the proof.

###### Completion of the proof of Theorem 8.7.

Let $r=\operatorname{round}(g+h,A)$, and note that $r$ depends on $O_{A,d}(1)$
coordinates. Lemma 8.4 shows that
$\|f-r\|^{2}=O(\|f-(g+h)\|^{2}+\operatorname*{\mathbb{E}}[\operatorname{dist}(f,A)^{2}])=O_{A,d}(\varepsilon)$.
If $\deg r>d$ then since $r$ is an $A$-valued function depending on
$O_{A,d}(1)$ coordinates, we have $\|r^{>d}\|^{2}=\Omega_{A,d}(1)$, implying
that $\|f-r\|^{2}=\Omega_{A,d}(1)$ and so $\varepsilon=\Omega_{A,d}(1)$. As in
the proof of Theorem 8.5, in this case $\|f-a\|^{2}=O_{A,d}(\varepsilon)$ for
any $a\in A$. ∎

## References

  * [BGH+15] Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer.  _Making the long code shorter_.  SIAM J. Comput., 44(5):1287–1324, 2015.  (Preliminary version in 53rd FOCS, 2012).  arXiv:1111.0405, eccc:2011/TR11-142, doi:10.1137/130929394.
  * [Bou99] Jean Bourgain.  _On sharp threshold of monotone properties_.  J. Amer. Math. Soc., 12(4):1017–1054, 1999.  (Appendix to E. Friedgut, Sharp Thresholds of Graph Properties, and the $k$-Sat Problem).  doi:10.1090/S0894-0347-99-00305-7.
  * [Bou02] ———.  _On the distribution of the Fourier spectrum of Boolean functions_.  Israel Journal of Mathematics, 131(1):269–276, 2002.  doi:10.1007/BF02785861.
  * [DFH17] Irit Dinur, Yuval Filmus, and Prahladh Harsha.  _Agreement tests on graphs and hypergraphs_ , 2017.  (manuscript).
  * [DG08] Irit Dinur and Elazar Goldenberg.  _Locally testing direct product in the low error range_.  In _Proc. $49$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, pages 613–622. 2008.  doi:10.1109/FOCS.2008.26.
  * [DKK+16] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  _Towards a proof of the 2-to-1 games conjecture?_ Technical Report 2016/TR16-198, Elect. Colloq. on Comput. Complexity (ECCC), 2016.  eccc:2016/TR16-198.
  * [DKK+17] ———.  _On non-optimally expanding sets in Grassmann graphs_.  Technical Report 2017/TR17-094, Elect. Colloq. on Comput. Complexity (ECCC), 2017.  eccc:2017/TR17-094.
  * [DS14] Irit Dinur and David Steurer.  _Direct product testing_.  In _Proc. $29$th IEEE Conf. on Comput. Complexity_, pages 188–196. 2014.  eccc:2013/TR13-179, doi:10.1109/CCC.2014.27.
  * [Fil16] Yuval Filmus.  _Friedgut-Kalai-Naor theorem for slices of the boolean cube_.  Chicago J. Theor. Comput. Sci., 2016(14), 2016.  arXiv:1410.7834, doi:10.4086/cjtcs.2016.014.
  * [FK96] Ehud Friedgut and Gil Kalai.  _Every monotone graph property has a sharp threshold_.  Proc. Amer. Math. Soc., 124(10):2993–3002, 1996.  doi:10.1090/S0002-9939-96-03732-X.
  * [FKN02] Ehud Friedgut, Gil Kalai, and Assaf Naor.  _Boolean functions whose Fourier transform is concentrated on the first two levels and neutral social choice_.  Adv. Appl. Math., 29(3):427–437, 2002.  doi:10.1016/S0196-8858(02)00024-6.
  * [Fri98] Ehud Friedgut.  _Boolean functions with low average sensitivity depend on few coordinates_.  Combinatorica, 18(1):27–35, 1998.  doi:10.1007/PL00009809.
  * [Fri99] ———.  _Sharp thresholds of graph properties, and the $k$-sat problem_.  J. Amer. Math. Soc., 12(4):1017–1054, 1999.  doi:10.1090/S0894-0347-99-00305-7.
  * [Hat12] Hamed Hatami.  _A structure theorem for Boolean functions with small total influences_.  Ann. of Math., 176(1):509–533, 2012.  doi:10.4007/annals.2012.176.1.9.
  * [IKW12] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.  _New direct-product testers and 2-query PCPs_.  SIAM J. Comput., 41(6):1722–1768, 2012.  (Preliminary version in 41st STOC, 2009).  eccc:2009/TR09-090, doi:10.1137/09077299X.
  * [Kin03] Guy Kindler.  _Property Testing, PCP and Juntas_.  Ph.D. thesis, Tel Aviv University, 2003.  eccc:2016/TR16-007.
  * [KKL88] Jeff Kahn, Gil Kalai, and Nathan Linial.  _The influence of variables on Boolean functions (extended abstract)_.  In _Proc. $29$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, pages 68–80. 1988.  doi:10.1109/SFCS.1988.21923.
  * [KKM+17] Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, and Rüdiger L. Urbanke.  _Reed-Muller codes achieve capacity on erasure channels_.  IEEE Trans. Inform. Theory, 63(7):4298–4316, 2017.  (Preliminary version in 48th STOC, 2016).  arXiv:1601.04689, doi:10.1109/TIT.2017.2673829.
  * [KM13] Subhash Khot and Dana Moshkovitz.  __NP_ -hardness of approximately solving linear equations over reals_.  SIAM J. Comput., 42(3):752–791, 2013.  (Preliminary version in 43rd STOC, 2011).  eccc:2010/TR10-053, doi:10.1137/110846415.
  * [KMS17] Subhash Khot, Dor Minzer, and Muli Safra.  _On independent sets, 2-to-2 games, and Grassmann graphs_.  In _Proc. $49$th ACM Symp. on Theory of Computing (STOC)_, pages 576–589. 2017.  eccc:2016/TR16-124, doi:10.1145/3055399.3055432.
  * [KS02] Guy Kindler and Shmuel Safra.  _Noise-resistant Boolean functions are juntas_ , 2002.  (manuscript).
  * [NS94] Noam Nisan and Mario Szegedy.  _On the degree of Boolean functions as real polynomials_.  Comput. Complexity, 4:301–313, 1994.  (Preliminary version in 24th STOC, 1992).  doi:10.1007/BF01263419.
  * [O’D14] Ryan O’Donnell.  _Analysis of Boolean Functions_.  Cambridge University Press, 2014.  doi:10.1017/CBO9781139814782.