# A strong composition theorem for junta complexity
and the boosting of property testers

Guy Blanc
Stanford Caleb Koch
Stanford Carmen Strassle
Stanford Li-Yang Tan
Stanford

###### Abstract

We prove a strong composition theorem for junta complexity and show how such
theorems can be used to generically boost the performance of property testers.

The $\varepsilon$-approximate junta complexity of a function $f$ is the
smallest integer $r$ such that $f$ is $\varepsilon$-close to a function that
depends only on $r$ variables. A strong composition theorem states that if $f$
has large $\varepsilon$-approximate junta complexity, then $g\circ f$ has even
larger $\varepsilon’$-approximate junta complexity, even for
$\varepsilon’\gg\varepsilon$. We develop a fairly complete understanding of
this behavior, proving that the junta complexity of $g\circ f$ is
characterized by that of $f$ along with the multivariate noise sensitivity of
$g$. For the important case of symmetric functions $g$, we relate their
multivariate noise sensitivity to the simpler and well-studied case of
univariate noise sensitivity.

We then show how strong composition theorems yield boosting algorithms for
property testers: with a strong composition theorem for any class of
functions, a large-distance tester for that class is immediately upgraded into
one for small distances. Combining our contributions yields a booster for
junta testers, and with it new implications for junta testing. This is the
first boosting-type result in property testing, and we hope that the
connection to composition theorems adds compelling motivation to the study of
both topics.

###### Contents

  1. 1 Introduction
  2. 2 Our results and techniques
    1. 2.1 First main result: A strong composition theorem for junta complexity
      1. 2.1.1 Context and motivation: Counterexamples to natural composition theorems
      2. 2.1.2 Our Strong Composition Theorem
    2. 2.2 Second main result: Composition theorems and boosting of property testers
      1. 2.2.1 Example applications of Theorem 2: New implications for junta testing
  3. 3 Other related work
  4. 4 Discussion and future work
  5. 5 Preliminaries
    1. 5.1 Fourier Analysis
  6. 6 A strong composition theorem for juntas
    1. 6.1 Proof of the lower bound on advantage
      1. 6.1.1 Characterizing the advantage of composed form approximators
      2. 6.1.2 Unbalanced noise stability behaves strangely
      3. 6.1.3 Unbalanced noise stability behaves well if we use the best $h$
    2. 6.2 Proof of the upper bound on advantage
    3. 6.3 Proofs of the consequences of our strong composition theorem
  7. 7 Multivariate noise stability of symmetric functions
    1. 7.1 The upper bound on the multivariate noise stability of symmetric functions
    2. 7.2 The lower bound on the multivariate noise stability of symmetric functions
    3. 7.3 Bounding the $(\delta,\varepsilon)$-noise stability of symmetric functions
  8. 8 Composition theorems yield boosters for property testing
    1. 8.1 A general boosting framework
    2. 8.2 Implications for current landscape of junta testing
      1. 8.2.1 Noise stability of parity under general product distributions
      2. 8.2.2 Warmup: weak testers suffice for $(0,\varepsilon,r,r^{\prime})$-testing juntas
      3. 8.2.3 Weak testers suffice for tolerant junta testing
      4. 8.2.4 Hardness of distribution-free tolerant junta testing
  9. A Counterexamples to natural composition theorems
    1. A.1 Counterexample to Conjecture 1
    2. A.2 Counterexample to Conjecture 2
    3. A.3 Counterexample to Conjecture 3

##  1 Introduction

The growth in the sizes of modern datasets is both a blessing and a curse.
These datasets, many of which now come with billions of features, contain a
wealth of information that machine learning algorithms seek to tap into. On
the other hand, their size stands in the way of the opportunities they
present, as many of the algorithms that we would like to run on them simply
cannot handle their dimensionality.

Thankfully, for many tasks of interest the vast majority of features are
irrelevant. This motivates the design of algorithms that are able to quickly
home in on the small number of relevant features, and whose efficiency scales
gracefully with the number of such features. Already in the early 1990s Blum
[Blu94] (see also [BL97, Blu03]) proposed the clean theoretical challenge of
learning an unknown $r$-junta, a function that depends on $r\ll n$ many of its
$n$ variables. Quoting [Blu94], “It is my belief that some of the most central
open problems in computational learning theory are, at their core, questions
about finding relevant variables.” This is now known simply as the junta
problem and is the subject of intensive study [BHL95, MOS04, AR07, AS07,
KLM+09, AM10, ST11, Bel15, Val15, ABR16, CJLW21, CNY23], having distinguished
itself as “the single most important open question in uniform distribution
learning” [MOS04].

The premise of the junta problem suggests an even more basic algorithmic
problem, that of determining if an unknown function is even an $r$-junta to
begin with. This is the problem of testing juntas, introduced by Fischer,
Kindler, Ron, Safra, and Samorodnitsky [FKR+04] and subsequently studied in
numerous works [CG04, AS07, Bla08, Bla09, CGSM11, BGSMdW13, STW15, ABR16,
ABRW16, BKT18, Sağ18, LCS+18, CST+18, BCE+18, Bsh19, Bel19, LW19, DMN19,
CJLW21, ITW21, PRW22, CNY23]. Junta testers are also at the heart of the best
known testers for numerous other classes of functions, the key insight being
that many functions are well-approximated by small juntas (see [DLM+07, Ser10]
and Chapter 5 of [Ron10] for more on this connection). The surveys by Blais
[Bla10, Bla16] give broad overviews of various junta testers and their
applications throughout theoretical computer science.

##### This work.

These algorithmic applications motivate the study of approximability by small
juntas as a complexity measure. For a function $f:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ and a distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$, the
$\varepsilon$-approximate junta complexity of $f$ with respect to
$\mathcal{D}$, denoted $J_{\mathcal{D}}(f,\varepsilon)$, is the smallest
integer $r$ such that $f$ is $\varepsilon$-close to an $r$-junta. Among the
most basic questions one can ask about any complexity measure of functions is
how it behaves under composition. In the first part of this paper we develop,
from the ground up, a fairly complete understanding of this question for junta
complexity. We prove a near-optimal composition theorem (Theorem 1) that is
built on notions of noise stability, both classical and new. In the second
part we draw a general connection (Theorem 2) between the type of composition
theorem that we prove—a strong composition theorem, which we will soon
define—and property testing, showing how they can be used to design the first
generic boosters for property testers. Combining our two main contributions
yields new implications for junta testing.

##  2 Our results and techniques

###  2.1 First main result: A strong composition theorem for junta complexity

Composition theorems are statements about hardness amplification: the goal is
to understand the extent to which the disjoint composition $(g\circ
f)(x)\coloneqq g(f(x^{(1)}),\ldots,f(x^{(k)}))$ is more complex than $f$
itself, and how this depends on intrinsic properties of the combining function
$g$. For approximate measures such has junta complexity, we are furthermore
interested in strong composition theorems, statements of the form:

$J_{\mathcal{D}^{k}}(g\circ f,\varepsilon_{\mathrm{large}})\gg
J_{\mathcal{D}}(f,\varepsilon_{\mathrm{small}})\ \ \text{even for}\ \
\varepsilon_{\mathrm{large}}\gg\varepsilon_{\mathrm{small}}.$ ($\diamondsuit$)

In words, the composed function requires much more resources—in our case, much
larger junta approximators—even if one only seeks a much coarser
approximation. Strong composition theorems stand in contrast to weak ones that
only amplify hardness with respect to one of the two parameters, either
resources or approximation quality only. The canonical example in this context
is Yao’s XOR lemma [Yao82], which says that if $f$ is mildly hard to
approximate with size-$s$ circuits, then $\mathrm{XOR}\circ f$ is extremely
hard to approximate with size-$s’$ circuits. A long-recognized downside of
this important result, inherent to all known proofs of it [Lev85, GNW11,
Imp95, IW97] and its generalizations to arbitrary combining functions [O’D02],
is the fact that it is only known to hold for $s’\ll s$, whereas intuitively
it should hold even for $s’\gg s$.

Composition theorems, both weak and strong, have been studied for a variety of
complexity measures but appear to have been underexplored for junta
complexity. One reason may be that the question appears deceptively simple.
Indeed, things are completely straightforward in the zero-error setting, where
we have the intuitive identity $J(g\circ f,0)=J(g,0)\cdot J(f,0)$. However, we
show that the question becomes surprisingly intricate once error is allowed.

####  2.1.1 Context and motivation: Counterexamples to natural composition
theorems

The question proves to be tricky even in the special case where the combining
function $g$ is symmetric. We now state a sequence of three seemingly
intuitive conjectures for this special case. While false, these conjectures
and their counterexamples will motivate and lead us to the statement of our
actual composition theorem. (Details and proofs of the counterexamples
discussed in this section are given in Appendix A.)

The following notation will be useful for us throughout this paper:

##### Notation.

For a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mathcal{D}$
over $\\{\pm 1\\}^{n}$, and integer $r$, we write $\tilde{f}_{\mathcal{D},r}$
to denote the best $r$-junta approximator of $f$ with respect to
$\mathcal{D}$. When $\mathcal{D}$ is clear from context, we simply write
$\tilde{f}_{r}$.

##### Conjecture 1.

It will be convenient for us to consider composition theorems in their
contrapositive form. Suppose we would like to approximate $g\circ f$ with an
$R$-junta, say with respect to the uniform distribution. If $g$ is a
$k$-variable symmetric function, how would we go about constructing an
approximator that achieves the highest accuracy possible? Since $g$ is
symmetric, one may be inclined to divide the “junta budget” of $R$ evenly
among the $k$ inner functions and conjecture that

$g\circ\tilde{f}_{R/k}=g(\tilde{f}_{R/k},\ldots,\tilde{f}_{R/k})$

achieves the best, or close to the best, accuracy among all $R$-junta
approximators.

However, this is badly false. Let $g$ be the $k$-variable Majority function
and $f$ the $n$-variable Parity function. For any choice of $R$ satisfying
$R/k<n$ (i.e. each inner Parity receiving a budget that falls short of its
arity), we have $\mathrm{Pr}[g\circ\tilde{f}_{R/k}\neq g\circ f]=\frac{1}{2}.$
This is because it is “all or nothing” when it comes to approximating Parity:
no ($n-1$)-junta can achieve accuracy better than that of a constant
approximator. The best strategy is therefore to allocate a full budget of $n$
to as many of the inner Parities as possible (i.e. $R/n$ many of them), and a
budget of zero to the others. This shows a gap of $\frac{1}{2}$ versus
$1-o(1)$ in the accuracies of the “divide budget equally” strategy and the
optimal one.

##### Conjecture 2.

In light of this counterexample, one may then conjecture that the best
strategy is to partition the junta budget optimally among the $k$ inner
functions and feed the respective approximators of $f$ into $g$. That is, the
conjecture is that the best approximator is of the form:

$g(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}})\text{ where
}\sum_{i=1}^{k}r_{i}=R.$

While this is true for our example above, it is again badly false in general.
In fact, the error of such an approximator can be close to $1$, even worse
than the trivial bound of $\leq\frac{1}{2}$ achievable with a constant
approximator.

Our counterexample reveals another counterintuitive aspect of the overall
problem. Consider an approximator for $g\circ f$ of the form
$g(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}).$ We show its approximation
accuracy can increase if we replace one of the inner approximators for $f$
with a worse one: e.g. if we replace $\tilde{f}_{r_{1}}$ with
$\tilde{f}_{{r_{1}}’}$ where ${r_{1}}’<r_{1}$. In more technical terms that we
will soon define: while the noise stability of a function is, as one would
expect, monotone in the noise rate, we show that the natural generalization of
it where the corruption probabilities of $0$’s and $1$’s are decoupled
(defined in Section 6.1) is not monotone.

##### Conjecture 3.

Finally, we consider a conjecture that is far laxer than either of the
previous ones. It simply states that the optimal approximator for the composed
function $g\circ f$ is one of composed form:

$h(q^{(1)},\ldots,q^{(k)})\text{ for some $h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$
and $q^{(1)},\ldots,q^{(k)}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,}$

where the relevant variables of $q^{(i)}$ fall within the $i$th block of
variables. We show (to our own surprise) that this conjecture is still false:
there are composed functions for which the optimal approximator is not of
composed form. However, unlike the first two conjectures, our work shows that
this conjecture is morally true in a precise sense.

####  2.1.2 Our Strong Composition Theorem

Our strong composition theorem implies a close quantitative relationship
between the error of the optimal approximator and that of the optimal composed
form approximator, and indeed one with a specific structure that we call
canonical:

######  Definition 1 (Canonical composed form approximators).

We say that a composed form approximator for $g\circ f$ is canonical if it is
of the form:

$h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}),$

where $h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ is the function:

$h(y)=\mathrm{sign}\bigg{(}\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\Big{[}(g\circ
f)(\bm{x})\mid\text{$y_{i}=\tilde{f}_{r_{i}}(\bm{x}^{(i)})$ for all
$i\in[k]$}\Big{]}\bigg{)}.$

For intuition regarding the choice of $h$, we note that for the fixed
$k$-tuple of functions $\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}$, it is the
combining function that minimizes error with respect to $g\circ f$. Canonical
composed form approximators are therefore ones whose individual components are
“locally” optimal: each $\tilde{f}_{r_{i}}$ is the optimal $r_{i}$-junta
approximator for $f$, and $h$ the optimal way of combining the $f_{r_{i}}$’s.
Our strong composition theorem will say that we can get very close to the
globally optimal approximator this way.

The notion of noise stability is central to our work:

######  Definition 2 (Multivariate noise stability).

For any $\mu\in(-1,1)$ and vector $\vec{\rho}\in[0,1]^{k}$, we define the
multivariate noise stability of $g$ as

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}[g(\bm{y})g(\bm{z})]$

where independently for each $i\in[k]$, we draw $(\bm{y}_{i}$, $\bm{z}_{i})$
as follows: Using $\pi_{\mu}$ to denote the unique distribution supported on
$\\{\pm 1\\}$ with mean $\mu$, $\bm{y}_{i}\sim\pi_{\mu}$, and

$\bm{z}_{i}=\begin{cases}\bm{y}_{i}&\text{w.p.~{}}\vec{\rho}_{i}\\\
\text{Independent draw from
$\pi_{\mu}$}&\text{w.p.~{}}1-\vec{\rho}_{i}.\end{cases}$

When $\mu=0$ we simply write $\mathrm{Stab}_{\vec{\rho}}(g)$.

This definition allows for a different noise rate for each coordinate,
generalizing the more commonly studied definition where the noise rates are
the same for every coordinate (see e.g. Chapter 2 of [O’D14]). We use the
terms multivariate noise stability and univariate noise stability to
distinguish these definitions. Even in the case of symmetric combining
functions $g$, our strong composition theorem will naturally involve its
multivariate noise stability (necessarily so, as already suggested by the
counterexample to Conjecture 1).

We present our strong composition theorem as a sequence of two parts that each
carries a standalone message, the first of which formalizes the fact that the
optimal canonical composed form approximator is a good proxy for the actual
optimal approximator. It will be more convenient for us to state our results
in terms of advantage instead of error, the two quantities being related via
the identity $\text{advantage}=1-2\cdot\text{error}$. Also, for notational
clarity we only state here the special case where $f$ is balanced (i.e.
$\operatorname{{\mathds{E}}}_{\mathcal{D}}[f]=0$).

######  Theorem 1 (Part I: Canonical composed form approximators are near
optimal).

Let $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ be
arbitrary functions and $\mathcal{D}$ be any distribution over $\\{\pm
1\\}^{n}$. Assume that $\operatorname{{\mathds{E}}}_{\mathcal{D}}[f]=0$. For
the task of approximating $g\circ f$ under $\mathcal{D}^{k}$ with an
$R$-junta, there is a correlation vector $\vec{\rho}\in[0,1]^{k}$ such that
$\displaystyle\mathrm{Stab}_{\vec{\rho}}(g)^{2}$
$\displaystyle\leq\textnormal{Advantage of optimal canonical composed form
approximator}$ $\displaystyle\leq\textnormal{Advantage of optimal
approximator}\leq\sqrt{\mathrm{Stab}_{\vec{\rho}}(g)}.$

For most applications of composition theorems, including those in this paper,
the parameters of interest are such that the quartic gap between the upper and
lower bounds above are inconsequential. (In particular, if the advantage of
the optimal canonical composed form approximator diminishes to $0$ as $k$
grows, our bounds imply that the same is true for the actual optimal
approximator. Indeed, the two rates of convergence are the same up to a
polynomial factor.)

Part II of Theorem 1 elaborates on the correlation vector $\vec{\rho}$,
showing how it is is determined by the junta complexity of $f$ and the noise
stability of $g$:

Theorem 1 (Part II: Explicit description of $\vec{\rho}$). The correlation
vector $\vec{\rho}\in[0,1]^{k}$ in Part I is the vector that maximizes
$\mathrm{Stab}_{\vec{\rho}}(g)$, subject to the constraint:
$\vec{\rho}_{i}=\mathop{{\mathds{E}}\/}_{\mathcal{D}}\big{[}f\cdot\tilde{f}_{r_{i}}\big{]}\text{
for all $i\in[k]$ where }\displaystyle\sum_{i=1}^{k}r_{i}=R.$

Taken together, the two parts of Theorem 1 show that the junta complexity of
$g\circ f$ is tightly characterized by the junta complexity of $f$ and the
multivariate noise stability of $g$. It furthermore gives a simple and
explicit strategy for constructing a near-optimal approximator: first
partition the junta budget optimally among the $k$ inner functions; next
approximate each inner function optimally with its allocated budget; and
finally combine these approximators in the optimal way.

Naturally, it would be preferable to understand the strategy for constructing
the actual optimal approximator, but our counterexamples suggest that it
defies a clean and interpretable description even for symmetric $g$ (indeed,
even for $g$ being the And function).

##### Corollary: Highly noise sensitive functions strongly amplify junta
complexity.

Theorem 1 yields a hardness amplification statement of the form $\diamondsuit$
‣ 2.1 the following way. Suppose $f$ is mildly hard for $r$-juntas, i.e.
$\operatorname{{Pr}}[\tilde{f}_{r}\neq f]\geq\varepsilon_{\mathrm{small}}$.
Our goal is to show that $g\circ f$ is extremely hard for $R$-juntas,
$\operatorname{{Pr}}[(g\circ f)_{R}\neq g\circ
f]\eqqcolon\varepsilon_{\mathrm{large}}\gg\varepsilon_{\mathrm{small}}$, even
for $R\gg r$. For any partition of $R=\sum_{i=1}^{k}r_{i}$, at most a
$0.999$-fraction of the $r_{i}$’s exceed $1.01R/k\eqqcolon r$. Theorem 1
therefore tells us that the advantage of the optimal $R$-junta is upper
bounded by

$\sqrt{\mathrm{Stab}_{\vec{\rho}}(g)}\text{ where at least a $0.001$-fraction
of $\vec{\rho}$'s coordinates are at most
$1-2\cdot\varepsilon_{\mathrm{small}}$.}$

(Equivalently, at least a $0.001$-fraction of coordinates receive at least an
$\varepsilon_{\mathrm{small}}$ amount of noise.)

This motivates the following definition:

######  Definition 3 (Stability under partial noise).

The $(\delta,\varepsilon)$-noise stability of a function $g:\\{\pm
1\\}^{k}\to\\{\pm 1\\}$ is the quantity

$\max\big{\\{}\mathrm{Stab}_{\vec{\rho}}(g)\colon\text{at least a
$\delta$-fraction of $\vec{\rho}$'s coordinates are at most
$1-2\varepsilon$}\big{\\}}.$

By the monotonicity of noise stability, this maximum is achieved by a
$\vec{\rho}$ with exactly a $\delta$-fraction of coordinates being exactly
$1-2\varepsilon$, and the remaining $(1-\delta)$-fraction being $1$.

We have sketched the following corollary of Theorem 1:

######  Corollary 2.1 (Highly noise sensitive functions strongly amplify junta
complexity).

Let $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ be a function whose
$(\frac{1}{2},\varepsilon_{\mathrm{small}})$-noise stability is at most
$\tau$. Then for all functions $f$,

$\mathop{\underbrace{J_{\mathcal{D}^{k}}\big{(}g\circ
f,\tfrac{1}{2}(1-\sqrt{\tau})\big{)}}_{\textup{Junta complexity of $g\circ
f$}}}_{\textup{for large error}}\geq
0.99k\cdot\mathop{\underbrace{J_{\mathcal{D}}(f,\varepsilon_{\mathrm{small}})}_{\textup{Junta
complexity of $f$}}}_{\textup{for small error}}.$

In words, $g\circ f$ requires much larger junta approximators, an $\Omega(k)$
multiplicative factor more, even if we allow much larger error,
$\frac{1}{2}(1-\sqrt{\tau})\eqqcolon\varepsilon_{\mathrm{large}}$ instead of
$\varepsilon_{\mathrm{small}}$. As two extreme examples of combining functions
$g$,

  * $\circ$

The $(0.001,\varepsilon_{\mathrm{small}})$-noise stability of the $k$-variable
Parity function is $(1-2\cdot\varepsilon_{\mathrm{small}})^{\Omega(k)}$,
making it an excellent amplifier of junta complexity.

  * $\circ$

The $(0.001,\varepsilon_{\mathrm{small}})$-noise stability of a dictator
function $g(x)=x_{i}$ is $1$, making it a terrible amplifier of junta
complexity as one would expect: if $g$ is a dictator function then $g\circ
f\equiv f$ is of course no more complex than $f$ itself.

The partial-noise stability of these two specific examples are straightforward
to compute, but the calculations quickly become unwieldy even for other basic
functions. In addition to being a quantity of independent technical interest,
the upcoming connections between strong composition theorems and the boosting
of property testers will also motivate understanding the partial-noise
stability of broad classes of functions beyond just parity and dictator.
(Roughly speaking, to boost testers for a property $\mathcal{P}$ we need to
analyze a function $g$ such that $\mathcal{P}$ is closed under $g$.)

Our next result is a general technique that yields sharp bounds on the
partial-noise stability, and more generally the multivariate noise stability,
of all symmetric functions.

##### The multivariate noise sensitivity of symmetric functions.

For a symmetric function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ one intuits that
its multivariate noise stability at a vector $\vec{\rho}\in[0,1]^{k}$ should
be related to its univariate noise stability at a value $\rho^{\star}\in[0,1]$
that is an “average” of the coordinates of $\vec{\rho}$. (This is certainly
not true for general functions; consider for example the dictator function.)
Using techniques from the study of negative association, we formalize this
intuition and prove that indeed it is sandwiched by the arithmetic and
geometric means of the coordinates of $\vec{\rho}$:

######  Lemma 2.2 (Multivariate and univariate noise stabilities of symmetric
functions).

Let $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ be a symmetric function, $\mu\in(-1,1)$,
and $\vec{\rho}\in[0,1]^{k}$. Define

$\rho^{(\mathrm{GM})}\coloneqq\Bigg{(}\prod_{i\in[k]}\vec{\rho}_{i}\Bigg{)}^{1/k}\quad\text{and}\quad\
\ \rho^{(\mathrm{AM})}\coloneqq\frac{1}{k}\sum_{i\in[k]}\vec{\rho}_{i}.$

Then

$\mathrm{Stab}_{\mu,\rho^{(\mathrm{GM})}}(g)\leq\mathrm{Stab}_{\mu,\vec{\rho}}(g)\leq\mathrm{Stab}_{\mu,\rho^{(\mathrm{AM})}}(g).$

Furthermore, the lower bound holds under the weaker assumption that $g$ is
transitive.

The more “reasonable” $\vec{\rho}$ is, the closer the upper and lower bounds
of Lemma 2.2 are. In particular, we get the following bound on the
$(\delta,\varepsilon)$-noise stability of symmetric functions:

######  Corollary 2.3 (The $(\delta,\varepsilon)$-noise stability of symmetric
functions; informal).

For any symmetric function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$,
$\delta\in(0,1)$, and $\varepsilon\in(0,1/2)$, the
$(\delta,\varepsilon)$-noise stability of $g$ is equal to
$\mathrm{Stab}_{\mu,\rho^{\star}}(g)$ for some $\rho^{\star}\in[0,1]$
satisfying

$1-2\delta\varepsilon-O(\varepsilon^{2})\leq\rho^{\star}\leq
1-2\delta\varepsilon.$

Recall that $\varepsilon$ corresponds to the initial inapproximability factor
$\varepsilon_{\mathrm{small}}$ in Corollary 2.1, and so the additive gap of
$O(\varepsilon^{2})$ between the upper and lower bounds is indeed small for
our intended application.

###  2.2 Second main result: Composition theorems and boosting of property
testers

Composition theorems are most naturally thought of as statements about
hardness amplification, and indeed that is how they are most commonly used. As
our second main contribution, we show how they can be used fruitfully in their
contrapositive form as meta-algorithms. In more detail, we show how they can
be used to generically boost the performance guarantees of property testers.
While boosting is a story of success in both the theory and practice of
machine learning, to our knowledge the analogous concept in property testing
has not yet been considered. The connection that we draw can be instantiated
with either strong or weak composition theorems, but as we now see, the
parameters are qualitatively better in case of strong composition theorems.

Within property testing, a major strand of research, initiated by Parnas, Ron,
and Samorodnitsky [PRS02], concerns testing whether an unknown function has a
concise representation. Consider any parameterized property
$\mathcal{P}=\\{\mathcal{P}_{s}\\}_{s\in\mathbb{N}}$ of boolean functions:
size-$s$ parities, size-$s$ juntas, size-$s$ decision trees, $s$-sparse
polynomials over various fields, and so on. The task is as follows:

######  Definition 4 ($(\varepsilon,s,s^{\prime})$-testing of $\mathcal{P}$
under $\mathcal{D}$).

Given queries to an unknown function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, access
to i.i.d. draws from a distribution $\mathcal{D}$, and parameters
$s,s^{\prime}\in\mathds{N}$ and $\varepsilon>0$, distinguish between:

  * $\circ$

Yes: $f\in\mathcal{P}_{s}$

  * $\circ$

No: $f$ is $\varepsilon$-far under $\mathcal{D}$ from every function in
$\mathcal{P}_{s^{\prime}}$.

Note that the task is more challenging as $\varepsilon$ gets smaller, and as
the gap between $s$ and $s^{\prime}$ gets smaller. We show how a composition
theorem for $\mathcal{P}$ allows one to trade off these two parameters: a
tester for large $\varepsilon$ can be upgraded into one for small
$\varepsilon$, at the price of larger gap between $s$ and $s^{\prime}$. The
stronger the composition theorem, the more favorable this tradeoff is, and
with an optimally strong composition theorem one is able to improve the
$\varepsilon$-dependence without any associated price in the multiplicative
gap between $s$ and $s^{\prime}$:

######  Theorem 2 (Composition theorems yield boosters for testers; informal).

Let $\mathcal{P}=\\{\mathcal{P}_{s}\\}_{s\in\mathds{N}}$ be a property and
$g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ be such that $\mathcal{P}$ behaves linearly
w.r.t. $g$. Suppose that $\mathcal{P}$ admits an
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem w.r.t. $g$. Then any $(\varepsilon_{\mathrm{large}},ks,\lambda
ks^{\prime})$-tester for $\mathcal{P}$ can be converted in to an
$(\varepsilon_{\mathrm{small}},s,s^{\prime})$-tester for $\mathcal{P}$.

We defer the precise definitions of the terms
“$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem” and “behaves linearly” to the body of the paper, mentioning for now
that $\lambda\in[0,1]$ measures the strength of the composition theorem: such
a theorem says that the composed function requires $\lambda k$ more resources
to achieve $\varepsilon_{\mathrm{large}}$ error than original function to
achieve $\varepsilon_{\mathrm{small}}$ error. Therefore $\lambda=\frac{1}{k}$
can be viewed as the threshold separating weak and strong composition
theorems, with $\lambda=1$ corresponding to an optimally strong one.
(Corollary 2.1, for example, achieves $\lambda=0.99$.) Note that if
$\lambda=1$ in Theorem 2, then an $(\varepsilon_{\mathrm{large}},s,s)$-tester
for all $s$ yields an $(\varepsilon_{\mathrm{small}},s,s)$-tester for all $s$.

The formal version of Theorem 2 will also show that it upgrades uniform-
distribution testers to strong uniform-distribution testers, and distribution-
free testers to strong distribution-free testers. This stands in contrast to
standard boosting in learning which can only upgrade distribution-free
learners.

####  2.2.1 Example applications of Theorem 2: New implications for junta
testing

As mentioned in the introduction, juntas are among the most basic and
intensively-studied function classes in property testing. Owing to two decades
of research, the complexity of testing juntas in the non-tolerant setting is
now fairly well-understood: we have highly-efficient adaptive [Bla09], non-
adaptive [Bla08], and distribution-free testers [LCS+18, Bsh19], all of them
achieving query complexities that are essentially optimal [CG04, Bla08, STW15,
CST+18].

The picture is much less clear in the more challenging tolerant setting. For
the uniform distribution, the best known testers require exponentially many
queries [BCE+18, ITW21], and there are no known distribution-free testers. By
generalization Theorem 2 to the tolerant setting and instantiating it with our
strong composition theorem for juntas, we obtain new implications, both
positive and negative, that help clarify this picture.

##### Positive implication: boosting of tolerant junta testers.

First, any tolerant junta tester for large distance parameter can now be
converted into one for small distance parameters, at the price of a slight gap
in the junta sizes of the Yes and No cases. For example, for both the uniform
and distribution-free settings we get:

######  Corollary 2.4 (Boosting of tolerant junta testers; special case).

Suppose we have a $\mathrm{poly}(r)$-query tester that distinguishes between

  * $\circ$

Yes: $f$ is $\frac{1}{4}$-close to an $r$-junta

  * $\circ$

No: $f$ is $\frac{1}{3}$-far from every $r$-junta.

Then for every $\varepsilon>0$ we have a $\mathrm{poly}(r/\varepsilon)$-query
tester that distinguishes between

  * $\circ$

Yes: $f$ is $\varepsilon$-close to an $r$-junta

  * $\circ$

No: $f$ is $\Omega(\varepsilon)$-far from every $1.001r$-junta.

The resulting gap between the junta sizes of the Yes and No cases, while mild,
is admittedly not ideal. As alluded to above, this stems from the fact that
the “strength parameter” of Corollary 2.1 is $\lambda=0.99$ and not
$\lambda=1$. Designing boosters that do not incur this gap, either via an
optimally strong composition theorem or otherwise, is a natural avenue for
future work.

On the other hand, we now show that even with this gap, Corollary 2.4 already
carries with it an interesting consequence. This consequence crucially relies
on our composition theorem for juntas being strong; the proof would not have
gone through had the strength parameter of Corollary 2.1 only been
$\lambda=\frac{1}{k}$.

##### Negative implication: NP-hardness in the distribution-free setting.

This implication concerns the time rather than query complexity of testers.
The same proof of Corollary 2.4 also converts a $\mathrm{poly}(r,n)$-time
tester into a $\mathrm{poly}(r,1/\varepsilon,n)$-time tester. Implicit in the
work of Hancock, Jiang, Li, and Tromp [HJLT96] is an NP-hardness result for
tolerantly testing juntas in the distribution-free setting. One downside of
their result is that it only holds in the regime of
$\varepsilon=1/\mathrm{poly}(n)$. Applying the time-analogue of Corollary 2.4,
we lift this hardness up to the standard regime of constant $\varepsilon$:

######  Corollary 2.5 (NP-hardness in the distribution-free testing).

The following task is NP-hard under randomized reductions. Given queries to a
function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, access to i.i.d. draws from a
distribution $\mathcal{D}$, and parameters $r\in\mathds{N}$ and
$\varepsilon>0$, distinguish between:

  * $\circ$

Yes: $f$ is $\frac{1}{4}$-close under $\mathcal{D}$ to an $r$-junta;

  * $\circ$

No: $f$ is $\frac{1}{3}$-far under $\mathcal{D}$ from every $r$-junta.

This implies a fairly dramatic separation between the non-tolerant versus
tolerant versions of the problem. The recent $\mathrm{poly}(r)$-query non-
tolerant testers [LCS+18, Bsh19] are also time efficient, running in
$\mathrm{poly}(r,n)$ time. Corollary 2.5 shows that any tolerant tester,
regardless of query efficiency, must have time complexity that is as bad as
that of SAT: e.g. if SAT requires randomized exponential time, then so does
any tolerant tester.

In fact, our actual result is stronger than as stated in Corollary 2.5: we
prove that the task is NP-hard even if the Yes case states that $f$ is 0-close
under $\mathcal{D}$ to an $r$-junta. We therefore show that the testers of
[LCS+18, Bsh19] are quite fragile in the sense that they break if the Yes case
in the definition of non-tolerant testing is changed from “$f$ is an
$r$-junta” to “$f$ is $0$-close under $\mathcal{D}$ to an $r$-junta”.

##  3 Other related work

##### O’Donnell’s generalization of Yao’s XOR lemma.

Yao’s XOR lemma states that if $f$ is $\varepsilon$-hard against circuits of
size $s$, meaning every size-$s$ circuit differs from $f$ on at least an
$\varepsilon$-fraction of inputs, then $\mathrm{XOR}_{k}\circ f$ is
$(\frac{1}{2}+\frac{1}{2}(1-2\varepsilon)^{k}+\delta)$-hard against circuits
of size $s^{\prime}$ where

$s^{\prime}=\Theta\bigg{(}\frac{\delta^{2}}{\log(1/\varepsilon)}\bigg{)}\cdot
s.$

The $(1-2\varepsilon)^{k}$ term in the resulting inapproximability factor
agrees precisely with the (univariate) noise stability of $\mathrm{XOR}_{k}$
at $\rho=1-2\varepsilon$. In [O’D02] O’Donnell showed that this is no
coincidence. He proved a far-reaching generalization of Yao’s XOR lemma that
allows for an arbitrary combining function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$
instead of XOR, and showed that the resulting inapproximability of $g\circ f$
is given by the “expected bias” of $g$, a quantity that is closely related to
the (univariate) noise stability of $g$.

Like Yao’s XOR lemma, [O’D02]’s composition theorem is weak in the sense that
the hardness of $g\circ f$ only holds against size $s^{\prime}$ circuits where
$s^{\prime}\ll s$. (In fact, [O’D02] incurs an additional multiplicative loss
of $k$ in the resulting circuit size.) Our composition theorem concerns a
different resource, juntas instead of circuits, and as emphasized in the
introduction, our main focus is on proving a composition theorem that is
strong in the sense of amplifying both the amount of resource required and the
inapproximability factor.

Both our work and [O’D02] utilize Fourier analysis in our proofs, which is to
be expected given the centrality of noise stability to both works. That aside,
our overall approach and techniques are entirely different from
[O’D02]’s—necessarily so, as we elaborate next.

##### Hardness amplification via boosting.

In [KS03] Klivans and Servedio observed that most known hardness amplification
results are proved via a boosting-type argument. For example, for Yao’s XOR
lemma and [O’D02]’s generalization of it, one proceeds by contradiction: one
assumes that $\mathrm{XOR}_{k}\circ f$ can be mildly approximated by a
size-$s^{\prime}$ circuit $C$ (in the language of boosting, $C$ is a weak
hypothesis for $\mathrm{XOR}_{k}\circ f$), and one constructs a larger circuit
$C^{\star}$ of size $s$ that well-approximates $f$ (i.e. $C^{\star}$ is a
strong hypothesis for $f$). In boosting, the strong hypothesis is built out of
many weak hypotheses; likewise, in Yao’s XOR lemma the size-$s$ circuit
$C^{\star}$ is built out of many size-$s^{\prime}$ circuits that are like $C$.
The work of [KS03] formalizes this connection.

From this perspective, it becomes clear why such approaches are fundamentally
limited to weak composition theorems where $s^{\prime}\ll s$. Strong
composition theorems therefore necessitate a different tack, and indeed our
proof proceeds via the forward implication instead of the contrapositive: we
reason directly about the inapproximability of $g\circ f$ under the assumption
about the inapproximability of $f$. Somewhat ironically, our second main
contribution is then an application of strong composition theorems to the
boosting of property testers, which goes in the opposite direction to [KS03]’s
“Boosting $\Rightarrow$ Hardness Amplification” observation above.

##### Independent work of Chen and Patel [CP23].

A recent work of Chen and Patel also gives new lower bounds for tolerant junta
testing. For the problem of testing whether an unknown function is
$\varepsilon_{1}$-close to or $\varepsilon_{2}$-far from a $k$-junta under the
uniform distribution, they prove a query lower bound of
$k^{\Omega(\log(1/(\varepsilon_{2}-\varepsilon_{1})))}$, which is
superpolynomial when the gap $\varepsilon_{2}-\varepsilon_{1}$ is subconstant.
This yields the first superpolynomial query complexity separation between
tolerant and non-tolerant testing for a natural property of boolean functions.

Their result is incomparable to Corollary 2.5 in several respects. We give a
time lower bound when the gap $\varepsilon_{2}-\varepsilon_{1}$ is a fixed
constant in the distribution-free setting. Being an NP-hardness result, our
lower bound is conditional whereas theirs is unconditional.

##  4 Discussion and future work

Complexity measures can behave in highly counterintuitive ways under
composition, which makes composition theorems, and strong composition theorems
in particular, tricky to prove. A motivating goal of this work is to develop
an understanding of strong composition theorems from first principles, and
hence our focus on junta complexity, perhaps the most basic complexity measure
of a function. We are optimistic that our techniques can apply to other
measures, though we believe that as in this work, much of the challenge will
lie in first figuring out the right statement to prove.

Consider for example decision tree complexity, a natural next step from junta
complexity. There are existing strong XOR lemmas for decision tree complexity,
but they come with limitations and do not appear to be the final word.
(Briefly, the XOR lemma of [Dru12] is only strong when the initial
inapproximability factor $\varepsilon_{\mathrm{small}}$ is at least a
constant, and the strong XOR lemma of [BB19, BKLS20] only holds for decision
trees that are allowed to “abort”.) Indeed, Shaltiel [Sha04] has shown that
certain hoped-for strong XOR lemmas for decision tree complexity are false,
though as he remarked, his counterexample “seems to exploit defects in the
formation of the problem rather than show that our general intuition for
direct product assertions is false”. We hope that our results, and
specifically the new connections to various notions of noise stability, can
serve as a guide to the right statement for decision tree complexity and other
measures.

As for our second main result, the general connection between strong
composition theorems and the boosting of property testers, we believe that it
adds compelling algorithmic motivation to the study of composition theorems, a
topic traditionally considered to be mostly of complexity-theoretic interest.
Likewise, we hope that our work spurs future research on this new notion of
boosting for property testers, a notion that we believe is of interest
independent of the connections to composition theorems. For example, an
ambitious goal for future work is to broadly understand when and how a tester
for constant distance parameter $\varepsilon$ can be automatically upgraded
into one with the optimal $\varepsilon$-dependence, as well as the associated
costs of such a transformation.

##  5 Preliminaries

Distributions and random variables. We use bold font (e.g
$\bm{x}\sim\mathcal{D}$) to denote random variables. For any set $S$, we use
$\bm{x}\sim S$ as shorthand for $\bm{x}\sim\mathrm{Unif}(S)$ where
$\mathrm{Unif}(\cdot)$ denotes the uniform distribution. Of particular
importance to this work will be $\mu$-biased distributions over the Boolean
hypercube.

######  Definition 5 ($\mu$-biased distribution).

For any $\mu\in(-1,1)$, we use $\pi_{\mu}$ to denote the unique distribution
over $\\{\pm 1\\}$ with mean $\mu$. Formally, for $\bm{y}\sim\pi_{\mu}$,

$\bm{y}=\begin{cases}1&\text{with probability }\frac{1+\mu}{2}\\\
-1&\text{with probability }\frac{1-\mu}{2}.\end{cases}$

Similarly, for ${\vec{\rho}}\in[-1,1]^{k}$, we use $\pi_{\vec{\rho}}$ to
denote the product distribution
$\pi_{\vec{\rho}_{1}}\times\cdots\times\pi_{\vec{\rho}_{k}}$.

######  Definition 6 ($\vec{\rho}$-correlated).

Fix some bias $\mu\in(-1,1)$. For any $\vec{\rho}\in[0,1]^{k}$ and $y\in\\{\pm
1\\}^{k}$, we write $\bm{z}\overset{\vec{\rho}}{\sim}y$ to denote that for
each $i\in[k]$, $\bm{z}_{i}$ is independently drawn as

$\bm{z}_{i}=\begin{cases}y_{i}&\text{with probability }\vec{\rho}_{i}\\\
\text{Drawn from $\pi_{\mu}$}&\text{with probability
}1-\vec{\rho}_{i}.\end{cases}$

Whenever we use the above notation, the choice of $\mu$ will be clear from
context. This gives the following more succinct way to express Definition 2,
defining multivariate noise stability,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k},\bm{z}\overset{\vec{\rho}}{\sim}\bm{y}}[g(\bm{y})g(\bm{z})].$

Some useful sets. For any integers $a\leq b$, we use $[a,b]$ as shorthand for
the set $\\{a,a+1,\ldots,b\\}$. Similarly, for $b\geq 1$, we use $[b]$ as
shorthand for the set $[1,b]$. For any set $S$ and $\ell\leq|S|$, we use
$\binom{S}{\ell}$ to denote all subsets of $S$ with cardinality $\ell$.

Junta complexity. For any function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, and
$S\subseteq[n]$, we say that $f$ is an $S$-junta if for all $x,y\in\\{\pm
1\\}^{n}$ for which $x_{i}=y_{i}$ whenever $i\in S$ it holds that $f(x)=f(y)$.
With a slight abuse of notation, when $r\in[n]$ is an integer, we say that $f$
is an $r$-junta if there is a set $|S|\leq r$ for which $f$ is an $r$-junta.

Advantage. For any functions $f,g:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and
distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$, we define

$\mathrm{Adv}_{\mathcal{D}}(f,g)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})g(\bm{x})].$

With a slight abuse of notation, we define for $f:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ and $S\subseteq[n]$,

$\mathrm{Adv}_{\mathcal{D}}(f,S)\coloneqq\max_{S\text{-junta }g:\\{\pm
1\\}^{n}\to\\{\pm 1\\}}\mathrm{Adv}_{\mathcal{D}}(f,g).$

Similarly, for $r\in[n]$,

$\mathrm{Adv}_{\mathcal{D}}(f,r)\coloneqq\max_{r\text{-junta }g:\\{\pm
1\\}^{n}\to\\{\pm 1\\}}\mathrm{Adv}_{\mathcal{D}}(f,g).$

When the base distribution $\mathcal{D}$ is clear, we will drop it from our
notation. Furthermore, for any function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and
$S\subseteq[n]$ or $r\in[n]$, we use $\tilde{f}_{S}$ and $\tilde{f}_{r}$ to
denote the $S$-junta and $r$-junta respectively maximizing the above two
advantages.

Function composition. For a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, its
direct product $f^{\otimes k}:\left(\\{\pm 1\\}^{n}\right)^{k}\to\\{\pm
1\\}^{k}$ is defined as

$f^{\otimes k}(x^{(1)},\ldots,x^{(k)})=(f(x^{(1)}),\ldots,f(x^{(k)})).$

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, we use $g\circ f:\left(\\{\pm
1\\}^{n}\right)^{k}\to\\{\pm 1\\}$ as shorthand for $g\circ f^{\otimes k}$,
meaning,

$(g\circ f)(x^{(1)},\ldots,x^{(k)})=g(f(x^{(1)}),\ldots,f(x^{(k)})).$

Vector powers. For any vector $v\in\mathds{R}^{k}$ and set $S\subseteq[k]$,
we’ll use the notation $v^{S}$ as shorthand for

$v^{S}\coloneqq\prod_{i\in S}v_{i}.$

###  5.1 Fourier Analysis

Our proof of Theorem 1 will make heavy use of Fourier analysis over the
$\mu$-biased hypercube, $(\pi_{\mu})^{k}$. In this section, we will review
relevant definitions and facts. A more complete exposition is given in
[O’D14].

For any $\mu\in(-1,1)$, we define $\phi_{\mu}(x)\coloneqq\frac{x-\mu}{\sigma}$
where $\sigma\coloneqq\sqrt{1-\mu^{2}}$. Every $g:\\{\pm
1\\}^{k}\to\mathds{R}$ can be uniquely decomposed as

$g(y)=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\prod_{i\in
S}\phi_{\mu}(y_{i})\quad\quad\text{where}\quad\quad\hat{g}_{\mu}(S)=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}\left[g(\bm{y})\prod_{i\in
S}\phi_{\mu}(\bm{y}_{i})\right].$

This decomposition has a number of useful properties stemming from the fact
that transforming $g$ from its representation as a truth table to its Fourier
coefficients $\hat{g}_{\mu}(S)$ is an orthonormal transformation.

######  Fact 5.1 (Basic facts about the Fourier decomposition).

  1. 1.

Plancherel’s theorem: For any $g,h:\\{\pm 1\\}^{k}\to\mathds{R}$ and
$\mu\in(-1,1)$,

$\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}[g(\bm{y})h(\bm{y})]=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\hat{h}_{\mu}(S).$

  2. 2.

Parseval’s theorem: For any $g:\\{\pm 1\\}^{k}\to\mathds{R}$ and
$\mu\in(-1,1)$,

$\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}[g(\bm{y})^{2}]=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)^{2}.$

In particular, when $g$ has a range of $\\{\pm 1\\}$, Parseval’s theorem
guarantees that the sum of its squared Fourier coefficients is $1$. As a
result, the following distribution is well defined.

######  Definition 7 (Spectral sample).

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ and bias $\mu\in(-1,1)$, the
_spectral sample_ of $g$, denoted $\mathcal{S}_{\mu}(g)$, is the probably
distribution over subsets of $[k]$ in which the set $S$ has probability
$\hat{g}_{\mu}(S)^{2}$.

The Fourier decomposition gives a concise way to represent important
quantities, as in the following results.

######  Proposition 5.2 (Multivariate noise stability from the Fourier
spectrum.).

For any $\mu\in(-1,1)$ and $\vec{\rho}\in[0,1]^{k}$,
$\mathrm{Stab}_{\mu,\vec{\rho}}$ can be related to $g$’s $\mu$-biased Fourier
decomposition as,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\sum_{S\subseteq[k]}\hat{g}(S)^{2}\vec{\rho}^{S}=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}[(\vec{\rho})^{\bm{S}}].$

###### Proof.

We define
$g^{(\vec{\rho})}(y)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{z}\overset{\vec{\rho}}{\sim}y}[g(\bm{z})]$.
Then, by Plancherel’s theorem,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}[g(\bm{y})g^{(\vec{\rho})}(\bm{y})]=\sum_{S\subseteq[k]}\widehat{g}_{\mu}(S)\widehat{g^{(\vec{\rho})}}_{\mu}(S).$

Next, we compute the Fourier decomposition of $g^{(\vec{\rho})}$.

$\displaystyle\widehat{g^{(\vec{\rho})}}_{\mu}(S)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}\left[g^{(\vec{\rho})}(\bm{y})\prod_{i\in
S}\phi_{\mu}(\bm{y}_{i})\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k},\bm{z}\overset{\vec{\rho}}{\sim}\bm{x}}\left[g(\bm{z})\prod_{i\in
S}\phi_{\mu}(\bm{y}_{i})\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k},\bm{z}\overset{\vec{\rho}}{\sim}\bm{x}}\left[g(\bm{y})\prod_{i\in
S}\phi_{\mu}(\bm{z}_{i})\right]$ ($(\bm{y},\bm{z})$ distributed identically to
$(\bm{z},\bm{y})$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}\left[g(\bm{y})\cdot\mathop{{\mathds{E}}\/}_{\bm{z}\overset{\vec{\rho}}{\sim}\bm{y}}\left[\prod_{i\in
S}\phi_{\mu}(\bm{z}_{i})\right]\right].$

Applying the independence of $\bm{z}_{1},\ldots,\bm{z}_{k}$ conditioned on
$\bm{y}$ and that
$\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{z}_{i})]=\vec{\rho}_{i}\phi_{\mu}(\bm{y}_{i})$,

$\displaystyle\widehat{g^{(\vec{\rho})}}_{\mu}(S)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}\left[g(\bm{y})\cdot\prod_{i\in
S}\vec{\rho}_{i}\phi_{\mu}(\bm{y}_{i})\right]$
$\displaystyle=(\vec{\rho})^{S}\cdot\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k}}\left[g(\bm{y})\cdot\prod_{i\in
S}\phi_{\mu}(\bm{y}_{i})\right]=(\vec{\rho})^{S}\widehat{g}_{\mu}(S).$

Putting the above together,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)^{2}(\vec{\rho})^{S}.\qed$

One immediate corollary of the above is that multivariate noise stability is
monotone.

######  Corollary 5.3 (Multivariate noise stability is monotone).

For any $\mu\in(-1,1)$, $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, and
$\vec{\rho},\vec{\rho^{\prime}}\in[0,1]^{k}$ satisfying
$\vec{\rho}_{i}\leq\vec{\rho^{\prime}}_{i}$ for all $i\in[k]$,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)\leq\mathrm{Stab}_{\mu,\vec{\rho^{\prime}}}(g).$

Recall that for any $\nu\in[-1,1]^{k}$, the distribution $\pi_{\nu}$ is the
unique product distribution supported on $\\{\pm 1\\}^{k}$ with mean $\nu$.
The Fourier decomposition of $g$ also gives a useful way to compute
$\mathop{{\mathds{E}}\/}_{\bm{y}\sim\pi_{\nu}}[g(\bm{y})]$.

######  Fact 5.4.

For any $g:\\{\pm 1\\}^{k}\to\mathds{R}$, $\mu\in(-1,1)$, and
$\nu\in[-1,1]^{k}$,

$\mathop{{\mathds{E}}\/}_{\bm{y}\sim\pi_{\nu}}[g(\bm{y})]=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\prod_{i\in
S}\phi_{\mu}(\nu_{i}).$

###### Proof.

We expand $g$ into it’s Fourier decomposition

$\displaystyle\mathop{{\mathds{E}}\/}[g(\bm{y})]$
$\displaystyle=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\mathop{{\mathds{E}}\/}\left[\prod_{i\in
S}\phi_{\mu}(\bm{y}_{i})\right]$ (Linearity of expectation)
$\displaystyle=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\prod_{i\in
S}\mathop{{\mathds{E}}\/}\left[\phi_{\mu}(\bm{y}_{i})\right]$
($\bm{y}_{1},\ldots,\bm{y}_{k}$ are independent)
$\displaystyle=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\prod_{i\in
S}\mathop{{\mathds{E}}\/}\left[\frac{\bm{y}_{i}-\mu}{\sigma}\right]$
(Definition of $\phi_{\mu}$)
$\displaystyle=\sum_{S\subseteq[k]}\hat{g}_{\mu}(S)\prod_{i\in
S}\phi_{\mu}(\nu_{i}).$ (Linearity of expectation)

∎

##  6 A strong composition theorem for juntas

In this section, we characterize the junta size required to approximate
$g\circ f$ in terms of the _multivariate noise stability_ of $g$, and the
junta size required to approximate $f$.

######  Theorem 3 (A strong composition theorem for junta complexity,
generalization of Theorem 1).

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$
and base distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$, let
$\mu=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})]$.

  1. 1.

Lower bound on advantage: For any approximators $q^{(1)},\ldots,q^{(k)}:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$, define the _lower normalized correlations_ , for each
$i\in[k]$ as

$\alpha_{i}\coloneqq\max\left(0,\frac{\mathrm{Adv}_{\mathcal{D}}(f,q^{(i)})^{2}-\mu^{2}}{1-\mu^{2}}\right).$

Then, there is an $h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ for which

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,h(q^{(1)},\ldots,q^{(k)}))\geq\mathrm{Stab}_{\mu,\alpha}(g).$

  2. 2.

Upper bound on advantage: For any $S_{1},\ldots,S_{k}$, define the _upper
normalized correlation_ as

$\beta_{i}\coloneqq\max\left(0,\frac{\mathrm{Adv}_{\mathcal{D}}(f,S_{i})-\mu^{2}}{1-\mu^{2}}\right),$

construct $S\subseteq[n]\times[k]$ by taking $S_{1}$ from the first block,
$S_{2}$ from the second block, and so on (formally
$S\coloneqq\cup_{i\in[k],j\in S_{i}}\\{(j,i)\\}$). Then,

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,S)\leq\sqrt{\mathrm{Stab}_{\mu,\beta}(g)}.$

Our goal is to understand the error of the best $R$-junta approximating
$g\circ f$. Theorem 3 says that for _any_ way to partition $R=r_{1}+\cdots
r_{k}$, the approximator $h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}})$
achieves nearly optimal advantage across all $R$-juntas that partition their
budget this way. Of course, by maximizing both sides across all partitions, we
can conclude that there is some partitioning and function $h$ for which
$h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}})$ has nearly optimal advantage
among all $R$-juntas. Indeed, as a simple corollary of Theorem 3, we can show
that the _error_ of the optimal canonical composed form approximator is within
a factor of $4$ of the optimal approximator. Recall that
$\mathrm{error}_{\mathcal{D}}(q_{1},q_{2})=\operatorname{{Pr}}_{\bm{x}\sim\mathcal{D}}[q_{1}(\bm{x})\neq
q_{2}(\bm{x})]$ and is related to advantage via the equality
$\mathrm{Adv}=1-2\cdot\mathrm{error}$.

######  Corollary 6.1 (Canonical composed form achieves nearly optimal error).

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\},f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
junta budget $R$, and base distribution $\mathcal{D}$, there is an $h:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ and partition of the budget $r_{1}+\cdots+r_{k}=R$ for
which,.

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ
f,h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}))\leq
4\cdot\mathrm{error}_{\mathcal{D}^{k}}(g\circ f,R).$

When $\mu=0$, the guarantee of Theorem 3 can further be given in the concise
form of Theorem 1: For an appropriately chosen $\vec{\rho}\in[0,1]^{k}$,

$\displaystyle\mathrm{Stab}_{\vec{\rho}}(g)^{2}$
$\displaystyle\leq\textnormal{Advantage of optimal canonical composed form
approximator}$ $\displaystyle\leq\textnormal{Advantage of optimal
approximator}\leq\sqrt{\mathrm{Stab}_{\vec{\rho}}(g)}.$

We include the proofs of Corollary 6.1 and Theorem 1 in Section 6.3.

###  6.1 Proof of the lower bound on advantage

In this subsection, we show that $(x_{1},\ldots,x_{k})\to
h(\tilde{f}_{r_{1}}(x_{1}),\ldots,\tilde{f}_{r_{k}}(x_{k}))$ is close to the
best $R$-junta approximator for $g\circ f$. Here, the function $h$ can be
different than $g$, and this is necessary as shown in the counterexample to
conjecture 2 in Section 2.1.1.

######  Lemma 6.2 (Part 1 of Theorem 3: Lower bound on advantage).

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
and approximators $q^{(1)},\ldots,q^{(k)}$, there is some $h:\\{\pm
1\\}^{k}\to\\{\pm 1\\}$ for which

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,h\circ(q^{(1)},\ldots,q^{(k)}))\geq\mathrm{Stab}_{\mu,\alpha}(g),$

where $\mu=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})]$ and for
each $i\in[k]$,

$\alpha_{i}\coloneqq\max\left(0,\frac{\mathrm{Adv}(f,q^{(i)})^{2}-\mu^{2}}{1-\mu^{2}}\right).$

Note $\alpha_{i}$ naturally interpolates between $0$ and $1$. Setting
$q^{(i)}$ to the better of the constant $-1$ or the constant $+1$ function
will lead to $\alpha_{i}=0$, while setting $q^{(i)}=f$ gives $\alpha_{i}=1$.

####  6.1.1 Characterizing the advantage of composed form approximators

To ease notation, we begin with a simpler setting. Suppose we use the same
budget, $r\coloneqq R/k$, in each of the $k$ pieces. Our goal is to understand

$\max_{h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}}\mathrm{Adv}(g\circ
f,h\circ\tilde{f}_{r})$

in terms of the noise sensitivity of $g$ and $\mathrm{Adv}(f,\tilde{f}_{r})$.
To do so, we will consider _unbalanced_ noise stability.

######  Definition 8 (Unbalanced noise stability).

For any $x\in\\{\pm 1\\}^{k}$, we use the notation
$\bm{y}\overset{a,b}{\sim}x$ to denote that for each $i\in[k]$, $\bm{y}_{i}$
is independently drawn as

  1. 1.

If $x_{i}=-1$, with probability $a$, we set $\bm{y}_{i}=x_{i}$ and otherwise
set $\bm{y}_{i}=-x_{i}$

  2. 2.

If $x_{i}=1$, with probability $b$, we set $\bm{y}_{i}=x_{i}$ and otherwise
set $\bm{y}_{i}=-x_{i}$.

For any $g,h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $\mu\in[-1,1]$ and $a,b\in[0,1]$,
we define the _unbalanced_ noise stability as

$\mathrm{UnbalStab}_{\mu,(a,b)}(g,h)=\mathop{{\mathds{E}}\/}_{\bm{x}\sim(\pi_{\mu})^{k},\bm{y}\overset{a,b}{\sim}\bm{x}}[g(\bm{x})h(\bm{y})].$

We refer to the above notion as _unbalanced_ because when drawing
$\bm{y}\overset{a,b}{\sim}x$, the probability of the $i^{\text{th}}$
coordinate flipping from $-1$ to $1$ and from $1$ to $-1$ may differ.
Unbalanced noise stability is useful in our setting due to the following
proposition.

######  Proposition 6.3.

For any $f,\tilde{f}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and $g,h:\\{\pm
1\\}^{k}\to\\{\pm 1\\}$,

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}[(g\circ
f)(\bm{x})\cdot(h\circ\tilde{f})(\bm{x})]=\mathrm{UnbalStab}_{\mu,(a,b)}(g,h),$

where

$\mu\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})],\quad\quad
a\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[\tilde{f}(\bm{x})=-1\mid
f(\bm{x})=-1],\quad\quad
b\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[\tilde{f}(\bm{x})=1\mid
f(\bm{x})=1].$

###### Proof.

Draw $\bm{x}\sim\mathcal{D}^{k}$ and then define $\bm{y}\coloneqq f^{\otimes
k}(\bm{x}),\tilde{\bm{y}}\coloneqq\tilde{f}^{\otimes k}(\bm{x})$. Clearly,

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}[(g\circ
f)(\bm{x})\cdot(h\circ\tilde{f})(\bm{x})]=\mathop{{\mathds{E}}\/}[g(\bm{y})h(\tilde{\bm{y}})].$

Furthermore, the distribution of $\bm{y},\tilde{\bm{y}}$ is equivalent to if
we drew $\bm{y}\sim(\pi_{\mu})^{k},\tilde{\bm{y}}\overset{a,b}{\sim}\bm{y}$.
The above quantity therefore matches the definition of
$\mathrm{UnbalStab}_{\mu,(a,b)}(g,h)$. ∎

####  6.1.2 Unbalanced noise stability behaves strangely

The most basic requirement of our approximation for $g\circ f$ is that it have
advantage at least $0$, as either the constant $-1$ or the constant $+1$
function is guaranteed to have such an advantage. Indeed, in the balanced
case, it is well known that the approximation will satisfy this basic
requirement even if we take $h=g$.

######  Fact 6.4.

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ and $a\in[0,1/2]$,

$\mathrm{UnbalStab}_{0,(a,a)}(g,g)\geq 0.$

However, in the unbalanced case, this basic requirement no longer holds.

######  Proposition 6.5.

For any $k\geq 0$, and $a,b\in[0,1]$ for which $|a-b|\geq 0.01$, there is a
function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ for which

$\mathrm{UnbalStab}_{0,(a,b)}(g,g)\leq-(1-2^{-\Omega(k)}).$

###### Proof.

Without loss of generality, we assume $b\geq a+0.01$. We define

$g(x)\coloneqq\begin{cases}1&\text{if }\sum_{i\in[k]}x_{i}\geq 0.005k,\\\
-1&\text{otherwise.}\end{cases}$

Draw $\bm{x}\sim(\pi_{\mu})^{k},\bm{y}\overset{a,b}{\sim}\bm{x}$. Then,

$\mathop{{\mathds{E}}\/}\left[\sum_{i\in[k]}\bm{x}_{i}\right]=0,\quad\quad\quad\quad\mathop{{\mathds{E}}\/}\left[\sum_{i\in[k]}\bm{y}_{i}\right]=k(b-a).$

Furthermore, a standard application of Hoeffding’s inequality implies that

$\mathop{{\operatorname{{Pr}}}\/}[g(\bm{x})=1]\leq
2^{-\Omega(k)},\quad\quad\quad\quad\mathop{{\operatorname{{Pr}}}\/}[g(\bm{y})=-1]\leq
2^{-\Omega(k)}.$

By union bound, with probability at least $2^{-\Omega(k)}$, we have that both
$g(\bm{x})=-1$ and $g(\bm{y})=1$. This implies the desired result. ∎

####  6.1.3 Unbalanced noise stability behaves well if we use the best $h$

Surprisingly, we show that if we use the best $h$, our approximation does meet
this most basic requirement. Furthermore, we can relate it to the classical
notion of _balanced_ noise stability. The below Lemma directly implies Lemma
6.2.

######  Lemma 6.6.

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ and distribution over
$\bm{x},\bm{y}$ each in $\\{\pm 1\\}^{k}$ satisfying,

  1. 1.

The pairs $(\bm{x}_{1},\bm{y}_{1}),\ldots,(\bm{x}_{k},\bm{y}_{k})$ are
independent of one another.

  2. 2.

The means satisfy
$\mathop{{\mathds{E}}\/}[\bm{x}_{1}]=\cdots=\mathop{{\mathds{E}}\/}[\bm{x}_{k}]=\mu$.

Define the correlations $\alpha_{1},\ldots,\alpha_{k}$ as

$\alpha_{i}\coloneqq\max\left(0,\frac{\mathop{{\mathds{E}}\/}[\bm{x}_{i}\bm{y}_{i}]^{2}-\mu^{2}}{1-\mu^{2}}\right).$

Then, there is an $h:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ for which

$\mathop{{\mathds{E}}\/}[g(\bm{x})h(\bm{y})]\geq\mathrm{Stab}_{\mu,\alpha}(g).$

Comparing to Proposition 6.5, if $\mu=0$, then $\alpha_{i}=\max(0,1-a-b)$ for
all $i\in[k]$. Since $\mathrm{Stab}_{\mu,\alpha}(g)\geq 0$ whenever
$\alpha\geq 0$, Lemma 6.6 shows that the phenomenon in Proposition 6.5 cannot
occur if we use the best approximator $h$.

The following Lemma will be useful in the proof of Lemma 6.6.

######  Lemma 6.7.

For any function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, let
$\bm{\nu}_{1},\ldots,\bm{\nu}_{k}$ be independent random variables each with
mean $\mu$ and supported on $[-1,1]$. Then,

$\mathop{{\mathds{E}}\/}_{\bm{\nu}}\left[\mathop{{\mathds{E}}\/}_{\bm{y}\sim\pi_{\bm{\nu}}}[g(\bm{y})]^{2}\right]=\mathrm{Stab}_{\mu,(\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu}_{1})^{2}],\ldots,\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu}_{k})^{2}])}(g).$

###### Proof.

We’ll use the $\mu$-biased Fourier expansion of $g$. Applying Fact 5.4,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{\nu}}\left[\mathop{{\mathds{E}}\/}_{\bm{y}\sim\pi_{\bm{\nu}}}[g(\bm{y})]^{2}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\nu}}\left[\left(\sum_{S\subseteq[k]}\hat{g}(S)\prod_{i\in
S}\phi_{\mu}(\bm{\nu}_{i})\right)^{2}\right]$
$\displaystyle=\sum_{S_{1},S_{2}\subseteq[k]}\hat{g}(S_{1})\hat{g}(S_{2})\mathop{{\mathds{E}}\/}\left[\prod_{i\in
S_{1}}\phi_{\mu}(\bm{\nu}_{i})\prod_{i\in
S_{2}}\phi_{\mu}(\bm{\nu}_{i})\right].$

We claim that, in the above sum, any term in which $S_{1}\neq S_{2}$ is equal
to $0$. Let $S_{1}\triangle S_{2}$ denote the symmetric difference of $S_{1}$
and $S_{2}$. Then, due to the independence of
$\bm{\nu}_{1},\ldots,\bm{\nu}_{k}$,

$\mathop{{\mathds{E}}\/}\left[\prod_{i\in
S_{1}}\phi_{\mu}(\bm{\nu}_{i})\prod_{i\in
S_{2}}\phi_{\mu}(\bm{\nu}_{i})\right]=\prod_{i\in S_{1}\cap
S_{2}}\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu}_{i})^{2}]\prod_{i\in
S_{1}\triangle S_{2}}\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu}_{i})].$

Since the mean of $\bm{\nu}_{i}$ is $\mu$,
$\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu}_{i})]=\phi_{\mu}(\mu)=0$. If
$S_{1}\neq S_{2}$, there is at least one element in $S_{1}\triangle S_{2}$,
and so the term is $0$. We are therefore left with,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{\nu}}\left[\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}(\bm{\nu})}[g(\bm{y})]^{2}\right]$
$\displaystyle=\sum_{S\subseteq[k]}\hat{g}(S)^{2}\prod_{i\in
S}\mathop{{\mathds{E}}\/}\left[\phi_{\mu}(\bm{\nu}_{i})^{2}\right].$

This is exactly the Fourier expansion for the claimed result. ∎

We’ll also use the following proposition.

######  Proposition 6.8.

For any random variable $\bm{\nu}$ bounded on $[-1,1]$ almost surely and with
mean $\mu$,

$\max\left(0,\frac{\mathop{{\mathds{E}}\/}[|\bm{\nu}|]^{2}-\mu^{2}}{1-\mu^{2}}\right)\leq\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}]\leq\frac{\mathop{{\mathds{E}}\/}[|\bm{\nu}|]-\mu^{2}}{1-\mu^{2}}.$

###### Proof.

We expand, using linearity of expectation,

$\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}]=\mathop{{\mathds{E}}\/}\left[\frac{(\bm{\nu}-\mu)^{2}}{1-\mu^{2}}\right]=\frac{\mathop{{\mathds{E}}\/}[\rho^{2}]-2\mu\mathop{{\mathds{E}}\/}[\bm{\nu}]+\mu^{2}}{1-\mu^{2}}.$

Since $\mathop{{\mathds{E}}\/}[\bm{\nu}]=\mu$, we have that
$\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}]=\frac{\mathop{{\mathds{E}}\/}[\bm{\nu}^{2}]-\mu^{2}}{1-\mu^{2}}$.
Therefore, by Jensen’s inequality,

$\frac{\mathop{{\mathds{E}}\/}[|\bm{\nu}|]^{2}-\mu^{2}}{1-\mu^{2}}\leq\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}].$

Furthermore, since $\bm{\nu}^{2}\leq|\bm{\nu}|$,

$\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}]\leq\frac{\mathop{{\mathds{E}}\/}[|\bm{\nu}|]-\mu^{2}}{1-\mu^{2}}.$

Lastly, $\mathop{{\mathds{E}}\/}[\phi_{\mu}(\bm{\nu})^{2}]\geq 0$ follows from
non-negativity. ∎

Finally, we are ready to prove Lemma 6.6.

###### Proof of Lemma 6.6.

For any $y\in\\{\pm 1\\}^{n}$, we define

$g_{\mathop{\mathrm{avg}}}(y)=\mathop{{\mathds{E}}\/}[g(\bm{x})\mid\bm{y}=y].$

Then, setting $h(y)\coloneqq\mathrm{sign}(g_{\mathop{\mathrm{avg}}}(y))$,

$\mathop{{\mathds{E}}\/}[g(\bm{x})h(\bm{y})]=\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\left|g_{\mathop{\mathrm{avg}}}(\bm{y})\right|\right]\geq\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\left(g_{\mathop{\mathrm{avg}}}(\bm{y})\right)^{2}\right].$

Note that, conditioning on $\bm{y}=y$, the distribution of $\bm{x}$ is still
product. Let $\nu(y)$ be the mean of this distribution, so that

$g_{\mathop{\mathrm{avg}}}(y)=\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(y)}}\left[g(\bm{z})\right].$

By Lemma 6.7,

$\mathop{{\mathds{E}}\/}_{\bm{y}}\left[\left(\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(\bm{y})}}\left[g(\bm{z})\right]\right)^{2}\right]=\mathrm{Stab}_{\mu,(\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{y})_{1})^{2}],\ldots,\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{y})_{k})^{2}]}(g).$

For each $i\in[k]$,

$\displaystyle\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{y})_{i})^{2}]$
$\displaystyle\geq\max\left(0,\frac{\mathop{{\mathds{E}}\/}_{\bm{y}}[|\nu(\bm{y})_{i}|]^{2}-\mu^{2}}{1-\mu^{2}}\right)$
( Proposition 6.8)
$\displaystyle\geq\max\left(0,\frac{\mathop{{\mathds{E}}\/}_{\bm{y}}[\bm{y}_{i}\nu(\bm{y})_{i}]^{2}-\mu^{2}}{1-\mu^{2}}\right)$
($|x|\geq cx$ when $c\in\\{\pm 1\\}$)
$\displaystyle=\max\left(0,\frac{\mathop{{\mathds{E}}\/}_{\bm{x},\bm{y}}[\bm{y}_{i}\bm{x}_{i}]^{2}-\mu^{2}}{1-\mu^{2}}\right)$
(Definition of $\nu(y)$) $\displaystyle=\alpha_{i}.$

Putting all of the above together,

$\displaystyle\mathop{{\mathds{E}}\/}[g(\bm{x})h(\bm{y})]$
$\displaystyle\geq\mathrm{Stab}_{\mu,(\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{y})_{1})^{2}],\ldots,\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{y})_{k})^{2}]}(g)$
$\displaystyle\geq\mathrm{Stab}_{\mu,\rho}(g),$

where the final inequality follows from the monotonicity of noise stability. ∎

###  6.2 Proof of the upper bound on advantage

In this section, we prove the following.

######  Lemma 6.9 (Part 2 of Theorem 3: Upper bound on advantage).

For any $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
$\mu\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})]$, and
$S_{1},\ldots,S_{k}$, define the _upper normalized correlation_ as

$\beta_{i}\coloneqq\frac{\mathrm{Adv}_{\mathcal{D}}(f,S_{i})-\mu^{2}}{1-\mu^{2}}.$

For $S\subseteq[n]\times[k]$ constructed by taking $S_{1}$ from the first
block, $S_{2}$ from the second block, and so on (formally
$S\coloneqq\cup_{i\in[k],j\in S_{i}}\\{(j,i)\\}$).. Then,

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,S)\leq\sqrt{\mathrm{Stab}_{\mu,\beta}(g)}.$

To begin with, we rewrite advantage in the following form.

######  Proposition 6.10.

For any function $q:\\{\pm 1\\}^{m}\to\\{\pm 1\\}$, distribution $\mathcal{D}$
over $\\{\pm 1\\}^{m}$, and $S\subseteq[m]$, define

$q_{S,\mathcal{D}}^{\mathop{\mathrm{avg}}}(x)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[q(\bm{y})\mid\bm{y}_{S}=x_{S}],$
(1)

where $y_{S}=x_{S}$ is shorthand for $x_{i}=y_{i}$ for all $i\in S$. Then,

$\mathrm{Adv}_{\mathcal{D}}(q,S)=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\left|q_{S,\mathcal{D}}^{\mathop{\mathrm{avg}}}(\bm{x})\right|\right].$

###### Proof.

Consider any $S$-junta $h$. Then,

$\mathrm{Adv}_{\mathcal{D}}(q,h)=\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[q(\bm{y})h(\bm{y})]=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[q(\bm{y})h(\bm{y})\mid\bm{x}_{S}=\bm{y}_{S}]\right].$

Since $h$ is an $S$-junta, it must classify $x$ and $y$ the same whenever
$x_{S}=y_{S}$. Therefore,

$\displaystyle\mathrm{Adv}(q,h)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[h(\bm{x})\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[q(\bm{y})\mid\bm{x}_{S}=\bm{y}_{S}]\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[h(\bm{x})q^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}}(\bm{x})\right].$

to maximize the above advantage among all $h$, we set
$h(x)=\mathrm{sign}(q^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}}(x))$, in which
case

$\mathrm{Adv}(q,h)=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\left|q^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}}(\bm{x})\right|\right].\qed$

Given Proposition 6.10, to compute $\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,S)$, it suffices to understand the function $(g\circ
f)^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}}$. We proceed to transform that
function into a form which is easier to understand.

######  Proposition 6.11.

In the setting of Lemma 6.9, for any $x\in(\\{\pm 1\\}^{n})^{k}$, let
$\nu(x)\in[-1,1]^{k}$ be the vector where

$\nu(x)_{i}\coloneqq\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}^{k}}[f(\bm{y})\mid
x^{(i)}_{S_{i}}=\bm{y}_{S_{i}}].$

Then,

$(g\circ
f)^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}^{k}}(x)=\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(x)}}[g(\bm{z})].$

###### Proof.

Consider drawing $\bm{y}\sim(\\{\pm 1\\}^{n})^{k}$ conditioned on
$\bm{y}_{S}=x_{S}$. Let $\bm{z}=f^{\otimes k}(\bm{y})$. By definition,

$(g\circ
f)^{\mathop{\mathrm{avg}}}_{S,\mathcal{D}^{k}}(x)=\mathop{{\mathds{E}}\/}[g(\bm{z})].$

Therefore, we merely need to show that the distribution of $\bm{z}$ is that of
$\pi_{\nu(x)}$. For this it is sufficient that,

  1. 1.

Each $\bm{z}_{1},\ldots,\bm{z}_{k}$ is independent. This follows from the fact
$\bm{y}_{1},\ldots,\bm{y}_{k}$ are independent, and that the restriction that
$\bm{y}_{S}=x_{S}$ is a disjoint restriction for each of the $k$ components.

  2. 2.

For each $i\in[k]$, that $\mathop{{\mathds{E}}\/}[\bm{z}_{i}]=\nu(x)_{i}$.
This follows from the definition of $\nu(x)_{i}$.

The desired result follows from the fact that $\pi_{\nu(x)}$ is the unique
product distribution over $\\{\pm 1\\}^{k}$ with mean $\nu(x)$. ∎

We now prove the upper bound.

###### Proof of Lemma 6.9.

Let $\nu$ be as defined in Proposition 6.11. Applying it and Proposition 6.10,

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,S)=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\left[\left|\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(\bm{x})}}[g(\bm{z})]\right|\right]\leq\sqrt{\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\left[\left(\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(\bm{x})}}[g(\bm{z})]\right)^{2}\right]}.$

The inequality above is Jensen’s. Consider the random variables
$\nu(\bm{x})_{1},\ldots,\nu(\bm{x})_{k}$. The have the following two
properties.

  1. 1.

They are independent. This is because the value of $\nu(\bm{x})_{i}$ depends
on only the value of $\bm{x}_{i}$, which is independent of the other
$\bm{x}_{j}$ for $j\neq i$.

  2. 2.

They each have mean $\mu$. This is because,

$\mathop{{\mathds{E}}\/}[\nu(\bm{x})_{i}]=\mathop{{\mathds{E}}\/}\left[\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[f(\bm{y})\mid(\bm{x}^{(i)})_{S_{i}}=y_{S_{i}}]\right]=\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[f(\bm{y})]=\mu.$

Therefore, we can use Lemma 6.7:

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\left[\left(\mathop{{\mathds{E}}\/}_{\bm{z}\sim\pi_{\nu(\bm{x})}}[g(\bm{z})]\right)^{2}\right]=\mathrm{Stab}_{\mu,(\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{x})_{1})^{2}],\ldots,\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{x})_{k})^{2}])}(g).$

We can further upper bound,

$\displaystyle\mathop{{\mathds{E}}\/}[\phi_{\mu}(\nu(\bm{x})_{i})^{2}]$
$\displaystyle\leq\frac{\mathop{{\mathds{E}}\/}[|\nu(\bm{x})_{i}|]-\mu^{2}}{1-\mu^{2}}$
(Proposition 6.8)
$\displaystyle=\frac{\mathrm{Adv}(f,S_{i})-\mu^{2}}{1-\mu^{2}}$ (Proposition
6.10) $\displaystyle=\beta_{i}.$

Putting the above together, we have that

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,S)\leq\sqrt{\mathrm{Stab}_{\mu,\beta}(g)}.\qed$

###  6.3 Proofs of the consequences of our strong composition theorem

In this section, we complete the proofs of Corollary 6.1 and Theorem 1.

###### Proof of Theorem 1.

For any partition of the budget junta budget $r_{1}+\cdots+r_{k}=R$, let
$\vec{\rho}(r_{1},\ldots,r_{k})$ be the vector,

$\vec{\rho}(r_{1},\ldots,r_{k})_{i}\coloneqq\mathrm{Adv}_{D}(f,r_{i}).$

Then, applying the upper bound on advantage of Theorem 3 and maximizing over
all possible partitions of the budget $R$, we have that

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,R)\leq\max_{r_{1}+\cdots+r_{k}=R}\sqrt{\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})}(g)}.$

This completes the upper bound on the advantage of the optimal $R$-junta
approximator of $g\circ f$ of Theorem 1. For the lower bound on the advantage
of the optimal _composed form_ approximator, let $r_{1},\ldots,r_{k}$ be the
partition of budget maximizing
$\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})}(g)$. Using the lower bound of
Theorem 3, and using $(\cdot)^{2}$ to refer to an elementwise squaring of a
vector,

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ
f,h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}))\geq\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})^{2}}(g).$

Using the Fourier expression for stability Proposition 5.2,

$\displaystyle\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})^{2}}(g)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[((\vec{\rho}(r_{1},\ldots,r_{k})^{2})^{\bm{S}}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[((\vec{\rho}(r_{1},\ldots,r_{k})^{\bm{S}})^{2}\right]$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[((\vec{\rho}(r_{1},\ldots,r_{k})^{\bm{S}})\right]^{2}$
(Jensen’s inequality)
$\displaystyle=\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})}(g)^{2}.$

Therefore, there is a composed form approximator with advantage at least
$\mathrm{Stab}_{\vec{\rho}(r_{1},\ldots,r_{k})}(g)^{2}$. ∎

Our proof of Corollary 6.1 uses the following.

######  Proposition 6.12.

For any $\alpha_{1},\ldots,\alpha_{m}\in[0,1]$ and
$\beta_{1},\ldots,\beta_{m}\in[0,1]$, satisfying $(1-\alpha_{i})\leq
2(1-\beta_{i})$ for each $i\in[m]$,

$1-\prod_{i\in[m]}\alpha_{i}\leq 2\left(1-\prod_{i\in[m]}\beta_{i}\right).$

###### Proof.

We consider the vector $\beta^{\prime}\in[0,1]^{m}$ satisfying

$1-\alpha_{i}=2\cdot(1-\beta^{\prime}_{i}).$

Note that $\beta^{\prime}_{i}\geq\beta_{i}$, which means that

$1-\prod_{i\in[m]}\beta^{\prime}_{i}\leq 1-\prod_{i\in[m]}\beta_{i}.$

Now, consider the function $q:[0,1]\to[0,1]$ defined as

$q(x)\coloneqq 1-\prod_{i\in[m]}1-x(1-\alpha_{i}).$

A quick calculation confirms that the second derivative of $q$ is nonpositive,
so $q$ is concave. Furthermore, it satisfies,

$\displaystyle q(0)$ $\displaystyle=0,$ $\displaystyle q(1)$
$\displaystyle=1-\prod_{i\in[m]}\alpha_{i},$ $\displaystyle q(1/2)$
$\displaystyle=1-\prod_{i\in[m]}\beta^{\prime}_{i}.$

We conclude,

$1-\prod_{i\in[m]}\alpha_{i}\overset{\text{concavity of
$q$}}{\leq}2\left(1-\prod_{i\in[m]}\beta^{\prime}_{i}\right)\leq\left(1-\prod_{i\in[m]}\beta_{i}\right).\qed$

###### Proof of Corollary 6.1.

Let $r_{1}+\cdots+r_{k}=R$ be the partition of $R$ used in the junta achieving
minimum error relative to $g\circ f$ and define, for each $i\in[k]$,

$\displaystyle\alpha_{i}$
$\displaystyle\coloneqq\max\left(0,\frac{\mathrm{Adv}_{\mathcal{D}}(f,r_{i})^{2}-\mu^{2}}{1-\mu^{2}}\right),$
$\displaystyle\beta_{i}$
$\displaystyle\coloneqq\max\left(0,\frac{\mathrm{Adv}_{\mathcal{D}}(f,r_{i})-\mu^{2}}{1-\mu^{2}}\right),$

which satisfy the relation

$1-\alpha_{i}\leq 2(1-\beta_{i}).$

Applying Theorem 3 and the relation $\mathrm{error}=\frac{1-\mathrm{Adv}}{2}$,
we have that

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ
f,R)\geq\frac{1-\sqrt{\mathrm{Stab}_{\mu,\beta}(g)}}{2},\quad\quad\text{and}\quad\quad\mathrm{error}_{\mathcal{D}^{k}}(g\circ
f,h(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}))\leq\frac{1-\mathrm{Stab}_{\mu,\alpha}(g)}{2}.$

Our goal is to show the following series of inequalities, which would imply
the desired result,

$1-\mathrm{Stab}_{\mu,\alpha}(g)\overset{(\text{iq
}1)}{\leq}2(1-\mathrm{Stab}_{\mu,\beta}(g))\overset{(\text{iq
}2)}{\leq}4(1-\sqrt{\mathrm{Stab}_{\mu,\beta}(g)}).$

The second, (inequality 2), follows the fact that for any $x\in[0,1]$,
$(1-x)\leq 2(1-\sqrt{x})$. For the first inequality, using Proposition 5.2, we
can express stability via the Fourier spectrum of $g$ as

$\displaystyle 1-\mathrm{Stab}_{\mu,\alpha}(g)$
$\displaystyle=\sum_{S}\hat{g}(S)^{2}(1-\prod_{i\in S}\alpha_{i})$
$\displaystyle\leq 2\sum_{S}\hat{g}(S)^{2}(1-\prod_{i\in S}\beta_{i})$
(Proposition 6.12, $1-\alpha_{i}\leq 2(1-\beta_{i})$)
$\displaystyle=2(1-\mathrm{Stab}_{\mu,\beta}(g)).$

This proves inequality 1, giving the desired result. ∎

##  7 Multivariate noise stability of symmetric functions

In this section, we prove Lemma 2.2 and Corollary 2.3, connecting the
multivariate noise stability of symmetric functions to their univariate noise
stability.

######  Definition 9 (Symmetric and transitive functions).

For any function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, a permutation
$\sigma:[k]\to[k]$ is an automorphism of $g$ if for all inputs $x\in\\{\pm
1\\}^{k}$,

$g(x)=g(x_{\sigma(1)},\ldots,x_{\sigma(k)}).$

We say $g$ is _symmetric_ if every permutation of $[k]$ is an automorphism of
$g$. Similarly, $g$ is _transitive_ if for all $i,j\in[k]$, there is an
automorphism of $g$ sending $i$ to $j$.

###  7.1 The upper bound on the multivariate noise stability of symmetric
functions

######  Lemma 7.1 (Upper bound of Lemma 2.2).

For any symmetric $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $\mu\in(-1,1)$, and
$\vec{\rho}\in[0,1]^{k}$, let $\rho^{(\mathrm{AM})}\coloneqq
1/k\cdot\sum_{i\in[k]}\vec{\rho}_{i}$. Then,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)\leq\mathrm{Stab}_{\mu,\rho^{(\mathrm{AM})}}(g).$

Our proof of Lemma 7.1 will use make heavy use of the _negative association_
of random variables.

######  Definition 10 (Negative association [JDP83]).

A set of random variables $\bm{x}_{1},\ldots,\bm{x}_{m}$ supported on
$\mathds{R}$ are _negatively associated_ if for all _disjoint_ subsets
$S_{1},S_{2}\subseteq[m]$ and $S_{1}$-juntas
$f_{1}:\mathds{R}^{m}\to\mathds{R}$, $S_{2}$-juntas
$f_{2}:\mathds{R}^{m}\to\mathds{R}$ both monotonically nondecreasing,

$\mathop{{\mathds{E}}\/}[f_{1}(\bm{x})f_{2}(\bm{x})]\leq\mathop{{\mathds{E}}\/}[f_{1}(\bm{x})]\mathop{{\mathds{E}}\/}[f_{2}(\bm{x})].$

For our purposes, we will only need a few useful facts about negatively
associated random variables given in [JDP83] (see also [Waj17] for a useful
overview).

######  Fact 7.2 (Permutation distributions are negatively associated,
[JDP83]).

For any $z_{1},\ldots,z_{m}\in\mathds{R}$, draw a uniformly random permutation
$\bm{\sigma}:[m]\to[m]$ and set $\bm{x}_{i}=z_{\bm{\sigma}(i)}$ for each
$i\in[k]$. Then, $\bm{x}_{1},\ldots,\bm{x}_{m}$ are negatively associated.

######  Fact 7.3 (Subsets of negatively associated random variables are
negatively associated).

For any $2\leq m^{\prime}\leq m$, if $\bm{x}_{1},\ldots,\bm{x}_{m}$ are
negatively associated, then $\bm{x}_{1},\ldots,\bm{x}_{m^{\prime}}$ are also
negatively associated.

######  Fact 7.4 (Product consequence of negative association).

For any negatively associated $\bm{x}_{1},\ldots,\bm{x}_{m}$ and nondecreasing
$f:\mathds{R}\to\mathds{R}_{\geq 0}$,

$\mathop{{\mathds{E}}\/}\left[\prod_{i\in[m]}f(\bm{x}_{i})\right]\leq\prod_{i\in[m]}\mathop{{\mathds{E}}\/}\left[f(\bm{x}_{i})\right].$

Given the above, facts about negative associated random variables, we can now
prove Lemma 7.1.

###### Proof of Lemma 7.1.

We expand $\mathrm{Stab}_{\mu,\vec{\rho}}(g)$ using the Fourier spectrum of
$g$ (Proposition 5.2),

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}[(\vec{\rho})^{\bm{S}}].$

Let $\bm{\ell}$ be the distributed the same as $|\bm{S}|$ for
$\bm{S}\sim\mathcal{S}_{\mu}(g)$. Then,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}[(\vec{\rho})^{\bm{S}}\mid|\bm{S}|=\ell]\right].$

Since $g$ is symmetric, for any $|S_{1}|=|S_{2}|$,
$\hat{g}(S_{1})=\hat{g}(S_{2})$. As a result the distribution of
$\bm{S}\sim\mathcal{S}_{\mu}(g)$ conditioned on $|\bm{S}|=\ell$ is simply a
uniformly random size-$\ell$ subset of $[k]$. Formally,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\binom{[k]}{\bm{\ell}}}[(\vec{\rho})^{\bm{S}}]\right].$

Let $\bm{x}_{1},\ldots,\bm{x}_{k}$ be a uniform random permutation of
$\vec{\rho}_{1},\ldots,\vec{\rho}_{k}$. Then, the distribution of
$(\vec{\rho})^{\bm{S}}$ for $\bm{S}\sim\binom{[k]}{\ell}$ is identical to that
of $\prod_{i\in[\ell]}\bm{x}_{i}$. By Facts 7.2 and 7.3,
$\bm{x}_{1},\ldots,\bm{x}_{\ell}$ are negatively associated, and so,

$\mathop{{\mathds{E}}\/}_{\bm{S}\sim\binom{[k]}{\ell}}[(\vec{\rho})^{\bm{S}}]=\mathop{{\mathds{E}}\/}\left[\prod_{i\in[\ell]}\bm{x}_{i}\right]\overset{\mathrm{(\lx@cref{creftypecap~refnum}{fact:NA-
prod})}}{\leq}\prod_{i\in[\ell]}\mathop{{\mathds{E}}\/}[\bm{x}_{i}]=\left(\rho^{(\mathrm{AM})}\right)^{\ell}.$

Therefore,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\left(\rho^{(\mathrm{AM})}\right)^{\bm{\ell}}\right]=\mathrm{Stab}_{\mu,\rho^{(\mathrm{AM})}}(g).\qed$

###  7.2 The lower bound on the multivariate noise stability of symmetric
functions

######  Lemma 7.5 (Lower bound of Lemma 2.2).

For any transitive $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $\mu\in(-1,1)$, and
$\vec{\rho}\in[0,1]^{k}$, let
$\rho^{(\mathrm{GM})}\coloneqq\left(\prod_{i\in[k]}\vec{\rho}_{i}\right)^{1/k}$.
Then,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)\geq\mathrm{Stab}_{\mu,\rho^{(\mathrm{GM})}}(g).$

Note that every transitive $g$ is also symmetric, but the reverse does not
hold.

###### Proof.

Similarly to the proof of Lemma 7.1, let $\bm{\ell}$ be the distribution of
$|\bm{S}|$ when $\bm{S}\sim\mathcal{S}_{\mu}(g)$. Then,

$\mathrm{Stab}_{\mu,\vec{\rho}}(g)=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}[(\vec{\rho})^{\bm{S}}\mid|\bm{S}|=\bm{\ell}]\right].$

For each $S\subseteq[k]$, we’ll use $\chi(S)\in\\{0,1\\}^{k}$ to denote the
characteristic vector of $S$, meaning $\chi(S)_{i}\coloneqq\mathds{1}[i\in
S]$. Then,

$\displaystyle\mathrm{Stab}_{\mu,\vec{\rho}}(g)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[\prod_{i\in[k]}(\vec{\rho}_{i})^{\chi(\bm{S})_{i}}\,\bigg{|}\,|\bm{S}|=\bm{\ell}\right]\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[\exp\left(\sum_{i\in[k]}\chi(\bm{S})_{i}\log(\vec{\rho}_{i})\right)\,\bigg{|}\,|\bm{S}|=\bm{\ell}\right]\right]$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\exp\left(\mathop{{\mathds{E}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[\sum_{i\in[k]}\chi(\bm{S})_{i}\log(\vec{\rho}_{i})\,\bigg{|}\,|\bm{S}|=\bm{\ell}\right]\right)\right]$
(Jensen’s inequality)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\exp\left(\sum_{i\in[k]}\log(\vec{\rho}_{i})\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[i\in\bm{S}\mid|\bm{S}|=\bm{\ell}\right]\right)\right].$
(Linearity of expectation)

Fix any $i_{1},i_{2}\in[k]$ and level $\ell\in[0,k]$. Since $g$ is transitive,
there is an automorphism, $\sigma$, of $g$ sending $i_{1}$ to $i_{2}$. Since
$\sigma$ is an automorphism of $g$, for any $S\subseteq[k]$, for
$\bm{S}\sim\mathcal{S}_{\mu}(g)$,
$\operatorname{{Pr}}[\bm{S}=S]=\operatorname{{Pr}}[\bm{S}=\sigma(S)]$. As a
result

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[i_{1}\in\bm{S}\mid|\bm{S}|=\ell\right]=\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[i_{2}\in\bm{S}\mid|\bm{S}|=\ell\right],$

and so
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{S}\sim\mathcal{S}_{\mu}(g)}\left[i\in\bm{S}\mid|\bm{S}|=\ell\right]$
must be the same for all $i\in[k]$. The sum of these probabilities is $\ell$,
meaning each is $\frac{\ell}{k}$. This allows us to bound,

$\displaystyle\mathrm{Stab}_{\mu,\vec{\rho}}(g)$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\exp\left(\sum_{i\in[k]}\log(\vec{\rho}_{i})\cdot\frac{\bm{\ell}}{k}\right)\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[\prod_{i\in[k]}\left(\vec{\rho}_{i}\right)^{\frac{\bm{\ell}}{k}}\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\left[(\rho^{(\mathrm{GM})})^{\bm{\ell}}\right]=\mathrm{Stab}_{\mu,\rho^{(\mathrm{GM})}}(g).\qed$

###  7.3 Bounding the $(\delta,\varepsilon)$-noise stability of symmetric
functions

Recall, from Definition 3, that the $(\delta,\varepsilon)$-noise stability of
a function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ is the quantity

$\max\big{\\{}\mathrm{Stab}_{\vec{\rho}}(g)\colon\text{at least
$\delta$-fraction of $\vec{\rho}$'s coordinates are at most
$1-2\varepsilon$}\big{\\}}.$

We prove Corollary 2.3, restated below.

######  Corollary 7.6 (Formal version of Corollary 2.3).

For any symmetric function $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$,
$\delta\in(0,1)$, and $\varepsilon\in(0,1/2)$, let
$\delta^{\prime}\coloneqq\frac{\lceil k\delta\rceil}{k}$ be $\delta$ rounded
up to the nearest integer multiple of $1/k$. Then, the
$(\delta,\varepsilon)$-noise stability of $g$ is equal to
$\mathrm{Stab}_{\mu,\rho^{\star}}(g)$ for some $\rho^{\star}$ satisfying

$1-2\delta^{\prime}\varepsilon-4\varepsilon^{2}\leq\rho^{\star}\leq
1-2\delta^{\prime}\varepsilon.$

###### Proof of Corollary 7.6.

Since stability is monotone (Corollary 5.3), the $(\delta,\varepsilon)$-noise
stability of $g$ is its multivariate noise stability with a correlation vector
$\vec{\rho}$ where $\delta^{\prime}$ fraction of the coordinates are
$1-2\varepsilon$ and the remainder are $1$. The arithmetic mean of this vector
is exactly $1-2\delta^{\prime}\varepsilon$, and its geometric mean is
$(1-2\varepsilon)^{\delta^{\prime}}$. The desired result then follows from
Lemmas 7.5 and 7.1 and the inequality

$(1-x)^{c}\geq 1-cx-(1-c)x^{2}\geq 1-cx-x^{2}$

which holds for all $c,x\in[0,1]$. To prove this inequality, it is sufficient
that $q_{c}(x)\geq 0$ for all $x,c\in[0,1]$ where

$q_{c}(x)\coloneqq(1-x)^{c}-1+cx+(1-c)x^{2}.$

To see this, we note that for any $c\in[0,1]$, the function $q_{c}(x)$ has
roots at $x=0$ and $x=1$. It is furthermore increasing at $x=0$, and
decreasing at $x=1$. If $q_{c}(x)$ were to be negative for any $x\in[0,1]$,
then, it would need to have at least $3$ local extrema. However, the
derivative $q_{c}^{\prime}(x)$ is concave, so it can only be zero at a maximum
of $2$ points. This proves the desired inequality. (If the reader prefers,
Figure 1 gives a “proof by picture”.) ∎

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.1$$0.2$$0.3$$x$$q_{c}(x)$$c=0.3$$c=0.5$$c=0.7$
Figure 1: Plots of $q_{c}$ defined in the proof of Corollary 7.6 for various
values of $c$, showing that $q_{c}(x)\geq 0$ for all $x\in[0,1]$.

##  8 Composition theorems yield boosters for property testing

###  8.1 A general boosting framework

Let $\mathcal{P}=\left\\{\mathcal{P}_{s}\right\\}_{s\in\mathds{N}}$ be a
parametrized property of Boolean functions. For a function $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ and distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$,
we write

$\mathrm{dist}_{\mathcal{D}}(f,\mathcal{P}_{s})\coloneqq\min_{h\in\mathcal{P}_{s}}\mathrm{error}_{\mathcal{D}}(f,h)$

to denote $f$’s distance to $\mathcal{P}_{s}$ over $\mathcal{D}$. We are
interested in the relaxed testing regime for size parameters $s>s^{\prime}$
where we want to decide whether an unknown target function $f$ belongs to
$\mathcal{P}_{s}$ or is $\varepsilon$-far from $\mathcal{P}_{s^{\prime}}$
under $\mathcal{D}$:
$\mathrm{dist}_{\mathcal{D}}(f,\mathcal{P}_{s^{\prime}})>\varepsilon$ (recall
Definition 4). We say that $\mathcal{P}$ is
$(\varepsilon,s,s^{\prime})$-testable if there exists an algorithm for
$(\varepsilon,s,s^{\prime})$-testing $\mathcal{P}$ for every distribution
$\mathcal{D}$. As $\varepsilon\to 0$, the gap between the Yes and No cases
becomes smaller and $(\varepsilon,s,s^{\prime})$-testing becomes more
difficult. The main result of this section is that if $\mathcal{P}$ “behaves
well” under function composition, then testers for large $\varepsilon$ can be
boosted to testers for the more challenging regime of small $\varepsilon$. We
will specialize our attention to properties which behave linearly with respect
to function composition.

######  Definition 11 (Linear with respect to composition).

A parametrized property
$\mathcal{P}=\left\\{\mathcal{P}_{s}\right\\}_{s\in\mathds{N}}$ behaves
linearly (with respect to function composition) if

$f\in\mathcal{P}_{s}\quad\Rightarrow\quad g\circ f\in\mathcal{P}_{k\cdot s}$

for all $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$, $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
and $s\in\mathds{N}$.

##### Examples.

Being an $s$-junta, depth-$s$ decision tree, depth-$s$ formula, or degree-$s$
polynomial are all properties of Boolean functions which behave linearly with
respect to composition. As is often the case, it is straightforward to show
from their definitions that these properties behave linearly. Many properties
which do not a priori behave linearly can be converted into ones that do by
applying an appropriate transformation to their size. For example, the
property $\mathcal{P}_{s}=\\{\text{size-exp}(s)\text{ decision trees}\\}$
behaves linearly.

##### Strong composition theorems for properties.

A property $\mathcal{P}$ which behaves linearly with respect to function
composition is said to admit a strong composition theorem if the upper bound
from Definition 11 can be shown to be nearly tight. This definition
generalizes the relation $\diamondsuit$ ‣ 2.1.

######  Definition 12
($(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem).

A parametrized property
$\mathcal{P}=\left\\{\mathcal{P}_{s}\right\\}_{s\in\mathds{N}}$ admits an
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem with respect to $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ for
$\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}}\in(0,1)$ and a
constant $\lambda>0$ if

$\mathrm{dist}_{\mathcal{D}}(f,\mathcal{P}_{s})>\varepsilon_{\mathrm{small}}\quad\Rightarrow\quad\mathrm{dist}_{\mathcal{D}^{k}}(g\circ
f,\mathcal{P}_{\lambda ks})>\varepsilon_{\mathrm{large}}$

for all $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and distributions $\mathcal{D}$ over
$\\{\pm 1\\}^{n}$.

Strong composition theorems depend on the combining function $g$. For example,
if $g$ is a constant function then one would not expect the upper bound from
Definition 11 to be tight. For this reason, the dependence on $g$ is made
explicit in the definition of strong composition theorem. Roughly speaking,
the definition says that if a property $\mathcal{P}$ behaves linearly and
admits a strong composition theorem with respect to $g$, then composing with
$g$ turns a function in $\mathcal{P}_{s}$ into one in $\mathcal{P}_{sk}$ and
turns a function slightly far from $\mathcal{P}_{s}$ into one very far from
$\mathcal{P}_{\Theta(sk)}$. For a fixed $\varepsilon_{\mathrm{large}}$, having
an
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem with respect to $g$ becomes stronger as $\varepsilon_{\mathrm{small}}$
approaches $0$. In general, we are interested in
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorems when $\varepsilon_{\mathrm{large}}\gg\varepsilon_{\mathrm{small}}$.
The parameter $\lambda$ is built into the definition to tolerate a small
amount of slack between the upper and lower bounds on $g\circ f$. For many
applications, this constant factor is necessary. We are now equipped to state
our main boosting theorem.

######  Theorem 4 (Boosting property testers, formal version of Theorem 2).

Let $\mathcal{P}=\\{\mathcal{P}_{s}\\}_{s\in\mathds{N}}$ be a property which
behaves linearly and admits an
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem with respect to $g:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$. If $\mathcal{P}$ is
$(\varepsilon_{\mathrm{large}},s,s^{\prime})$-testable in
$q(\varepsilon_{\mathrm{large}},s,s^{\prime})$ queries, then it is
$(\varepsilon_{\mathrm{small}},s,\lambda^{-1}s^{\prime})$-testable using
$k\cdot q(\varepsilon_{\mathrm{large}},ks,ks^{\prime})$ many queries.

###### Proof.

Let $\mathcal{T}_{\mathrm{weak}}$ be an algorithm for
$(\varepsilon_{\mathrm{large}},s,s^{\prime})$-testing $\mathcal{P}$. Given
queries to a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and random samples
from a distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$, we
$(\varepsilon_{\mathrm{small}},s,\lambda^{-1}s^{\prime})$-test $\mathcal{P}$
using the procedure in Figure 2 where $\mathcal{T}_{\mathrm{weak}}$ is given
an instance of $(\varepsilon_{\mathrm{large}},ks,ks^{\prime})$-testing
$\mathcal{P}$.

$\mathcal{T}_{\mathrm{strong}}$, a boosted tester for $\mathcal{P}$: Given:
$\mathcal{T}_{\mathrm{weak}}$, a weak tester for $\mathcal{P}$; queries to
$f$; and random samples from $\mathcal{D}$ Run: Simulate
$\mathcal{T}_{\mathrm{weak}}$ providing it with – queries: return
$g(f(x^{(1)}),\ldots,f(x^{(k)}))$ for a query
$(x^{(1)},\ldots,x^{(k)})\in(\\{\pm 1\\}^{n})^{k}$; and – random samples:
return $(\bm{x}^{(1)},\ldots,\bm{x}^{(k)})\sim\mathcal{D}^{k}$ from $k$
independent samples $\bm{x}^{(i)}\sim\mathcal{D}$. Output: Yes if and only if
$\mathcal{T}_{\mathrm{weak}}$ outputs Yes Figure 2: Boosting a weak tester via
function composition.

##### Query complexity.

The target $g\circ f:\\{\pm 1\\}^{nk}\to\\{\pm 1\\}$ is a
$(\varepsilon_{\mathrm{large}},ks,ks^{\prime})$-testing instance for
$\mathcal{T}_{\mathrm{weak}}$. Therefore, $\mathcal{T}_{\mathrm{weak}}$ makes
$q(\varepsilon_{\mathrm{large}},ks,ks^{\prime})$ queries to the target $g\circ
f:\\{\pm 1\\}^{nk}\to\\{\pm 1\\}$ before terminating. Our tester makes $k$
queries to $f$ for each query to $g\circ f$. So our tester for $f$ makes
$k\cdot q(\varepsilon_{\mathrm{large}},ks,ks^{\prime})$ queries in total.

##### Correctness.

In the Yes case, $f\in\mathcal{P}_{s}$. We then have $g\circ
f\in\mathcal{P}_{sk}$ since $\mathcal{P}$ behaves linearly. This ensures that
$\mathcal{T}_{\mathrm{weak}}$ outputs Yes. In the No case,
$\mathrm{dist}_{\mathcal{D}}(f,\mathcal{P}_{s^{\prime}/\lambda})>\varepsilon_{\mathrm{small}}$.
We then have $\mathrm{dist}_{\mathcal{D}^{k}}(g\circ
f,\mathcal{P}_{ks^{\prime}})>\lambda$ since $\mathcal{P}$ admits an
$(\varepsilon_{\mathrm{large}},\varepsilon_{\mathrm{small}},\lambda)$-composition
theorem. This ensures that $\mathcal{T}_{\mathrm{weak}}$ outputs No. ∎

###  8.2 Implications for current landscape of junta testing

Our results have new implications for tolerantly testing juntas. In this
regime, the Yes case of Definition 4 is relaxed to only require that $f$ is
close to an $r$-junta over $\mathcal{D}$.

######  Definition 13 (Tolerantly
$(\varepsilon_{\mathrm{yes}},\varepsilon_{\mathrm{no}},r,r^{\prime})$-testing
juntas).

Given parameters $r\leq r^{\prime}$ and
$\varepsilon_{\mathrm{yes}}\leq\varepsilon_{\mathrm{no}}$, queries to an
unknown function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, and random samples from a
distribution $\mathcal{D}$ over $\\{\pm 1\\}^{n}$, distinguish between

  * •

Yes: $f$ is $\varepsilon_{\mathrm{yes}}$-close to being an $r$-junta under
$\mathcal{D}$, and

  * •

No: $f$ is $\varepsilon_{\mathrm{no}}$-far from being an $r^{\prime}$-junta
under $\mathcal{D}$.

In all of our applications, we will be using Theorem 4, or a variant of it,
with $g$ set to $\mathrm{XOR}_{k}$. For this reason, we start with some useful
properties about the noise stability of parity.

####  8.2.1 Noise stability of parity under general product distributions

######  Lemma 8.1.

For any $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mathcal{D}$ over
$\\{\pm 1\\}^{n}$, junta budget $R$, and $R$-junta $h$,

$\mathrm{error}_{\mathcal{D}^{k}}(\mathrm{XOR}_{k}\circ
f,h)\geq\min_{r_{1}+\cdots+r_{k}=R}\frac{1-\sqrt{\prod_{i\in[k]}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}}{2}.$

Our proof of Lemma 8.1 will use the multivariate noise stability of parity.

######  Proposition 8.2 (The multivariate noise stability of parity).

For any $\mu\in(-1,1)$, $\vec{\rho}\in[0,1]^{k}$,

$\mathrm{Stab}_{\mu,\vec{\rho}}(\mathrm{XOR}_{k})=\prod_{i\in[k]}\left(\vec{\rho}_{i}+(1-\vec{\rho}_{i})\cdot\mu^{2}\right)=\prod_{i\in[k]}\left(1-(1-\vec{\rho}_{i})(1-\mu^{2})\right).$

###### Proof.

Note that $\mathrm{XOR}_{k}(y_{1},\ldots,y_{k})=\prod_{i\in[k]}y_{i}$.
Therefore,

$\mathrm{Stab}_{\mu,\vec{\rho}}(\mathrm{XOR}_{k})=\mathop{{\mathds{E}}\/}_{\bm{y}\sim(\pi_{\mu})^{k},\bm{z}\overset{\vec{\rho}}{\sim}\bm{y}}\left[\prod_{i\in[k]}\bm{y}_{i}\bm{z}_{i}\right].$

Each pair $(\bm{y}_{i},\bm{z}_{i})$ are independent of another, so

$\mathrm{Stab}_{\mu,\vec{\rho}}(\mathrm{XOR}_{k})=\prod_{i\in[k]}\mathop{{\mathds{E}}\/}\left[\bm{y}_{i}\bm{z}_{i}\right].$

The distribution of $(\bm{y}_{i},\bm{z}_{i})$ can be succinctly described:
With probability $\vec{\rho}_{i}$, $\bm{z}_{i}=\bm{y}_{i}$. Otherwise, they
are each independent draws from $\pi_{\mu}$. Therefore,

$\mathop{{\mathds{E}}\/}\left[\bm{y}_{i}\bm{z}_{i}\right]=\vec{\rho}_{i}+(1-\vec{\rho}_{i})\cdot\mu^{2}.$

The desired result follows from combining the above equations ∎

###### Proof of Lemma 8.1.

We apply our strong composition theorem, Theorem 3. It is stated in terms of
advantage and gives

$\max_{R\text{-juntas }h}\mathrm{Adv}_{\mathcal{D}^{k}}(\mathrm{XOR}_{k}\circ
f,h)\leq\max_{r_{1}+\cdots+r_{k}=R}\sqrt{\mathrm{Stab}_{\mu,\beta(r_{1},\ldots,r_{k})}(\mathrm{XOR}_{k})},$

where we define
$\mu=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})]$, and
$\beta(r_{1},\ldots,r_{k})\in[0,1]^{k}$ is the vector

$\beta(r_{1},\ldots,r_{k})_{i}=\frac{\mathrm{Adv}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})-\mu^{2}}{1-\mu^{2}}=\frac{1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})-\mu^{2}}{1-\mu^{2}}.$

Applying Proposition 8.2,

$\displaystyle\max_{R\text{-juntas
}h}\mathrm{Adv}_{\mathcal{D}^{k}}(\mathrm{XOR}_{k}\circ f,h)$
$\displaystyle\leq\max_{r_{1}+\cdots+r_{k}=R}\sqrt{\prod_{i\in[k]}\left(1-\left(1-\frac{1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})-\mu^{2}}{1-\mu^{2}}\right)(1-\mu^{2})\right)}$
$\displaystyle=\max_{r_{1}+\cdots+r_{k}=R}\sqrt{\prod_{i\in[k]}\left(1-\left(\frac{2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})}{1-\mu^{2}}\right)(1-\mu^{2})\right)}$
$\displaystyle=\max_{r_{1}+\cdots+r_{k}=R}\sqrt{\prod_{i\in[k]}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}.$

The desired result follows from $\mathrm{error}=\frac{1-\mathrm{Adv}}{2}$. ∎

####  8.2.2 Warmup: weak testers suffice for
$(0,\varepsilon,r,r^{\prime})$-testing juntas

We first boost tolerant testers in the regime where
$\varepsilon_{\mathrm{yes}}$ is fixed to $0$ in Definition 13. This version is
slightly easier to state and is also the version we will use later in proving
Theorem 7.

######  Theorem 5 (Boosting $(0,\varepsilon,r,r^{\prime})$-testers for
juntas).

If juntas can be $(0,\varepsilon_{\mathrm{large}},r,r^{\prime})$-tested using
$q(\varepsilon_{\mathrm{large}},r,r^{\prime})$ queries, then for all
$k\in\mathds{N}$ and $\lambda\in(0,1)$, they can be
$(0,\varepsilon_{\mathrm{small}},r,\lambda^{-1}r^{\prime})$-tested in $k\cdot
q(\varepsilon_{\mathrm{large}},kr,kr^{\prime})$ queries where

$\varepsilon_{\mathrm{large}}=\frac{1-(1-2\varepsilon_{\mathrm{small}})^{{(1-\lambda)k}/{2}}}{2}.$

We will need to following composition theorem for juntas. It is a more precise
version of Corollary 2.1 stated in terms of Definition 12.

######  Lemma 8.3.

For any $\lambda\in(0,1)$, the property of being an $r$-junta admits an
$(\varepsilon_{\mathrm{small}},\varepsilon_{\mathrm{large}},\lambda)$-composition
theorem with respect to $\mathrm{XOR}_{k}$ for any
$\varepsilon_{\mathrm{small}}\leq\varepsilon_{\mathrm{large}}$ where

$\varepsilon_{\mathrm{large}}=\frac{1-(1-2\varepsilon_{\mathrm{small}})^{{(1-\lambda)k}/{2}}}{2}.$

###### Proof.

Assume that $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ is
$\varepsilon_{\mathrm{small}}$-far from being an $r$-junta over $\mathcal{D}$.
We would like to show that $\mathrm{XOR}_{k}\circ f$ is
$\varepsilon_{\mathrm{large}}$-far from being a $\lambda rk$-junta over
$\mathcal{D}^{k}$ where $\varepsilon_{\mathrm{large}}$ is defined as in the
lemma statement. Let $r_{1}+\cdots+r_{k}=\lambda rk$ be the partition of the
junta budgets which minimizes the expression

$\frac{1-\sqrt{\prod_{i\in[k]}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}}{2}$

from Lemma 8.1. Let $A_{\leq r}\subseteq[k]$ denote the indices for which
$r_{i}\leq r$ and let $A_{>r}=[k]\setminus A_{\leq r}$. By a counting
argument, at least a $(1-\lambda)$-fraction of $r_{i}$ satisfy $r_{i}\leq r$
and so $|A_{\leq r}|\geq(1-\lambda)k$. By our assumption that $f$ is far from
being an $r$-junta, for these $r_{i}$, we get
$\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})>\varepsilon_{\mathrm{small}}$.
Therefore, we can conclude that for any $\lambda rk$-junta $h:\\{\pm
1\\}^{nk}\to\\{\pm 1\\}$:

$\displaystyle\mathrm{error}_{\mathcal{D}^{k}}(\mathrm{XOR}_{k}\circ f,h)$
$\displaystyle\geq\frac{1-\sqrt{\prod_{i\in[k]}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}}{2}$
(Lemma 8.1) $\displaystyle=\frac{1-\sqrt{\prod_{i\in A_{\leq
r}}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)\cdot\prod_{i\in
A_{>r}}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}}{2}$
$\displaystyle\geq\frac{1-\sqrt{\prod_{i\in A_{\leq
r}}\left(1-2\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})\right)}}{2}$
($\mathrm{error}\leq\frac{1}{2}$)
$\displaystyle>\frac{1-\left(1-2\varepsilon_{\mathrm{small}}\right)^{(1-\lambda)k/2}}{2}.$
($\mathrm{error}_{\mathcal{D}}(f,\tilde{f}_{r_{i}})>\varepsilon_{\mathrm{small}}$
for $i\in A_{\leq r}$)

Since $h$ was arbitrary, this shows that $\mathrm{XOR}_{k}\circ f$ is
$\varepsilon_{\mathrm{large}}$-far from being a $\lambda rk$-junta. ∎

###### Proof of Theorem 5.

Theorem 4 is stated in the non-tolerant regime. However, we note that the same
theorem holds in the $(0,\varepsilon,r,r^{\prime})$-testing regime. That is,
under the conditions of Theorem 4, if $\mathcal{P}$ is
$(0,\varepsilon_{\mathrm{large}},s,s^{\prime})$-testable, then it is also
$(0,\varepsilon_{\mathrm{small}},s,\lambda^{-1}s^{\prime})$-testable. This is
because if $\tilde{f}$ is a $0$-approximator of $f$ over $\mathcal{D}$, then
$g\circ\tilde{f}$ is a $0$-approximator of $g\circ f$ over $\mathcal{D}^{k}$.

Lemma 8.3 shows that the property of being an $r$-junta admits an
$(\varepsilon_{\mathrm{small}},\frac{1-(1-2\varepsilon_{\mathrm{small}})^{{(1-\lambda)k}/{2}}}{2},\lambda)$-composition
theorem. Therefore, Theorem 4 shows that if juntas can be
$(0,\varepsilon_{\mathrm{large}},r,r^{\prime})$-tested in
$q(\varepsilon_{\mathrm{large}},r,r^{\prime})$ queries then they can be
$(\varepsilon_{\mathrm{small}},r,r^{\prime})$-tested in $k\cdot
q(\varepsilon_{\mathrm{large}},kr,kr^{\prime})$ queries where

$\varepsilon_{\mathrm{large}}=\frac{1-(1-2\varepsilon_{\mathrm{small}})^{{(1-\lambda)k}/{2}}}{2}.\qed$

####  8.2.3 Weak testers suffice for tolerant junta testing

######  Theorem 6 (Boosting tolerant junta testers, formal version of
Corollary 2.4).

If there is a $q(r)$-query tester that, given queries to $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ and random samples from a distribution $\mathcal{D}$,
distinguishes between

  * •

Yes: $f$ is $\frac{1}{4}$-close to an $r$-junta, and

  * •

No: $f$ is $\frac{1}{3}$-far from every $r$-junta,

then for every $\varepsilon>0$ and $\lambda\in(0,1)$, there is a
$\frac{q(r/(4\varepsilon))}{4\varepsilon}$-query algorithm that distinguishes
between

  * •

Yes: $f$ is $\varepsilon$-close to an $r$-junta, and

  * •

No: $f$ is $\Omega(\frac{\varepsilon}{1-\lambda})$-far from every
$\lambda^{-1}r$-junta.

###### Proof.

Let $\mathcal{T}$ be a $q(r)$-query tester for juntas that satisfies the
theorem statement. Given queries to a function $f:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ and random samples to $\mathcal{D}$, we design an algorithm for
$(\varepsilon,\frac{5}{1-\lambda}\varepsilon,r,\lambda^{-1}r)$-testing $f$
over $\mathcal{D}$. The algorithm is straightforward. We choose
$k=\frac{1}{4\varepsilon}$, and run the procedure in Figure 2 with
$g=\mathrm{XOR}_{k}:\\{\pm 1\\}^{k}\to\\{\pm 1\\}$ and junta size $kr$.

##### Query complexity.

$\mathcal{T}$ makes $q(kr)=q(\frac{r}{4\varepsilon})$ queries to the target
$\mathrm{XOR}_{k}\circ f:\\{\pm 1\\}^{nk}\to\\{\pm 1\\}$ before it terminates.
Our tester makes $k$ queries to $f$ for each query to $\mathrm{XOR}_{k}\circ
f$. Therefore, our tester makes $k\cdot
q(\frac{r}{4\varepsilon})=(\frac{r}{4\varepsilon})/(4\varepsilon)$ queries in
total.

##### Correctness.

For correctness, we need to show:

  * Yes case:

if $f$ is $\varepsilon$-close to being an $r$-junta over $\mathcal{D}$, then
$\mathrm{XOR}_{k}\circ f$ is $1/4$-close to being a $kr$-junta over
$\mathcal{D}^{k}$, and

  * No case:

if $f$ is $\frac{5\varepsilon}{1-\lambda}$-far from being an
$\lambda^{-1}r$-junta over $\mathcal{D}$, then $\mathrm{XOR}_{k}\circ f$ is
$\frac{1}{3}$-far from being a $kr$-junta over $\mathcal{D}^{k}$.

###### Yes case.

Let $\tilde{f}$ be an $r$-junta which $\varepsilon$-approximates $f$ over
$\mathcal{D}$. By a union bound:

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\left[\text{XOR}_{k}\circ
f(\bm{x})\neq\text{XOR}_{k}\circ\tilde{f}(\bm{x})\right]$
$\displaystyle\leq\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}^{k}}\left[\text{some
}f(\bm{x}^{(i)})\neq f(\bm{x}^{(i)})\right]$ $\displaystyle\leq
k\cdot\mathrm{error}_{\mathcal{D}}(f,\tilde{f})\leq k\varepsilon=\frac{1}{4}.$

Since $\mathrm{XOR}_{k}\circ\tilde{f}$ is a $kr$-junta, this shows that
$\mathrm{XOR}_{k}\circ f$ is $\frac{1}{4}$-close to a $kr$-junta.

###### No case.

If $f$ is $\frac{5\varepsilon}{(1-\lambda)}$-far from being a
$\lambda^{-1}r$-junta, then Lemma 8.3 implies that $\mathrm{XOR}_{k}\circ f$
is

$\frac{1-(1-2\varepsilon_{\mathrm{small}})^{(1-\lambda)k/2}}{2}$

far from being a $\lambda\lambda^{-1}kr=kr$-junta over $\mathcal{D}^{k}$ where
$\varepsilon_{\mathrm{small}}\coloneqq\frac{5\varepsilon}{(1-\lambda)}$.
Therefore, it is sufficient to show that
$\frac{1-(1-2\varepsilon_{\mathrm{small}})^{(1-\lambda)k/2}}{2}\geq\frac{1}{3}$.
We observe
$\frac{2}{(1-\lambda)k}\leq\log_{\frac{1}{3}}(e)\cdot\varepsilon_{\mathrm{small}}$
which implies $3^{-2/((1-\lambda)k)}\geq
e^{-2\varepsilon_{\mathrm{small}}}\geq 1-2\varepsilon_{\mathrm{small}}$. It
follows:

$\frac{1}{3}\geq(1-2\varepsilon_{\mathrm{small}})^{(1-\lambda)k/2}$

which provides the desired bound. ∎

####  8.2.4 Hardness of distribution-free tolerant junta testing

We prove the following which implies Corollary 2.5.

######  Theorem 7 (Tolerant junta testing hardness, formal version of
Corollary 2.5).

Given queries to a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and random
samples from a distribution $\mathcal{D}$, and $r\leq n$, it is NP-hard under
randomized reductions to distinguish between

  * •

Yes: $f$ is $0$-close an $r$-junta over $\mathcal{D}$, and

  * •

No: $f$ is $\frac{1}{3}$-far from every $\Omega(r\log n)$-junta over
$\mathcal{D}$.

We reduce from the SetCover problem.

######  Definition 14 (The SetCover problem).

A SetCover instance over a universe $[m]$ is a collection of subsets
$\mathcal{S}=\\{S_{1},\ldots,S_{n}\\}$ where $S_{i}\subseteq[m]$. The SetCover
problem is to compute a minimal size subcollection
$\\{S_{i_{1}},\ldots,S_{i_{r}}\\}$ which covers the universe:
$[m]=S_{i_{1}}\cup\cdots\cup S_{i_{r}}$.

SetCover is known to be hard to approximate.

######  Theorem 8 (Hardness of approximating SetCover [RS97]).

Given a SetCover instance $\mathcal{S}$ and a parameter $r$, it is NP-hard to
distinguish between

  * •

Yes: $\mathcal{S}$ has a size-$r$ set cover, and

  * •

No: $\mathcal{S}$ requires set covers of size $\Omega(r\log n)$.

###### Proof of Theorem 7.

Suppose we have an algorithm $\mathcal{T}_{\mathrm{weak}}$ for testing juntas
that can distinguish between the Yes and No cases in the theorem statement. In
particular, there is a $(0,\frac{1}{3},r,\Omega(r\log n))$-tester for juntas.
Theorem 5 implies that there is a
$(0,\varepsilon_{\mathrm{small}},r,\Omega(r\log n))$-tester,
$\mathcal{T}_{\mathrm{strong}}$, for juntas as long as
$\varepsilon_{\mathrm{small}}$ satisfies

$\frac{1}{3}\leq\frac{1-(1-2\varepsilon_{\mathrm{small}})^{(1-\lambda)k/2}}{2}.$
($\circledast$)

In the reduction, we will choose $\varepsilon_{\mathrm{small}}$ appropriately
and use this boosted tester to solve SetCover.

##### The reduction.

The reduction from SetCover to junta testing is standard [HJLT96, ABF+09]. We
will restate it here for convenience. Let
$\mathcal{S}=\\{S_{1},\ldots,S_{n}\\}$ be a SetCover instance over the
universe $[m]$ and define $u^{(1)},\ldots,u^{(m)}\in\\{\pm 1\\}^{n}$ where

$(u^{(j)})_{i}=\begin{cases}1&\text{if $j\in S_{i}$}\\\
-1&\text{otherwise.}\end{cases}$

Let $\mathcal{D}$ be the uniform distribution over
$\\{u^{(1)},\ldots,u^{(m)},(-1)^{n}\\}$ and let $f:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ be the function which is the disjunction of its inputs: $f\coloneqq
x_{1}\lor\cdots\lor x_{n}$ (where $1$ is interpreted as true and $-1$ as
false).

We choose $k=\Theta(m)$ so that $\circledast$ ‣ 8.2.4 holds with
$\Omega(\frac{1}{m})<\varepsilon_{\mathrm{small}}<\frac{1}{m+1}$. We then run
the boosted tester $\mathcal{T}_{\mathrm{strong}}$ on the function $f$ and
distribution $\mathcal{D}$, to test if $f$ is $0$-close to an $r$-junta or
$\varepsilon_{\mathrm{small}}$-far from being a $\Omega(r\log n)$-junta (where
the parameters $r$ and $\Omega(r\log n)$ correspond to the SetCover
parameters). Our algorithm for SetCover outputs Yes if and only if the tester
accepts $f$ as being $0$-close to an $r$-junta.

##### Runtime.

If the tester $\mathcal{T}_{\mathrm{weak}}$ runs in polynomial time, then
since $k=\Theta(m)$ and $\varepsilon_{\mathrm{small}}=\Theta(\frac{1}{m})$,
the tester $\mathcal{T}_{\mathrm{strong}}$ runs in polynomial time. Queries to
the target function $f$ and random samples from $\mathcal{D}$ can also be
simulated in randomized polynomial time.

##### Correctness.

For correctness, we need to show:

  * Yes case:

if $\mathcal{S}$ has a size-$r$ set cover, then $f$ is $0$-close to an
$r$-junta over $\mathcal{D}$, and

  * No case:

if $\mathcal{S}$ requires set covers of size $\Omega(r\log n)$, then $f$ is
$\varepsilon_{\mathrm{small}}$-far from being a $\Omega(k\log n)$-junta over
$\mathcal{D}$.

###### Yes case.

Let $S_{i_{1}},\ldots,S_{i_{r}}$ be a size-$r$ set cover. Consider the
function $\tilde{f}=x_{i_{1}}\lor\cdots\lor x_{i_{r}}$. Since these indices
form a set cover of $\mathcal{S}$, $\tilde{f}(u^{(i)})=1$ for all $i\in[m]$
and $\tilde{f}((-1)^{n})=-1$. This shows
$\mathrm{error}_{\mathcal{D}}(f,\tilde{f})=0$. It follows that $f$ is
$0$-close to an $r$-junta over $\mathcal{D}$ since $\tilde{f}$ is an
$r$-junta.

###### No case.

Suppose $\tilde{f}$ is an $r^{\prime}$-junta satisfying
$\mathrm{error}_{\mathcal{D}}(f,\tilde{f})<\frac{1}{m+1}$. The relevant
variables of $\tilde{f}$ must correspond to a set cover of $\mathcal{S}$: if
some element $i\in[m]$ is not covered, then
$\tilde{f}(u^{(i)})=\tilde{f}((-1)^{n})$ and
$\mathrm{error}_{\mathcal{D}}(f,\tilde{f})\geq\frac{1}{m+1}$. This shows if
$\mathcal{S}$ requires set covers of size $\Omega(r\log n)$ then $f$ is
$\frac{1}{m+1}$-far from every $\Omega(r\log n)$-junta. In particular, since
$\varepsilon_{\mathrm{small}}<\frac{1}{m+1}$, every $\Omega(r\log n)$-junta is
$\varepsilon_{\mathrm{small}}$-far from $f$. ∎

## Acknowledgments

We thank the FOCS reviewers for their helpful comments and feedback. The
authors are supported by NSF awards 1942123, 2211237, 2224246 and a Google
Research Scholar award. Caleb is also supported by an NDSEG fellowship, and
Carmen by a Stanford Computer Science Distinguished Fellowship.

## References

  * [ABF+09] Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toniann Pitassi.  The complexity of properly learning simple concept classes.  Journal of Computer & System Sciences, 74(1):16–34, 2009.
  * [ABR16] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld.  Learning and testing junta distributions.  In Conference on Learning Theory (COLT), pages 19–46, 2016.
  * [ABRW16] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf.  Efficient quantum algorithms for (gapped) group testing and junta testing.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 903–922. SIAM, 2016.
  * [AM10] Jan Arpe and Elchanan Mossel.  Application of a generalization of russo’s formula to learning from multiple random oracles.  Combinatorics, Probability and Computing, 19(2):183–199, 2010.
  * [AR07] Jan Arpe and Rüdiger Reischuk.  Learning juntas in the presence of noise.  Theoretical computer science, 384(1):2–21, 2007.
  * [AS07] Alp Atıcı and Rocco A Servedio.  Quantum algorithms for learning and testing juntas.  Quantum Information Processing, 6(5):323–348, 2007.
  * [BB19] Eric Blais and Joshua Brody.  Optimal Separation and Strong Direct Sum for Randomized Query Complexity.  In 34th Computational Complexity Conference (CCC), volume 137, pages 29:1–29:17, 2019.
  * [BCE+18] Eric Blais, Clément Canonne, Talya Eden, Amit Levi, and Dana Ron.  Tolerant junta testing and the connection to submodular optimization and function isomorphism.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2113–2132, 2018.
  * [Bel15] Aleksandrs Belovs.  Quantum algorithms for learning symmetric juntas via the adversary bound.  computational complexity, 24:255–293, 2015.
  * [Bel19] Aleksandrs Belovs.  Quantum algorithm for distribution-free junta testing.  In Proceedings of the 14th International Computer Science Symposium in Russia (CSR), pages 50–59. Springer, 2019.
  * [BGSMdW13] Harry Buhrman, David Garcıa-Soriano, Arie Matsliah, and Ronald de Wolf.  The non-adaptive query complexity of testing k-parities.  Chicago Journal of Theoretical Computer Science, 6:1–11, 2013.
  * [BHL95] Avrim Blum, Lisa Hellerstein, and Nick Littlestone.  Learning in the presence of finitely or infinitely many irrelevant attributes.  Journal of Computer and System Sciences, 50(1):32–40, 1995.
  * [BKLS20] Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu.  A strong XOR lemma for randomized query complexity.  arXiv preprint arXiv:2007.05580, 2020.
  * [BKT18] Mark Bun, Robin Kothari, and Justin Thaler.  The polynomial method strikes back: Tight quantum query bounds via dual polynomials.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 297–310, 2018.
  * [BL97] Avrim Blum and Pat Langley.  Selection of relevant features and examples in machine learning.  Artificial Intelligence, 97(1-2):245–271, 1997.
  * [Bla08] Eric Blais.  Improved bounds for testing juntas.  In Proceedings of the 12th Intl. Workshop on Randomization and Computation (RANDOM), pages 317–330. Springer, 2008.
  * [Bla09] Eric Blais.  Testing juntas nearly optimally.  In Proceedings of the 41st Annual ACM Symposium on Theory of computing (STOC), pages 151–158, 2009.
  * [Bla10] Eric Blais.  Testing juntas: A brief survey.  Property testing, 6390:32–40, 2010.
  * [Bla16] Eric Blais.  Testing juntas and related properties of boolean functions.  In Encyclopedia of Algorithms, pages 2222–2226. 2016.
  * [Blu94] Avrim Blum.  Relevant examples and relevant features: Thoughts from computational learning theory.  In AAAI Fall Symposium on ‘Relevance, volume 5, page 1, 1994.
  * [Blu03] Avrim Blum.  Learning a function of $r$ relevant variables.  In Proceedings of the 16th Annual Conference on Learning Theory, pages 731–733, 2003.
  * [Bsh19] Nader H Bshouty.  Almost optimal distribution-free junta testing.  In 34th Computational Complexity Conference (CCC), 2019.
  * [CG04] Hana Chockler and Dan Gutfreund.  A lower bound for testing juntas.  Information Processing Letters, 90(6):301–305, 2004.
  * [CGSM11] Sourav Chakraborty, David García-Soriano, and Arie Matsliah.  Efficient sample extractors for juntas with applications.  In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pages 545–556. Springer, 2011.
  * [CJLW21] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  Learning and testing junta distributions with sub cube conditioning.  In Conference on Learning Theory (COLT), pages 1060–1113, 2021\.
  * [CNY23] Thomas Chen, Shivam Nadimpalli, and Henry Yuen.  Testing and learning quantum juntas nearly optimally.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1163–1185, 2023.
  * [CP23] Xi Chen and Shyamal Patel.  New lower bounds for adaptive tolerant junta testing.  arXiv preprint arXiv:2304.10647, 2023.
  * [CST+18] Xi Chen, Rocco A Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie.  Settling the query complexity of non-adaptive junta testing.  Journal of the ACM (JACM), 65(6):1–18, 2018.
  * [DLM+07] Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, and Andrew Wan.  Testing for concise representations.  In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 549–558, 2007.
  * [DMN19] Anindya De, Elchanan Mossel, and Joe Neeman.  Junta correlation is testable.  In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1549–1563, 2019.
  * [Dru12] Andrew Drucker.  Improved direct product theorems for randomized query complexity.  computational complexity, 21(2):197–244, 2012.
  * [FKR+04] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky.  Testing juntas.  Journal of Computer and System Sciences, 68(4):753–787, 2004.
  * [GNW11] Oded Goldreich, Noam Nisan, and Avi Wigderson.  On yao’s xor-lemma.  Studies in Complexity and Cryptography, 6650:273–301, 2011.
  * [HJLT96] Thomas Hancock, Tao Jiang, Ming Li, and John Tromp.  Lower bounds on learning decision lists and trees.  Information and Computation, 126(2):114–122, 1996.
  * [Imp95] Russell Impagliazzo.  Hard-core distributions for somewhat hard problems.  In Proceedings of 36th Annual Foundations of Computer Science (FOCS), pages 538–545, 1995.
  * [ITW21] Vishnu Iyer, Avishay Tal, and Michael Whitmeyer.  Junta distance approximation with sub-exponential queries.  In Proceedings of the 36th Computational Complexity Conference (CCC), 2021.
  * [IW97] Russell Impagliazzo and Avi Wigderson.  $\mathrm{P}=\mathrm{BPP}$ if $\mathrm{E}$ requires exponential circuits: Derandomizing the xor lemma.  In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pages 220–229, 1997.
  * [JDP83] Kumar Joag-Dev and Frank Proschan.  Negative association of random variables with applications.  The Annals of Statistics, pages 286–295, 1983.
  * [KLM+09] Mihail N Kolountzakis, Richard J Lipton, Evangelos Markakis, Aranyak Mehta, and Nisheeth K Vishnoi.  On the Fourier spectrum of symmetric boolean functions.  Combinatorica, 29:363–387, 2009.
  * [KS03] Adam R Klivans and Rocco A Servedio.  Boosting and hard-core set construction.  Machine Learning, 51:217–238, 2003.
  * [LCS+18] Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie.  Distribution-free junta testing.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, page 749–759, New York, NY, USA, 2018. Association for Computing Machinery.
  * [Lev85] Leonid A Levin.  One-way functions and pseudorandom generators.  In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pages 363–365, 1985.
  * [LW19] Amit Levi and Erik Waingarten.  Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs.  In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019.
  * [MOS04] Elchanan Mossel, Ryan O’Donnell, and Rocco A. Servedio.  Learning functions of $k$ relevant variables.  Journal of Computer and System Sciences, 69(3):421–434, 2004.
  * [O’D02] Ryan O’Donnell.  Hardness amplification within np.  In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 751–760, 2002.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [PRS02] Michal Parnas, Dana Ron, and Alex Samorodnitsky.  Testing basic boolean formulae.  SIAM Journal on Discrete Mathematics, 16(1):20–46, 2002.
  * [PRW22] Ramesh Krishnan S Pallavoor, Sofya Raskhodnikova, and Erik Waingarten.  Approximating the distance to monotonicity of boolean functions.  Random Structures & Algorithms, 60(2):233–260, 2022.
  * [Ron10] Dana Ron.  Algorithmic and analysis techniques in property testing.  Foundations and Trends® in Theoretical Computer Science, 5(2):73–205, 2010.
  * [RS97] Ran Raz and Shmuel Safra.  A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP.  In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, page 475–484, New York, NY, USA, 1997. Association for Computing Machinery.
  * [Sağ18] Mert Sağlam.  Near log-convexity of measured heat in (discrete) time and consequences.  In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 967–978, 2018.
  * [Ser10] Rocco A Servedio.  Testing by implicit learning: A brief survey.  Property testing: current research and surveys, pages 197–210, 2010\.
  * [Sha04] Ronen Shaltiel.  Towards proving strong direct product theorems.  Computational Complexity, 12(1/2):1–22, 2004.
  * [ST11] Amir Shpilka and Avishay Tal.  On the minimal fourier degree of symmetric boolean functions.  In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 200–209. IEEE, 2011.
  * [STW15] Rocco A. Servedio, Li-Yang Tan, and John Wright.  Adaptivity helps for testing juntas.  In Proceedings of the 30th Conference on Computational Complexity, page 264–279, Dagstuhl, DEU, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [Val15] Gregory Valiant.  Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem.  Journal of the ACM (JACM), 62(2):1–45, 2015.
  * [Waj17] David Wajc.  Negative association: definition, properties, and applications.  Manuscript, available from https://goo. gl/j2ekqM, 2017.
  * [Yao82] Andrew C Yao.  Theory and application of trapdoor functions.  In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 80–91. IEEE, 1982.

##  Appendix A Counterexamples to natural composition theorems

###  A.1 Counterexample to Conjecture 1

######  Lemma A.1.

For any odd $k$ and $n\geq k$ let $R=(n-1)k$ and $\mathcal{D}$ be the uniform
distribution over $\\{\pm 1\\}^{n}$. There are symmetric functions $g:\\{\pm
1\\}^{k}\to\\{\pm 1\\}$ and $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ for which the
following holds.

  1. 1.

There is an $R$-junta $h$ achieving,

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ f,h)\leq O(1/\sqrt{k}).$

  2. 2.

The natural strategy of dividing the budget equally achieves,

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ f,g\circ\tilde{f}_{R/k})=1/2.$

We set $g=\textsc{Maj}_{k}$ to be the majority function on $k$ bits,

$g(y_{1},\ldots,y_{k})=\begin{cases}1&\text{if }\sum_{i\in[k]}y_{i}\geq 0\\\
-1&\text{otherwise}\end{cases}.$

and $f=\mathrm{XOR}_{n}$ to be the parity function,

$f(x_{1},\ldots,x_{n})=\prod_{i\in[n]}x_{i}.$

The following fact will be useful in giving a strategy that achieves low
error.

######  Fact A.2.

Let $\bm{y}_{1},\ldots,\bm{y}_{k-1}$ each be uniform and independent samples
from $\\{\pm 1\\}$. Then, for any choice of $c$,

$\operatorname{{Pr}}\left[\sum_{i\in[k-1]}\bm{y}_{i}=c\right]\leq
O\left(1/\sqrt{k}\right).$

We now give the junta achieving low error.

######  Proposition A.3 (Lemma A.1, there is a low error junta).

Let $h=\textsc{Maj}_{k-1}\circ\mathrm{XOR}_{n}$. Then,

  1. 1.

$h$ is an $((k-1)n\leq R)$-junta.

  2. 2.

$h$ achieves,

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ f,h)\leq O(1/\sqrt{k}).$

###### Proof.

Clearly $h$ depends on only the first $(k-1)n$ bits of its inputs, so it is an
$R$-junta as long as $(k-1)n\leq(n-1)k$, which is guaranteed by the assumption
$n\geq k$ in Lemma A.1. We compute $h$’s error,

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ
f,h)=\operatorname{{Pr}}_{\bm{y}\sim\\{\pm
1\\}^{n}}[\textsc{Maj}_{k}(\bm{y})\neq\textsc{Maj}_{k-1}(\bm{y})].$

In order for $\textsc{Maj}_{k}(\bm{y})\neq\textsc{Maj}_{k-1}(\bm{y})$, it must
be the case that the $\sum_{i\in[k-1]}\bm{y}_{i}$ is $-1$ or $0$. The desired
result follows from Fact A.2. ∎

We’ll next show the natural strategy achieves advantage $0$, equivalent to
error $1/2$.

######  Proposition A.4.

Let $f=\mathrm{XOR}_{n}$ and $\mathcal{D}$ be the uniform distribution over
$\\{\pm 1\\}^{n}$. Then,

$\mathrm{Adv}_{\mathcal{D}}(f,\tilde{f}_{n-1})=0.$

###### Proof.

By Proposition 6.10, it is sufficient to show that for any set $|S|=n-1$ and
any $x\in\\{\pm 1\\}^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}}[f(\bm{y})\mid\bm{y}_{S}=x_{S}]=0.$

For any fixed $x$, there are two $y\in\\{\pm 1\\}^{n}$ satisfying
$y_{S}=x_{S}$: The first choice if $y=x$, and the second choice is $x$ with a
single bit flipped (the one bit not in $S$). One of these two choices will
have a parity of $+1$ and one will have a parity of $-1$, so the average
parity is $0$, as desired. ∎

######  Proposition A.5.

For any odd $k$, $\mu=0$, and $\vec{\rho}=[0,\ldots,0]$,

$\mathrm{Stab}_{\mu,\vec{\rho}}(\textsc{Maj}_{k})=0.$

###### Proof.

For odd $k$, $\textsc{Maj}_{k}$ is an odd function,
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\\{\pm
1\\}^{n}}[\textsc{Maj}_{k}(\bm{x})]$. Then,

$\displaystyle\mathrm{Stab}_{\mu,\vec{\rho}}(\textsc{Maj}_{k})$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}_{1}\sim\\{\pm
1\\}^{k},\bm{x}_{2}\sim\\{\pm
1\\}^{k}}[\textsc{Maj}_{k}(\bm{x}_{1})\textsc{Maj}_{k}(\bm{x}_{2})]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}_{1}\sim\\{\pm
1\\}^{k}}[\textsc{Maj}_{k}(\bm{x}_{1})]\mathop{{\mathds{E}}\/}_{\bm{x}_{2}\sim\\{\pm
1\\}^{k}}[\textsc{Maj}_{k}(\bm{x}_{2})]$ ($\bm{x}_{1},\bm{x}_{2}$ independent)
$\displaystyle=0\cdot 0=0.$ ($\textsc{Maj}_{k}$ is odd)

∎

The following completes the proof of Lemma A.1.

######  Corollary A.6.

In the setting of Lemma A.1,

$\mathrm{Adv}_{\mathcal{D}^{k}}(g\circ f,g\circ\tilde{f}_{R/k})=0.$

###### Proof.

This follows from Theorem 3 and Propositions A.4 and A.5. ∎

###  A.2 Counterexample to Conjecture 2

######  Lemma A.7.

For any $n\geq 10$, $k\in\mathds{N}$, and $R\leq n/2$, let $\mathcal{D}$ be
uniform over $\\{\pm 1\\}^{n}$. There are $g:\\{\pm 1\\}^{k}$ and $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ for which, for all partitions $r_{1}+\cdots+r_{k}=R$,

$\mathrm{error}_{\mathcal{D}^{k}}(g\circ
f,g(\tilde{f}_{r_{1}},\ldots,\tilde{f}_{r_{k}}))\geq 1-2^{-\Omega(k)}.$

Lemma A.7 is particularly surprising in light of the fact that either the
constant $-1$ or constant $1$ functions, both of which are $0$-juntas, will
achieve error $\leq 1/2$ with respect to $g\circ f$. We begin with a
probabilistic construction of $f$ achieving the following.

######  Proposition A.8.

For any $n\geq 10$, there is an $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ for which
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\\{\pm 1\\}^{n}}[f(\bm{x})]\leq 0.5$ but,
for all $|S|\leq n/2$ and $x\in\\{\pm 1\\}^{n}$,

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\\{\pm
1\\}^{n}}[f(\bm{x})\mid\bm{x}=x]>0.$