DNF DNFs AC^0 TC^0 MAJ MUX NAE OR AND Tribes LocalCorrect sgn sparsity rank
span quasipoly Bias DTdepth DTsize PARITY Dict Corr avg smooth dist ETH

# Junta Distance Approximation with Sub-Exponential Queries

Vishnu Iyer UC Berkeley. Email<EMAIL_ADDRESS>Avishay Tal UC
Berkeley. Email<EMAIL_ADDRESS>Michael Whitmeyer UC Berkeley. Email:
<EMAIL_ADDRESS>
###### Abstract

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different
results pertaining to the _tolerant testing_ of juntas. Given black-box access
to a Boolean function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$:

  1. 1.

We give a $\poly(k,\frac{1}{\varepsilon})$ query algorithm that distinguishes
between functions that are $\gamma$-close to $k$-juntas and
$(\gamma+\varepsilon)$-far from $k^{\prime}$-juntas, where
$k^{\prime}=O(\frac{k}{\varepsilon^{2}})$.

  2. 2.

In the non-relaxed setting, we extend our ideas to give a
$2^{\widetilde{O}(\sqrt{k/\varepsilon})}$ (adaptive) query algorithm that
distinguishes between functions that are $\gamma$-close to $k$-juntas and
$(\gamma+\varepsilon)$-far from $k$-juntas. To the best of our knowledge, this
is the first subexponential-in-$k$ query algorithm for approximating the
distance of $f$ to being a $k$-junta (previous results of Blais, Canonne,
Eden, Levi, and Ron [SODA, 2018] and De, Mossel, and Neeman [FOCS, 2019]
required exponentially many queries in $k$).

Our techniques are Fourier analytical and make use of the notion of
“normalized influences” that was introduced by Talagrand [Tal94].

##  1 Introduction

The study of property testing, initiated by Blum, Luby, and Rubinfeld in their
seminal work on linearity testing [BLR90], is concerned with making fast
decisions about a global object having some global property, while only
accessing (or querying) parts of it. This notion was further explored by
Goldreich, Goldwasser, and Ron [GGR96], who drew connections to the areas of
learning theory and approximation algorithms in the context of graph
properties. We focus on properties of Boolean functions, i.e., $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$. First, we state the definition of a property testing
algorithm $\mathcal{A}$. Given $\varepsilon>0$ and a class of functions
$\mathcal{C}$, we say that $\mathcal{A}$ is a property tester for
$\mathcal{C}$ if it satisfies the following two conditions:

  1. 1.

if $f\in\mathcal{C}$, then $\mathcal{A}$ accepts $f$ with probability at least
$2/3$;

  2. 2.

if $\dist(f,g)\geq\varepsilon$ for all $g\in\mathcal{C}$, then $\mathcal{A}$
rejects with probability at least $2/3$.

In the above definition, $\dist(f,g)=\mathop{\bf Pr\/}[f(x)\neq g(x)]$ is the
fraction of inputs on which $f$ and $g$ disagree under the uniform
distribution. The primary measure of efficiency for such property testing
algorithms is the algorithms query complexity, or the number of times it must
use its black box access to $f$. Such query algorithms can be adaptive in that
the coordinates on which they query $f$ depend on previous answers, or they
can be nonadaptive in that the algorithm always queries $f$ in a predetermined
manner.

In this writeup, our algorithms will be adaptive, and we will focus on testing
the particular class of functions known as $k$-juntas. Juntas comprise a
simple and natural class of functions: those that depend only on a smaller
subset of their input variables. More precisely, a Boolean function $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ is said to be a $k$-junta if there exists $k$
coordinates $i_{1},\ldots,i_{k}\in[n]$ such that $f(x)$ only depends on
$x_{i_{1}},\ldots,x_{i_{k}}$. In essence, juntas capture the existence of many
irrelevant variables, and arise naturally in the context of feature selection
in machine learning and many computational biology problems. A canonical
example is the problem of determining the relationship between genes and
phenotypes; for example, one might wish to test whether a particular physical
trait is a function of many genes or only a small number.

The fundamental problem of learning and/or testing juntas has been given much
attention in recent years. We refer the reader to the works of Mossel,
O’Donnell, and Servedio [MOS03] and Valiant [Val12] for the most recent work
on learning $k$-juntas. In this paper, we focus on the problem of testing
juntas. Testing $1$-juntas (aka dictators) and related functions had initial
theoretical interest in the context of long-code testing in PCPs [Hås01,
BGS98], and was first formally explored in [PRS01], which gave algorithms for
testing dictators, monomials, and monotone DNFs. The more general problem of
testing $k$-juntas was first studied by Fischer et. al. [Fis+04], where they
exhibited a $k$-junta tester with query complexity $\widetilde{O}(k^{2})$
queries to $f$. Crucially, their upper bound lacked any dependence on the
ambient dimension $n$. More recently, it was shown in [Bla09] that $O(k\log
k+k/\varepsilon)$ adaptive queries suffice to test $k$-juntas, and this is
tight for constant $\varepsilon$ [Sag18, CG04]. There has also been recent
interest in the distribution free setting for junta testing (wherein the
distribution on inputs is not assumed to be uniform). Liu et al. [Liu+19]
initially gave a $\widetilde{O}(k^{2}/\varepsilon)$-query algorithm with one-
sided error, which was quickly followed up by the works of Bshouty [Bsh19] and
Zhang [Zha19] who gave $\widetilde{O}(k/\varepsilon)$-query algorithms with
two-sided and one-sided error, respectively. The methods utilized by Bshouty
extend those of Diakonikolas et al. [Dia+07] and result in algorithms not only
for junta testing but also several subclasses of juntas. We note that while we
solve a similar problem in a different setting, some of our techniques
resemble those of [Bsh19]: notably, an idea introduced in [Bsh19] is to find a
witness such that, if all coordinates outside a subset of the coordinates are
fixed to this witness’ values, then $f$ becomes a dictator on a single
coordinate within that subset. This can be thought of as obtaining oracle
access to a relevant coordinate, an idea pervasive throughout the work of
[DMN19] and ours. The techniques in [Dia+07, Dia+08, Bsh19] can all be
categorized in the “testing via implicit learning” paradigm, as surveyed in
[Ser10].

###  1.1 Tolerant Junta Testing

One of the first relaxations of the standard property testing model considered
(sometimes referred to as the “parameterized” regime) were testers that
distinguished between $f\in H$ and $f$ being $\varepsilon$-far from
$H^{\prime}\supseteq H$. This notion was introduced by Kearns and Ron [KR00]
in the context of testing decision trees and certain classes of neural
networks. We note that if $H^{\prime}$ is a strict superset of $H$, then the
job of the tester becomes easier, and smaller query or sample complexity is
often achievable than in the regular testing model. Indeed, our Theorem 1.3 is
an example of a (tolerant) parameterized tester. Tolerant testing is another
generalization of the standard property testing model. The notion was first
introduced by Parnas, Ron, and Rubinfeld [PRR04]. Normal property testing
entails distinguishing between functions that exactly satisfy a certain
property, and functions that are $\varepsilon$-far from satisfying said
property. This is somewhat restrictive, and the tolerant testing problem seeks
to more generally distinguish functions that are $c_{\ell}$ close to having
the desired property, and those that are at least $c_{u}$ far from having the
property, for some $0<c_{\ell}<c_{u}<1$. We also note that the notion of
tolerant testing is closely related to the notion of distance approximation –
indeed, if one can estimate $\dist(f,\mathcal{C})$ up to additive error
$(c_{u}-c_{\ell})/2$ with probability at least $2/3$, then one has solved the
tolerant testing problem for that class.111The reverse direction is also true
– given a tolerant tester it is possible to estimate the distance to that
property. See for example section 3 in [Ail+07]. In general, tolerant testing
(and therefore distance approximation), is much more challenging than
traditional property testing. Figure 1 provides a visualization of the
tolerant testing problem. Tolerant testing has received a lot of attention
recently, see for example [BLT20] for work on tolerant testing of decision
trees and [Ail+07] [PRW20] for work on tolerant testing of monotonicity. For
the case of $k$-juntas, we have the following (relaxed) definition of a
tolerant tester. In the following we denote by $\mathcal{J}_{n,k}$ the class
of $k$-juntas, and for a class of functions $\mathcal{C}$, we denote
$\dist(f,\mathcal{C}):=\min_{g\in\mathcal{C}}\dist(f,g)$.

######  Definition 1.1.

For constants $0<c_{\ell}<c_{u}<1/2$ and a given $k^{\prime},k\in\mathbb{N}$
with $k^{\prime}\geq k$, a _$(k,k^{\prime},c_{\ell},c_{u})$ tolerant junta
tester_ is an algorithm that, given oracle access to $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$,

  1. 1.

if $\dist(f,\mathcal{J}_{n,k})\leq c_{\ell}$ accepts with probability $2/3$;

  2. 2.

if $\dist(f,\mathcal{J}_{n,k^{\prime}})\geq c_{u}$ rejects with probability
$2/3$.

$\Pi$$c_{u}$$c_{\ell}$ Figure 1: A visualization of the tolerant property
testing paradigm. Assuming the outermost oval represents all functions
$f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and the property at hand is represented by a
class of functions $\Pi$, the goal is to distinguish between the light grey
(at most $c_{\ell}$ close to a function in $\Pi$) and the dark grey (at least
$c_{u}$ far from all functions in $\Pi$) regions.

Our definition incorporates both tolerant and parameterized testers; when
$c_{\ell}=0$ the tester is non-tolerant and when $k^{\prime}=k$ the tester is
non-parameterized. We note that in the above definition we upper bound
$c_{u}<1/2$ since $k$-juntas are closed under complements, meaning if
$g\in\mathcal{J}_{n,k}$, then $-g\in\mathcal{J}_{n,k}$. Parnas, Ron, and
Rubinfeld in their seminal work [PRR04] showed that while standard property
testers, when querying uniformly, are weakly tolerant, entirely new algorithms
are usually needed to tolerant test with better parameters. Tolerant junta
testing was first considered by Diakonikolas et al. [Dia+07] which used the
aforementioned observation from [PRR04] to show that a standard tester from
[Fis+04] actually gave a $(k,k,\poly(\frac{\gamma}{k}),\gamma)$ tolerant
tester. Chakraborty et al. [Cha+12] subsequently showed that a similar
analysis to that of Blais [Bla09] gave a $(k,k,\gamma/C,\gamma)$ tolerant
junta tester (for some constant $C$) using $\exp(k/\gamma)$ queries.

More recently, Blais et al. [Bla+19, Theorem 1.2] showed a tradeoff between
query complexity and the amount of tolerance. In particular, they gave an
algorithm which, given $k$, $\gamma$, and $\rho\in(0,1)$, is a
$(k,k,\rho\gamma/16,\gamma)$ tolerant junta tester. The query complexity of
the algorithm is $O\\!\left(\frac{k\log k}{\gamma\rho(1-\rho)^{k}}\right)$. In
particular, note that when $\rho$ is a constant bounded away from zero, this
yields an $\exp(k)$ query algorithm, but when $\rho=1/k$ this yields a
$\poly(k)$ query algorithm. We also note that there is an undesirable
multiplicative gap between $c_{u}$ and $c_{\ell}$ that precludes one from
tolerantly testing for arbitrary close values of $c_{u}$ and $c_{\ell}$ (i.e.,
in [Bla+19], $c_{u}\geq 16c_{\ell}$ for all choices of $\rho$). The recent
work of [DMN19] addressed this, giving an algorithm for any arbitrary
$\gamma,\varepsilon>0$ that required $2^{k}\poly(k,\frac{1}{\varepsilon})$
queries and was a $(k,k,\gamma,\gamma+\varepsilon)$ tolerant junta tester.

In the relaxed setting (when $k^{\prime}\neq k$), [Bla+19, Theorem 1.1] also
gave an algorithm which used $\poly(k,\frac{1}{\gamma})$ queries to $f$ and
was a $(k,4k,\gamma/16,\gamma)$ tolerant junta tester. This once again posed
the issue of not allowing for arbitrary $c_{u}$ and $c_{\ell}$ values, which
was resolved by [DMN19, Corollary 1.6], which gave a
$(k,O(k^{2}/\varepsilon^{2}),\gamma,\gamma+\varepsilon)$ tolerant junta tester
with query complexity $\poly(k,\frac{1}{\varepsilon})$.

It is interesting to note that the techniques used to obtain the results from
[Bla+19] and [DMN19] are actually quite different, and yield results that are
qualitatively similar but quantitatively incomparable. The results from
[Bla+19] extend the techniques of [Bla09], which partition the $n$ input
coordinates into $\poly(k)$ disjoint sets or parts. It is immediate that any
$k$-junta is a $k$-part junta, but in [Bla09] it was shown that with high
probability a function that is far from being a $k$-junta is also far from
being a $k$-part junta (for a definition of this and more details we refer the
reader to [Bla09]). The results of [Bla+19] extend the idea of considering the
relationship between $k$-juntas and $k$-part juntas in the context of tolerant
testing.

The techniques in [DMN19] suggest a new way of attacking the problem of
tolerant $k$-junta testing. The core idea in [DMN19] was to get access to
oracles to coordinates of $f$ which have large low-degree influence. These
_coordinate oracles_ are obtained with high probability via a combination of
random restrictions and noise operators to the original function, and once
obtained, can be used to search, in a brute force manner, for the nearest
$k$-junta.

In terms of lower bounds for tolerant testing of juntas, two recent works
addressed the non-adaptive case. Levi and Waingarten [LW19] demonstrated that
there exists $0<\varepsilon_{1}<\varepsilon_{2}<1/2$ such that any
$(k,k,\varepsilon_{1},\varepsilon_{2})$ tolerant junta tester requires
$\widetilde{\Omega}(k^{2})$ non-adaptive queries to $f$. In particular, this
result demonstrated that the tolerant testing regime is quantitatively harder
than the standard testing regime, in which a $\widetilde{O}(k^{3/2})$-query
non-adaptive query algorithm is known [Bla08] (and indeed optimal due to
[Che+18]). Subsequently, Pallavoor, Raskhodnikova, and Waingarten [PRW20]
demonstrated that for any $k\leq n/2$ there exists
$0<\varepsilon_{1}<\varepsilon_{2}<1/2$ (with
$\varepsilon_{1}=O(1/k^{1-\eta})$ and $\varepsilon_{2}=\Omega(1/\sqrt{k})$)
such that every nonadaptive $(k,k,\varepsilon_{1},\varepsilon_{2})$-tolerant
junta tester requires at least $2^{k^{\eta}}$ queries to $f$, for any
$0<\eta<1/2$.222We note that this lower bound does not necessarily rule out
$\poly(k)\exp(1/\varepsilon)$ nonadaptive query
$(k,k,\varepsilon_{1},\varepsilon_{2})$ (where
$\varepsilon=\varepsilon_{2}-\varepsilon_{1}$) tolerant junta testers due to
the setting of $\varepsilon_{1}$ and $\varepsilon_{2}$ in their hard instance.

###  1.2 Our Results

Our first result is a subexponential-in-$k$ query tolerant junta tester in the
standard (non-relaxed) setting. In fact, we obtain an $\varepsilon$-accurate
estimate of the distance of $f$ to the class of $k$-juntas.

######  Theorem 1.2.

Given a Boolean function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, it is possible to
estimate the distance of $f$ from the class of $k$-juntas to within additive
error $\varepsilon$ with probability $2/3$ using
$2^{\widetilde{O}(\sqrt{k/\varepsilon})}$ adaptive queries to $f$. In
particular, when $\varepsilon$ is constant, this yields a
$2^{\widetilde{O}(\sqrt{k})}$-query algorithm. However, the algorithm still
requires $\exp(k/\varepsilon)$ time.

A simple corollary of the above theorem is that for any
$0<c_{\ell}<c_{u}<1/2$, we have a $(c_{u},c_{\ell},k,k)$ tolerant junta tester
with the same query complexity as in Theorem 1.2, where
$\varepsilon=(c_{u}-c_{\ell})/2$. This is an improvement of the results of
[DMN19, Bla+19], whose tolerant junta testers when $k^{\prime}=k$ required
exponential query complexity in $k$ in the worst case. We note that although
we obtain this improvement, our algorithm still requires $\exp(k)$ time. In
the appendix, we show a result solving a similar problem333In particular, this
problem is the problem of finding the subset of $k$ inputs that “contain” the
most Fourier mass – see Section 2 and Theorem 5.10 for more details. with an
improved dependence on $\varepsilon$, giving an algorithm requiring only
$2^{\widetilde{O}(\sqrt{k}\log(1/\varepsilon))}$-queries and
$\exp(k\log(1/\varepsilon))$ time (see Theorem 5.10).

In the relaxed/parameterized setting when $k^{\prime}\neq k$, we give a
polynomial-in-$k$ query tolerant junta tester that is valid for any setting of
$c_{u}$ and $c_{\ell}$, and reduces $k^{\prime}$ dependence on $k$ to be
linear instead of quadratic due to the result of [DMN19, Corollary 1.6].

######  Theorem 1.3.

For any $\gamma,\varepsilon>0$ and $k\in\mathbb{N}$, there is an algorithm
with query complexity $\poly(k,1/\varepsilon)$ that is a
$(k,O(k/\varepsilon^{2}),\gamma,\gamma+\varepsilon)$-tolerant junta tester.

Theorem 1.3 is a simple corollary of the following theorem we prove.

######  Theorem 1.4.

Let $\varepsilon>0$, $k\in\mathbb{N}$, and $k^{\prime}=O(k/\varepsilon^{2})$.
Then, there exists an algorithm that given parameters $k,\varepsilon$ and
oracle access to $f$ makes at most $poly(k,1/\varepsilon)$ queries to $f$ and
returns a number $\alpha$ such that with high probability (at least $0.99$)

  1. 1.

$\alpha\leq\dist(f,\mathcal{J}_{n,k})+\varepsilon$

  2. 2.

$\alpha\geq\dist(f,\mathcal{J}_{n,k^{\prime}})-\varepsilon$

Indeed, to solve the problem in Theorem 1.3 we can apply the algorithm from
Theorem 1.4 with $\varepsilon=(c_{u}-c_{\ell})/3$ and accept if and only if
$\alpha<\frac{1}{2}(c_{u}+c_{\ell})$. If $\dist(f,\mathcal{J}_{n,k})\leq
c_{\ell}$ we have that with high probability $\alpha\leq
c_{\ell}+\varepsilon<\frac{1}{2}(c_{u}+c_{\ell})$ and we will accept. On the
other hand, if $\dist(f,\mathcal{J}_{n,k^{\prime}})\geq c_{u}$ we have that
with high probability $\alpha\geq
c_{u}-\varepsilon>\frac{1}{2}(c_{u}+c_{\ell})$ and we will reject.

Both of the algorithms used to prove Theorem 1.2 and Theorem 1.4 rely on the
fact that we can get approximate oracle access to influential coordinates of
$f$ using techniques from [DMN19]. From there, we analyze the Fourier
coefficients of $f$ after a series of random restrictions in order gain more
information about the relevant coordinates of $f$ at different Fourier levels.
Along the way, we give an algorithm which provides us with oracle access to a
junta in the following sense:444A similar technique appeared in [DMN19,
Section 5.1] to sample two inputs on which the coordinate oracles agree. We
note that our algorithm allows to specify the values the coordinate oracles
attain.

######  Theorem 1.5 (Informal).

Let $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
$\mathcal{D}=\\{g_{1},\ldots,g_{k^{\prime}}\\}$ be a set of functions giving
oracle access to a certain set of coordinates. Let $g$ be a function from
$\\{\pm 1\\}^{k^{\prime}}\to[-1,1]$ defined by $g(x)=\mathop{\bf
E\/}[f(y)|g_{1}(y)=x_{1},\ldots,g_{k^{\prime}}(y)=x_{k^{\prime}}]$. Then $g$
can be computed by a randomized algorithm that runs in expected time
$\poly(k^{\prime})$.

We note that one can view this as an oracle access to the junta, without even
figuring out the coordinates on which the junta depends. More details on the
ideas behind both algorithms can be found in Section 3.

###  1.3 Structure of this Paper

Section 2 surveys some necessary preliminaries. Section 3 gives high level
overviews of the techniques and ideas that go into the proofs of Theorem 1.4
and Theorem 1.2. Section 4 first describes how to get obtain “oracle access”
to a junta (see Theorem 1.5) using only oracles for relevant coordinates of
the junta, and then provides all the details of the algorithm and proof for
Theorem 1.4. Finally, Section 5 provides all the details of the algorithm and
proof for Theorem 1.2.

##  2 Preliminaries

Throughout the paper we adopt certain notation conventions. For a positive
integer $n$, we denote by $[n]$ the set $\\{1,\ldots,n\\}$. For a distribution
$\mathcal{D}$, we denote that a random variable $x$ is sampled according to
$\mathcal{D}$ by $x\sim\mathcal{D}$. In the case that $x$ is sampled uniformly
at random from a set $S$, we will abuse notation slightly and write $x\sim S$.
The binomial distribution with $n$ trials and probability $p$ per trial will
be denoted $\textrm{Bin}(n,p)$. We denote the set $\\{-1,1\\}$ with the
shorthand $\\{\pm 1\\}$. For functions $f,g$ from $\\{\pm 1\\}^{n}$ to $\\{\pm
1\\}$ we define $\dist(f,g)=\mathop{\bf Pr\/}_{x\sim\\{\pm 1\\}^{n}}[f(x)\neq
g(x)]$: that is, the fraction of inputs on which $f$ and $g$ differ. For a set
$S\subseteq[n]$ we will denote by $\\{\pm 1\\}^{S}$ the set of possible
assignments to the variables $\\{x_{i}\\}_{i\in S}$.

###  2.1 Probability

We recall the following Chernoff/Hoeffding bounds.

######  Fact 2.1.

If $X_{1},\ldots,X_{N}$ are independent random variables bounded in $[0,1]$
and $\bar{X}:=\frac{1}{N}\sum_{i=1}^{N}X_{i}$, then we have

$\mathop{\bf Pr\/}[|\bar{X}-\mathop{\bf E\/}[\bar{X}]|\geq\eta]\leq
2\exp(-2N\eta^{2}),$

Furthermore, denoting by $p=\mathop{\bf E\/}[\bar{X}]$, we have

$\mathop{\bf Pr\/}[\bar{X}\leq p-\eta]\leq\exp(-2N\eta^{2}),$ $\mathop{\bf
Pr\/}[\bar{X}\leq(1-\eta)p]\leq\left(\frac{e^{-\eta}}{(1-\eta)^{1-\eta}}\right)^{pN}\leq\exp\\!\left(-\dfrac{\eta^{2}pN}{2}\right).$

###  2.2 Boolean Functions

In this section we recall some tools in the analysis of Boolean functions. For
a more thorough introduction to the field, we refer the reader to [ODo14].

For every subset $S\subseteq[n]$, we define the parity function on the bits in
$S$, denoted by $\chi_{S}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ as
$\chi_{S}(x)=\prod_{i\in S}x_{i}$. It is a well-known fact that we can express
uniquely any $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ as a linear combination of
$\\{\chi_{S}\\}_{S\subseteq[n]}$:

$f(x)=\sum_{S\subseteq[n]}\widehat{f}(S)\chi_{S}(x).$

The coefficients $\\{\widehat{f}(S)\\}_{S\subseteq[n]}$ are referred to as the
Fourier coefficients of $f$, and can be calculated by
$\widehat{f}(S)=\mathop{\bf E\/}[f(x)\chi_{S}(x)]$. We say Fourier
coefficients are on level $s$ if they correspond to subsets of size $s$.

Given a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and a coordinate $i\in[n]$,
we define the _influence_ of the $i$-th coordinate on $f$ to be

${\mathbf{Inf}}_{i}[f]=\mathop{\bf Pr\/}_{x\sim\\{\pm 1\\}^{n}}[f(x)\neq
f(x^{i})].$

It is a well-known fact (see, e.g., [ODo14, Theorem 2.20]) that
${\mathbf{Inf}}_{i}[f]=\sum_{S\ni i}\widehat{f}(S)^{2}$. The latter definition
naturally extends to functions $f:\\{\pm 1\\}^{n}\to\mathbb{R}$. We naturally
extend this notion and define the _low-degree influence_ (up to level $k$) of
coordinate $i$ on $f$ as

${\mathbf{Inf}}_{i}^{\leq k}[f]=\sum_{S\ni i,|S|\leq k}\widehat{f}(S)^{2}.$

For a set $T\subseteq[n]$ we define the projection of the function $f$ to $T$,
denoted $f^{\subseteq T}$, as the partial Fourier expansion restricted to sets
contained in $T$, i.e., $f^{\subseteq T}(x)=\sum_{S:S\subseteq
T}\widehat{f}(S)\chi_{S}(x)$. We observe that $f^{\subseteq T}$ depends only
on coordinates in $T$ and that it can be alternatively defined as
$f^{\subseteq T}(x)=\mathop{\bf E\/}_{y\sim\\{\pm
1\\}^{n}}[f(y)|y_{T}=x_{T}]$. As suggested by the last identity, we also
denote $f^{\subseteq T}$ by $f_{\avg,T}$.

In the regime of property testing, we will need a notion of “closeness” of
functions.

######  Definition 2.2.

For functions $f,g:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and a set of functions $G$,
all from $\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ we say that

  1. 1.

$f$ is _$\nu$ -close_ to $g$ if $\dist(f,g)\leq\nu$;

  2. 2.

$f$ is $\nu$-close to $G$ if $\min_{g\in G}\dist(f,g)\leq\nu$;

  3. 3.

$f$ and $g$ are $c$-correlated if $\mathop{\bf E\/}_{x\in\\{\pm
1\\}^{n}}[f(x)g(x)]=c$;

  4. 4.

$f$ and $G$ are $c$-correlated (denoted $\mathsf{corr}(f,G)=c$) if $\max_{g\in
G}\mathop{\bf E\/}_{x\in\\{\pm 1\\}^{n}}[f(x)g(x)]=c$.

In the paper, we will occasionally abbreviate the correlation between $f$ and
$g$ as $\mathop{\bf E\/}[fg]$ when the domain is implied. Observe that when
$f$ and $g$ are Boolean-valued (in $\pm 1$) we have $\mathop{\bf
E\/}[fg]=1-2\dist(f,g)$.

######  Fact 2.3.

For functions $f,g:\\{\pm 1\\}^{n}\to\mathbb{R}$, we have Plancheral’s
identity:

$\mathop{\bf E\/}_{x\sim\\{\pm
1\\}^{n}}[f(x)g(x)]=\sum_{S\subseteq[n]}\widehat{f}(S)\widehat{g}(S)\;.$

When $f=g$, this fact is known as Parseval’s identity.

######  Definition 2.4.

For a function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ we define:

$\mathbf{W}^{\leq k}[f]=\sum_{|S|\leq k}\widehat{f}(S)^{2}\;.$

The definitions of $\mathbf{W}^{\geq k}[f]$, $\mathbf{W}^{=k}[f]$, and similar
follow from a natural extension. Now, we define some classes of Boolean
functions with properties that will be useful to us.

######  Definition 2.5 (Junta).

Let $T\subseteq[n]$. A function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ is called a
_junta_ on $T$ if $f$ depends only on coordinates in $T$. I.e., there exists a
function $g:\\{\pm 1\\}^{T}\to\mathbb{R}$ such that $f(x)=g(x_{T})$. A
function is called a  _$k$ -junta_ if it is a junta on $T$ for some
$T\subseteq[n]$ of size $k$. Following the notation of [DMN19], we denote the
class of $k$-juntas on $n$ inputs as $\mathcal{J}_{n,k}$. We also denote
$\mathcal{J}_{U,k}$ as the set of $k$-juntas with inputs inside of $U$, and
when $|U|=k$ then we often denote $\mathcal{J}_{U}:=\mathcal{J}_{U,k}$ for
brevity.

######  Definition 2.6 (Dictator, Anti-Dictator).

The $i$-th dictator function is given by $\Dict_{i}(x)=x_{i}$, for $x\in\\{\pm
1\\}^{n}$. The $i$-th antidictator function is simply the negation
$-\Dict_{i}(x)$.

######  Claim 2.7 (Nearest $k$-junta on a Subset).

For a function $f:\\{\pm 1\\}^{n}\to[-1,1]$ and a subset $T\subseteq[n]$, the
Boolean-valued junta-on-$T$ most correlated with $f$ is given by

$\sgn(f_{\avg,T}(x))=\sgn\left(\mathop{\bf E\/}_{y\in\\{\pm
1\\}^{n}}[f(y)|y_{T}=x_{T}]\right).$

Furthermore, the correlation between $f$ and $\sgn(f_{\avg,T}(x))$ is simply
$\mathop{\bf E\/}_{x\sim\\{\pm 1\\}^{n}}[|f_{\avg,T}(x)|]$.

We keep the proof for this well-known claim for completeness.

###### Proof.

Let $g:\\{\pm 1\\}^{n}\to[-1,1]$ be any junta-on-$T$. It suffices to show that
$\mathop{\bf E\/}_{x}[f(x)g(x)]\leq\mathop{\bf E\/}[f(x)\sgn(f_{\avg,T}(x))]$,
as we do next. Indeed, for any $g(x)$ that is a junta-on-$T$ we have
$g(x)=g^{\prime}(x_{T})$ for some $g^{\prime}:\\{\pm 1\\}^{T}\to[-1,1]$. Thus,
we have

$\displaystyle\mathop{\bf E\/}_{x\sim\\{\pm 1\\}^{n}}[f(x)g(x)]$
$\displaystyle=\mathop{\bf E\/}_{x\sim\\{\pm 1\\}^{n}}[f(x)g^{\prime}(x_{T})]$
$\displaystyle=\mathop{\bf E\/}_{x\sim\\{\pm
1\\}^{n}}\left[g^{\prime}(x_{T})\cdot\mathop{\bf E\/}_{y\sim\\{\pm
1\\}^{n}}[f(y)|x_{T}=y_{T}]\right]$ $\displaystyle=\mathop{\bf
E\/}_{x\sim\\{\pm 1\\}^{n}}[g^{\prime}(x_{T})f_{\avg,T}(x)]$
$\displaystyle\leq\mathop{\bf E\/}_{x\sim\\{\pm 1\\}^{n}}[|f_{\avg,T}(x)|]$
$\displaystyle=\mathop{\bf E\/}_{x\sim\\{\pm
1\\}^{n}}[\sgn(f_{\avg,T}(x))\cdot f_{\avg,T}(x)]$ $\displaystyle=\mathop{\bf
E\/}_{x\sim\\{\pm 1\\}^{n}}[f(x)\sgn(f_{\avg,T}(x))].\qed$

A useful tool in Boolean Function Analysis is the noise operator $T_{\rho}$.
For a vector $x\in\\{\pm 1\\}^{n}$ we denote by $N_{\rho}(x)$ the distribution
over vectors $y\in\\{\pm 1\\}^{n}$ such that for each coordinate $i\in[n]$
independently $y_{i}=x_{i}$ with probability $(1+\rho)/2$ and $y_{i}=-x_{i}$
otherwise (alternatively, $\mathop{\bf E\/}[x_{i}y_{i}]=\rho$). For a function
$f:\\{\pm 1\\}^{n}\to\mathbb{R}$ we denote by $T_{\rho}f:\\{\pm
1\\}^{n}\to\mathbb{R}$ the function defined by

$T_{\rho}f(x)=\mathop{\bf E\/}_{y\sim N_{\rho}(x)}[f(y)]$

There’s also a nice Fourier expression for the function $T_{\rho}f$ given by
$T_{\rho}f(x)=\sum_{S\subseteq[n]}\widehat{f}(S)\rho^{|S|}$. We will need a
simple fact about the noise operator.

######  Fact 2.8 ([ODo14, Exercise 2.33]).

For any function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ and any $\rho\in[-1,1]$ we
have that $\mathop{\bf E\/}[|T_{\rho}f|]\leq\mathop{\bf E\/}[|f|]$.

###  2.3 Estimating Fourier Coefficients

The following claim is a standard tool in many learning algorithms. It
establishes that estimating Fourier coefficients of a Boolean function $f$ can
be done with a few queries to $f$.

######  Claim 2.9 ([ODo14, Proposition 3.39]).

Suppose $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and $S\subseteq[n]$ then there
exists an algorithm that estimates $\widehat{f}(S)$ up to additive error
$\varepsilon$ with probability at least $1-\delta$ that makes
$O((1/\varepsilon^{2})\cdot\log(1/\delta))$ samples.

The next claim generalizes the claim to a bounded function $f:\\{\pm
1\\}^{n}\to[-1,1]$. For that generalization, we need the definition of a
randomized algorithm computing a bounded function $f$.

######  Definition 2.10 (Randomized Algorithm for a Bounded Function).

Let $f:\\{\pm 1\\}^{n}\to[-1,1]$ be a bounded function. We say that algorithm
A is a randomized algorithm for $f$ if on any fixed input $x$ algorithm A
outputs a random bit $\mathbf{y}\in\\{\pm 1\\}$ with $\mathop{\bf
E\/}[\mathbf{y}]=f(x)$.

######  Claim 2.11.

Let $f:\\{\pm 1\\}^{n}\to[-1,1]$, and let $A$ be a randomized algorithm for
$f$. Then, there exists an algorithm making
$O((1/\varepsilon^{2})\cdot\log(1/\delta))$ calls to $A$ that estimates
$\widehat{f}(S)$ up to additive error $\varepsilon$ with probability at least
$1-\delta$.

###### Proof Sketch.

We estimate $\widehat{f}(S)$ by sampling
$m=O((1/\varepsilon^{2})\cdot\log(1/\delta))$ uniformly random inputs
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(m)}$, applying $A$ to each of them to
get random bits $(\mathbf{y}_{1},\mathbf{y}_{2},\ldots,\mathbf{y}_{m})$, and
taking the empirical mean of
$\frac{1}{m}\sum_{i=1}^{m}\mathbf{y}_{i}\cdot\chi_{S}(\mathbf{x}^{(i)})$. Note
that for each $i\in[m]$ we have that
$\mathbf{y}_{i}\cdot\chi_{S}(\mathbf{x}^{(i)})$ is a $\\{\pm 1\\}$ random
variable with expectation

$\mathop{\bf
E\/}_{\mathbf{x}^{(i)},\mathbf{y}_{i}}[\mathbf{y}_{i}\cdot\chi_{S}(\mathbf{x}^{(i)})]=\mathop{\bf
E\/}_{\mathbf{x}^{(i)}}\left[\mathop{\bf
E\/}_{\mathbf{y}_{i}}[\mathbf{y}_{i}|\mathbf{x}^{(i)}]\cdot\chi_{S}(\mathbf{x}^{(i)})\right]=\mathop{\bf
E\/}_{\mathbf{x}^{(i)}}[f(\mathbf{x}^{(i)})\cdot\chi_{S}(\mathbf{x}^{(i)})]=\widehat{f}(S).$

The claim follows from 2.1. ∎

###  2.4 Random Restrictions

######  Definition 2.12 (Restriction).

Consider the class of functions on $\\{\pm 1\\}^{n}$. A restriction is a pair
$(J,z)$ where $J\subseteq[n]$, and $z\in\\{\pm 1\\}^{\overline{J}}$. Given a
function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$, and a restriction $(J,z)$, the
restricted function $f_{\overline{T}\to z}:\\{\pm 1\\}^{T}\to\mathbb{R}$ is
defined by $f_{\overline{T}\to z}(x)=f(y)$ where $y_{T}=x$ and
$y_{\overline{T}}=z$.

######  Definition 2.13 ($\delta$-Random Restriction).

For $\delta\in[0,1]$ we say that $J$ is a $\delta$-random subset of $S$ if it
is formed by including each element independently with probability $\delta$,
which we denote as $J\subseteq_{\delta}S$. A $\delta$-random restriction,
denoted $(J,z)\sim\mathcal{R}_{\delta}$, is sampled by taking $J$ to be a
$\delta$-random subset $J$ on $[n]$, and taking $z$ to be a uniformly random
string in $\\{\pm 1\\}^{\overline{J}}$.

Occasionally, we will abuse notation and think of $f_{\overline{T}\to z}$ as a
function from $\\{\pm 1\\}^{n}$ to $\\{\pm 1\\}$ that ignores bits outside
$T$. For example, $f_{\overline{T}\to z}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ is
given by $f_{\overline{T}\to z}(x)=f(x_{T},z_{\overline{T}})$. Finally, we
will use the following fact on random restrictions:

######  Fact 2.14 ([ODo14, Corollary 3.22]).

For a function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ and sets $S\subseteq
J\subseteq[n]$ we have

$\mathop{\bf E\/}_{z\in\\{\pm 1\\}^{\overline{J}}}[\widehat{f_{\overline{J}\to
z}}(S)^{2}]=\sum_{\begin{subarray}{c}R\subseteq[n],R\cap
J=S\end{subarray}}\widehat{f}(R)^{2}.$

##  3 Overview of Techniques

Both of our algorithms rely on only having to consider a subset of influential
coordinates, rather than all $n$ input variables. This is obtained using
results from [DMN19], and is discussed further in Section 4. For now, we
simply assume that we are only dealing with $\poly(k,1/\varepsilon)$
coordinates $\mathcal{S}$. For simplicity of presentation, we ignore
dependence on $\varepsilon$, and focus only the dependence on $k$. Thus, in
this section, assume that $\varepsilon$ is a small universal constant, e.g.,
$\varepsilon=0.01$.

###  3.1 Techniques for Establishing Theorem 1.4

Our first result shows how to further reduce the number of coordinates we need
to consider down to $O(k/\varepsilon^{2})$, while only losing at most
$\varepsilon$ amount of correlation with the maximally correlated $k$-junta.
In establishing Theorem 1.4, we first develop intuition behind a notion of
normalized influence that we introduce next:

######  Definition 3.1 (Normalized Influence).

Let $f:\\{\pm 1\\}^{n}\to\mathbb{R}$. We define the normalized influence of
coordinate $i$ on $f$ as

${\mathbf{NInf}}_{i}[f]=\sum_{S\ni i}\frac{\widehat{f}(S)^{2}}{|S|}.$

We also naturally define the normalized influence below level $k$:

${\mathbf{NInf}}_{i}^{\leq k}[f]:=\sum_{\begin{subarray}{c}|S|\leq k\\\ S\ni
i\end{subarray}}\frac{\widehat{f}(S)^{2}}{|S|}.$

We note that while the term “normalized influence” is new, the quantity itself
is not. It first appeared in a work of Talagrand [Tal94] (expressed as
$M(\Delta_{i}f)^{2}$) which generalized the famous KKL theorem [KKL88,
Kel+20], and subsequently appeared in followup works extending Talagrand’s
theorem to Schreier graphs [OW13]. As far as we know, this is the first use of
this quantity in a learning or testing setting.

The next claim states that the sum of normalized influences of $f$ equals its
variance.

######  Claim 3.2.

For any function $f:\\{\pm 1\\}^{n}\to\mathbb{R}$, we have that
$\sum_{i}{\mathbf{NInf}}_{i}[f]=\mathop{\bf Var\/}[f].$

###### Proof.

We have that

$\sum_{i\in[n]}{\mathbf{NInf}}_{i}[f]=\sum_{i\in[n]}\sum_{S\ni
i}\frac{\widehat{f}(S)^{2}}{|S|}=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
S\neq\emptyset\end{subarray}}\sum_{i\in
S}\frac{\widehat{f}(S)^{2}}{|S|}=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
S\neq\emptyset\end{subarray}}|S|\frac{\widehat{f}(S)^{2}}{|S|}=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
S\neq\emptyset\end{subarray}}\widehat{f}(S)^{2}=\mathop{\bf Var\/}[f],$

where the last equality follows from Parseval’s identity. ∎

######  Remark 3.3.

We note that for a balanced Boolean function $f$ (that is, one where
$\mathop{\bf E\/}_{x}[f(x)]=0$) the normalized influences form a probability
distribution on the coordinates $i$.

The idea behind establishing Theorem 1.4 begins with the observation the these
normalized influences can be thought of as defining a sub-probability
distribution over the input coordinates of $f$, since these are non-negative
numbers whose sum is at most $1$. The weight assigned to coordinate $i$,
similar to the regular influence, captures how important $i$ is to $f$, but
assigns a higher relative weight to the coordinates with Fourier mass coming
from the lower levels of the Fourier decomposition.

The second important observation for us is that for any set $T$ of size at
most $k$ we can write

$\sum_{i\in T}{\mathbf{NInf}}_{i}^{\leq k}[f]=\sum_{i\in
T}\sum_{\begin{subarray}{c}|S|\leq k\\\ \emptyset\neq S\ni
i\end{subarray}}\frac{\widehat{f}(S)^{2}}{|S|}\geq\sum_{i\in
T}\sum_{\begin{subarray}{c}S\subseteq T\\\ S\ni
i\end{subarray}}\frac{\widehat{f}(S)^{2}}{|S|}=\sum_{\emptyset\neq S\subseteq
T}\widehat{f}(S)^{2}.$ (1)

Intuitively, this shows that if some set of coordinates captures large amount
of Fourier mass, then this same subset of coordinates also is very likely to
be sampled by our sub-probability distribution defined by the normalized
influences. Our idea follows this line of thought – we get decent estimates
for all of the normalized influences, and sample coordinates from this
estimated distribution. Let $T$ be the target set of size $k$, i.e., the one
for which the closest $k$-junta to $f$ is a junta on $T$. Without loss of
generality we can assume that $T$ captures constant fraction of the Fourier
mass, meaning $\sum_{\emptyset\neq S\subseteq
T}\widehat{f}(S)^{2}\geq\Omega(1)$. Otherwise, the best correlation of $f$
with a $k$-junta is $o(1)<\varepsilon$ and the task of
$\varepsilon$-accurately estimating the distance to the set of $k$-juntas
becomes trivial. Assuming $T$ captures constant fraction of the Fourier mass,
Equation 1 tells us that we will sample $i\in T$ with constant probability
mass. Thus, sampling from this distribution $O(k)$ times means we will have
seen most of $T$ up to a small loss in correlation.

To actually estimate these normalized influences, we apply a series of $\log
10k$ random restrictions to our function $f$ (first take $1$-random
restrictions, then $1/2$-random restrictions, then $1/4$-random restrictions,
and so on), and then show that summing $\widehat{f_{\bar{J}\to
z}}(\\{i\\})^{2}$ for each of these restrictions is sandwiched between
${\mathbf{NInf}}_{i}^{\leq k}[f]$ and ${\mathbf{NInf}}_{i}[f]$:

$\frac{1}{2}{\mathbf{NInf}}_{i}^{\leq k}[f]\leq\sum_{i=0}^{\log
10k}\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{2^{-i}}}\Bigl{[}\widehat{f_{\bar{J}\to
z}}(\\{i\\})^{2}\Bigr{]}\leq 2{\mathbf{NInf}}_{i}[f].$

This would allow us to effectively sample from a proxy distribution that still
samples $i\in T$ with constant probability.

We repeat the process iteratively, sampling coordinates one at a time, until
we either sampled all of $T$ or sampled a subset $T^{\prime}\subseteq T$ for
which we have that the best junta on $T^{\prime}$ is almost as correlated with
$f$ as the best junta on $T$. Since the process samples a coordinate in $T$
with constant probability in each round, after $O(k)$ iterations we are likely
to succeed, giving us a set $U$ of $O(k)$ coordinates that contains either $T$
or $T^{\prime}$ (as above). Finally, we show we can estimate, up to a small
additive error, the best correlation of a junta-on-$U$ with $f$, given only
approximate oracle access to the coordinates in $\mathcal{S}$. By the above
discussion the estimate we get is lower bounded by the best correlation with a
$k$-junta up to a small additive error. It is also upper bounded (trivially)
with the best correlation of $f$ with a $O(k)$-junta, since $|U|=O(k)$.

###  3.2 Techniques for Theorem 1.2

A limitation of the algorithm we described in the previous subsection is that
it only samples one coordinate at a time. In particular, suppose we want to
find $T$ exactly, instead of a superset $U$ of $T$. Then, the naive algorithm
would need to consider all subsets of $U$ of size $k$, estimating the best
correlation with a junta on each of them. This gives a $\exp(O(k))$-query
algorithm. It would be nicer if we can devise a sampling algorithm that
outputs, with constant probability, many coordinates of $T$ at a time. Such a
sampling algorithm would reduce the number of possibilities for $T$ in the
second stage. In particular, consider the case that the nearest $k$-junta to
$f$ had significant amount of Fourier mass on higher levels, say at level
$\approx k$ or maybe $\approx\sqrt{k}$. In this case it would be nice to be
able to sample from the Fourier distribution of $f$, that would give us a
large subset of $T$ with constant probability. We note that sampling from the
Fourier distribution of a Boolean function is easy for a quantum algorithm but
hard for a randomized algorithm. Nevertheless, the (classical) algorithm we
describe in this section takes inspiration from this, and samples subsets of
size $\sqrt{k}$ according to the Fourier mass of $f$ above level $\sqrt{k}$ of
each subset, in time and query complexity $\exp(\widetilde{O}(\sqrt{k}))$.

We will start with the preliminary that we have reduced to the case of only
having to consider the coordinates in $\mathcal{S}\subseteq[n]$ with
$|\mathcal{S}|\leq O(k/\varepsilon^{2})$, using our aforementioned algorithm
from the previous section, incurring only a small additive loss in correlation
with the closest $k$-junta. We start with the following definition that
generalizes normalized influences of coordinates to normalized influences of
sets of coordinates.

######  Definition 3.4.

For a given subset $U\subseteq[n]$, we define its normalized influence as
follows:

${\mathbf{NInf}}_{U}[f]:=\sum_{S:\,U\subseteq
S}\frac{\widehat{f}(S)^{2}}{\binom{|S|}{|U|}}.$

We also have the natural extension of ${\mathbf{NInf}}_{U}^{\leq
k}[f]=\sum_{S:\,|S|\leq k,U\subseteq
S}\frac{\widehat{f}(S)^{2}}{\binom{|S|}{|U|}}$, analogous to Definition 3.1.

This is a direct generalization of the quantity in Definition 3.1. In
particular, we consider taking $|U|=\sqrt{k}$. Note there are
$2^{\widetilde{O}(\sqrt{k})}$ such $U$ within the coordinates in
$\mathcal{S}$, and we can think of these normalized influences as once again
defining a sub-probability distribution over subsets of size $\sqrt{k}$. It
likely does not sum to $1$, but rather sums to
$\mathbf{W}_{\mathcal{S}}^{\geq\sqrt{k}}[f]\leq 1$. We show that these
normalized influences at exactly level $\sqrt{k}$ can once again be
approximated to within a constant factor via a sequence of random restrictions
to $f$:

$\frac{1}{2}{\mathbf{NInf}}_{U}^{\leq k}[f]\leq\sum_{i=0}^{2\sqrt{k}\log
10k}\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{p^{i}}}\Bigl{[}\widehat{f_{\bar{J}\to
z}}(U)^{2}\Bigr{]}\leq 3{\mathbf{NInf}}_{U}[f],$

where $p=\Bigl{(}1-\frac{1}{2\sqrt{k}}\Bigr{)}$. For more details on this
statement, see Theorem 5.1.

We are now ready to outline the overall algorithm in Section 5. Suppose
$T\subseteq\mathcal{S}$ is the subset on which the nearest $k$-junta (within
$\mathcal{S}$) is defined. Our algorithm can then be broken down into two
phases:

  1. Phase 1.

We get a proxy for ${\mathbf{NInf}}_{U}$ for all $|U|=\sqrt{k}$. This is
achieved by performing a series of random restrictions to $f$.

We consider these proxies as a distribution, and sample a constant (this
constant is actually dependent on $\varepsilon$, see Section 5 for details)
number of subsets of size $\sqrt{k}$. With high probability, one of these is
in our set of interest $T$, provided $T$ has a non-negligible amount of
Fourier mass above level $\sqrt{k}$.

We don’t know which of the subsets we sample are actually in $T$, so we start
a branching process. For each subset we sampled, we restrict $f$’s values in
that subset, and recursively sample from sets of size $\sqrt{k}$ using the
steps described above. Our branching process will have depth at most
$\sqrt{k}$ since at each level we sample $\sqrt{k}$ new coordinates, and $T$
can have at most $k$ relevant coordinates. This phase of our algorithm
produces $2^{\tilde{O}(\sqrt{k})}$ possible subsets of our target set $T$.

  2. Phase 2.

With high probability, one of the branches in the above process will have
captured most of the coefficients of $T$ that are relevant above level
$\sqrt{k}$ on the Fourier spectrum. Each branch of this process represents a
different possibility for what $T$ may be, so for each branch we randomly
restrict $f$ so that the coordinates sampled in that branch are fixed, which
effectively moves most of the mass of $T$ to levels below $\sqrt{k}$. We then
estimate all the Fourier coefficients of this restricted $f$ below level
$\sqrt{k}$, allowing us to get an estimate for the closest $k$-junta on any
subset using these estimated coefficients. Each estimation of a Fourier
coefficient requires $2^{\widetilde{O}(\sqrt{k})}$-queries to estimate to the
desired accuracy, and there are $2^{\widetilde{O}(\sqrt{k})}$ Fourier
coefficients to estimate, so overall we make at most
$2^{\widetilde{O}(\sqrt{k})}$ queries. From there, for each possible subset of
$B\subseteq T$ outputted by phase one, we brute force over all possible
subsets of size $k$ containing $B$, estimating the correlation $f$ has with
the closest $k$-junta on that subset using our estimated Fourier coefficients.
This last step takes exponential time in $k$. We emphasize that while our
runtime is exponential in $k$, our query complexity is only exponential in
$\widetilde{O}(\sqrt{k})$.

In the entire above explanation, we have eliminated the dependence on
$\varepsilon$ for simplicity. We also only consider $T$ for conceptual and
analytic simplicity – in reality, we have no idea what $T$ is, and indeed it
is exactly what we are looking for. Therefore, more work must be done in order
to show that we do not accidentally pick the wrong set, for which our
estimates may be inaccurate. To get around this subtle issue, we further apply
a noise operator in order to ensure that the significant parts of $f$ lie
below level roughly $\sqrt{k}$. We discuss this further in Section 5.2.

##  4 Finding a Small(er) Set of Influential Coordinate Oracles

In this section, we detail the process of constructing oracles to coordinates
with large low-degree influence. We expand upon the techniques in [DMN19],
reducing the number of coordinates one needs to consider to produce a highly
correlated $k$-junta (assuming one exists).

###  4.1 Approximate Oracles to Influential Coordinates

In this subsection we outline and generalize the methods used by [DMN19] to
achieve oracle access to coordinates with large low-degree infuence in $f$. We
start with the following definitions from their paper, repeated here for
clarity:

######  Definition 4.1 ([DMN19, Def. 3.1]).

Let $\mathcal{D}$ be a set of functions mapping $\\{\pm 1\\}^{n}$ to $\\{\pm
1\\}$. We say that $\mathcal{D}$ is an oracle for the coordinates in
$\mathcal{S}$ if

  * •

for every $g\in\mathcal{D}$, there is some $i\in\mathcal{S}$ such that
$g=\pm\Dict_{i}$; and

  * •

for every $i\in\mathcal{S}$, there is some $g\in\mathcal{D}$ such that
$g=\pm\Dict_{i}$.

In other words, $\mathcal{D}$ is an oracle for $\mathcal{S}$ if
$\mathcal{D}=\\{\Dict_{i}:i\in\mathcal{S}\\}$ “up to sign”.

However, it is not tractable to achieve perfect access to such oracles, so we
have to settle for the following weaker notion of approximate oracles:

######  Definition 4.2 ([DMN19, Def. 3.2]).

Let $\mathcal{D}$ be a set of functions mapping $\\{\pm 1\\}^{n}$ to $\\{\pm
1\\}$. We say that $\mathcal{D}$ is an $\nu$-oracle for the coordinates in
$\mathcal{S}$ if

  * •

for every $g\in\mathcal{D}$, there is some $i\in\mathcal{S}$ such that $g$ is
$\nu$-close to $\pm\Dict_{i}$; and

  * •

for every $i\in\mathcal{S}$, there is exactly one $g\in\mathcal{D}$ such that
$g$ is $\nu$-close to $\pm\Dict_{i}$; and

  * •

For every $g\in\mathcal{D}$, and $\delta>0$, there is a randomized algorithm
that compute $g(x)$ correctly on any $x\in\\{\pm 1\\}^{n}$ with probability at
least $1-\delta$, using $\poly(k,\log\frac{1}{\delta})$ queries to $f$.

Lemma 3.6 in [DMN19] establishes that we can achieve access to a set
$\mathcal{D}$ of approximate oracles to
$\mathcal{S}\supseteq\\{i\,:\,{\mathbf{Inf}}_{i}^{\leq
k}[f]\geq\varepsilon^{2}/k\\}$ of bounded size.

More specifically, we have the following corollary:

######  Corollary 4.3 ([DMN19, Lemma 3.6]).

With $\poly(k,\frac{1}{\varepsilon},\log\frac{1}{\delta})\cdot\frac{1}{\nu}$
queries to $f$, we can gain access to an approximate oracle set $\mathcal{D}$
in the sense that for every coordinate $i$ such that ${\mathbf{Inf}}_{i}^{\leq
k}[f]\geq\frac{\varepsilon^{2}}{k}$, there exists a $g\in\mathcal{D}$ such
that $g$ is $\nu$-close to $\pm\Dict_{i}$ with probability at least
$1-\delta$. Furthermore,
$|\mathcal{D}|\leq\poly(k,\frac{1}{\varepsilon},\log(1/\delta))$.

For our purposes, we take $\nu=0.1$ and
$\delta=2^{-\poly(k,\frac{1}{\varepsilon})}$ in all our algorithms. Since we
will make much fewer than $2^{\poly(k/\varepsilon)}$-many queries to the
coordinate oracles, we can assume that all of our oracles are indeed $\nu=0.1$
close to dictators/anti-dictators, since by a union bound this is true with
high probability.

It is important to note that we do not have a description of which coordinates
are influential: from an information theoretic standpoint this would require
query complexity dependent on $n$. What we do have is oracle access to these
coordinates in the sense that for all $i$ such that ${\mathbf{Inf}}_{i}^{\leq
k}[f]\geq\varepsilon^{2}/k$, there exists $g_{i}\in\mathcal{D}$ such that
$g_{i}(x)\approx\pm\Dict_{i}(x)$, that is, $\mathcal{D}$ contains dictators or
anti-dictators to every influential coordinate. Using simple techniques of
local correction we can simplify this: we need only consider dictators to each
coordinate in the oracle. Also, we can convert closeness on average $x$ to
high probability correctness for all $x$ (i.e., a worst-case guarantee).

######  Lemma 4.4.

Suppose $f$ is $\nu$-close to $\pm\Dict_{i}$. For any $x\in\\{\pm 1\\}^{n}$,
$\LocalCorrect(f,x)$ samples a random $y\sim\\{\pm 1\\}^{n}$ and outputs
$f(y)f(x\cdot y)$, where $x\cdot y$ is pointwise multiplication. Then,

$\forall{x}:\mathop{\bf Pr\/}_{y\sim\\{\pm
1\\}^{n}}[\LocalCorrect(f,x)\neq\Dict_{i}(x)]\leq 2\nu.$

###### Proof.

Suppose that $f$ is $\nu$ close to $\Dict_{i}$. Then we have $\mathop{\bf
Pr\/}_{y\sim\\{\pm 1\\}^{n}}[f(y)\neq\Dict_{i}(y)]\leq\nu$, and since $x\cdot
y$ has the same distribution as $y$, $\mathop{\bf Pr\/}_{y\sim\\{\pm
1\\}^{n}}[f(x\cdot y)\neq\Dict_{i}(x\cdot y)]\leq\nu$. Let $A$ be the event
that $f(y)\neq\Dict_{i}(y)$ and let $B$ be the event that $f(x\cdot
y)\neq\Dict_{i}(x\cdot y)$. Clearly if $\LocalCorrect(f,x)\neq\Dict_{i}(x)$
then at least one of $A$ and $B$ must have occurred (since
$\Dict_{i}(x)=\Dict_{i}(x\cdot y)\cdot\Dict_{i}(y)$). Thus, by the union
bound, we have

$\mathop{\bf Pr\/}_{y\sim\\{\pm
1\\}^{n}}[\LocalCorrect(f,x)\neq\Dict_{i}(x)]\leq\mathop{\bf Pr\/}[A\cup
B]\leq\mathop{\bf Pr\/}[A]+\mathop{\bf Pr\/}[B]\leq 2\nu$

A similar argument shows that if $f$ is $\nu$ close to $-\Dict_{i}$, then
$\LocalCorrect(f,x)$ is not equal to $(-\Dict_{i}(y))(-\Dict_{i}(x\cdot
y))=\Dict_{i}(y)\Dict_{i}(x\cdot y)=\Dict_{i}(x)$ with probability at most
$2\nu$. ∎

Given a noisy black box computing $h$ which is $\nu$-close to
$g=\pm\Dict_{i}$, local correction will compute $\Dict_{i}$ with high
probability, on every input $x$. Critically, we can treat potentially faulty
$\pm\Dict_{i}$ oracles as correct $\Dict_{i}$ oracles provided suitably many
repetitions.

######  Corollary 4.5.

If $f$ is $\nu$-close to $\pm\Dict_{i}$ for $\nu=0.1$, then repeating
$\LocalCorrect(f,x)$ independently $\poly(k,1/\varepsilon)$ times and taking
the majority outcome results in an incorrect value for $\Dict_{i}(x)$ with
probability at most $2^{-\poly(k,1/\varepsilon)}$.

###### Proof.

Clear from applying the first bound in 2.1 with $N=O(\poly(k/\varepsilon))$
and $\eta=(1-2\nu-0.5)=0.3$ in this case. ∎

We also show that restricting our attention to $\mathcal{S}$ we have not lost
more than $\varepsilon$ in the best correlation of $f$ with a $k$-junta. This
is proved in the following claim.

######  Claim 4.6.

Let $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and let $g:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ be a $k\text{-junta}$ on $U$. Let $\tau>0$. Take

$S=\left\\{i\in U\;\middle|\;{\mathbf{Inf}}_{i}^{\leq
k}[f]\geq\tfrac{\tau^{2}}{k}\right\\}$

Then, there is a junta on $S$ with correlation at least $\mathop{\bf
E\/}[fg]-\tau$ with $f$.

###### Proof.

To prove this claim, we define a function on the set $S$ such that the loss in
correlation is at most $\tau$. Consider:

$g^{\prime}(x)=g_{\avg,S}(x)=\mathop{\bf E\/}_{y}[g(y)|y_{S}=x_{S}]$

First, we note $g^{\prime}$ is a function over only the variables in $S$.
Second, it is bounded in $[-1,1]$, so it is not quite Boolean, but it can be
randomized rounded to a Boolean function, with the expected correlation with
$f$ equaling $\mathop{\bf E\/}[fg^{\prime}]$. Thus, it suffices to show that
$\mathop{\bf E\/}[fg^{\prime}]\geq\mathop{\bf E\/}[fg]-\tau$ to deduce that
there exists a randomize rounding of $g^{\prime}$ to a Boolean function
$g^{\prime\prime}$ with $\mathop{\bf E\/}[fg^{\prime\prime}]\geq\mathop{\bf
E\/}[fg]-\tau$. We also recall that

$\widehat{g^{\prime}}(T)=\begin{cases}\widehat{g}(T)&\text{ if }T\subseteq
S\\\ 0&\text{otherwise}\end{cases}$

We thus have:

$\displaystyle\left|\mathop{\bf E\/}[fg]-\mathop{\bf
E\/}[fg^{\prime}]\right|=\bigg{|}\sum_{\begin{subarray}{c}T\nsubseteq S\\\
T\subseteq U\end{subarray}}\widehat{f}(T)\widehat{g}(T)\bigg{|}$
$\displaystyle\leq\sqrt{\sum_{\begin{subarray}{c}T\nsubseteq S\\\ T\subseteq
U\end{subarray}}\widehat{f}(T)^{2}}\leq\sqrt{\sum_{i\in U\setminus
S}\sum_{\begin{subarray}{c}T\ni i\\\ T\subseteq
U\end{subarray}}\widehat{f}(T)^{2}}$ $\displaystyle\leq\sqrt{\sum_{i\in
U\setminus S}{\mathbf{Inf}}_{i}^{\leq
k}(f)}\leq\sqrt{k\cdot\frac{\tau^{2}}{k}}=\tau\qed$

Finally, the below corollary summarizes what we have achieved in this section.

######  Corollary 4.7.

With $\poly(k,\frac{1}{\varepsilon},\log\frac{1}{\delta})$ queries to $f$, we
can gain access to an approximate oracle set $\mathcal{D}$ for a set of
coordinates $\\{i:{\mathbf{Inf}}_{i}^{\leq
k}\geq\frac{\varepsilon^{2}}{k}\\}\subseteq\mathcal{S}\subseteq[n]$. Moreover,
these coordinates and oracles satisfy the following properties.

  * •

For every coordinate $i\in\mathcal{S}$, there exists a $g\in\mathcal{D}$ such
that $g$ is $0.1$-close to $\Dict_{i}$ with probability at least $1-\delta$.

  * •

$\dist(f,\mathcal{J}_{n,k})-\dist(f,\mathcal{J}_{\mathcal{S},k})\leq\varepsilon$.

  * •

$|\mathcal{S}|\leq\poly(k,1/\varepsilon,\log(1/\delta))$.

  * •

For any algorithm $A$ that uses at most $q$ queries to $\mathcal{D}$, we can
use $\LocalCorrect$ from Lemma 4.4 with error $\delta/q$ to assume that we
actually have perfect access to each coordinate oracle, up to an additive loss
of $\delta$ in confidence and a multiplicative overhead of
$\poly(\log(q/\delta))$ in query complexity.

###### Proof.

The first and the third bullet point follow from Corollary 4.3. The second
bullet point follows from 4.6. To achieve the last point, we can use Corollary
4.5 every time we make a “query” to an oracle in our algorithm. Thus every
“query” to an oracle $g\approx\pm\Dict_{i}$ at $x$ involves
$\poly(\log(q/\delta))$ many repetitions of $\LocalCorrect(g,x)$, which
results in an incorrect value with probability at most $\delta/2q$, as noted
above. Recall that Corollary 4.3 guarantees that we can output $g(x)$
correctly with probability $1-\delta/2q$ with only a $\poly(k,\log(q/\delta))$
queries to $f$. Since we only ever make at most $q$ queries to our coordinate
oracles, we can assume that $\LocalCorrect(g,x)=\Dict_{i}(x)$ in all queries.
This happens with probability at least $1-\delta$ by the union bound. ∎

Therefore, for the rest of this paper, we will assume that we have oracle
access to exact dictators.

###  4.2 Implicit Access to an Underlying Junta

An important consequence of having coordinate oracles is that it allows us to
reduce the input size of the function dramatically. Suppose $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$ and we have
$\mathcal{D}=\\{g_{1},\ldots,g_{{k^{\prime}}}\\}$ are randomized algorithms
that for any $x\in\\{\pm 1\\}^{n}$ output
$g_{i}(x)=\Dict_{j_{i}}(x)=x_{j_{i}}$. We have that
$j_{1},\ldots,j_{k^{\prime}}\in[n]$ are a set of ${k^{\prime}}$ distinct
coordinates.

Let $U=\\{j_{1},\ldots,j_{k^{\prime}}\\}$. We want to get access to the
following function: $g(x_{1},\ldots,x_{k^{\prime}})=\mathop{\bf
E\/}[f(y)|y_{j_{1}}=x_{1},y_{j_{2}}=x_{2},\ldots,y_{j_{k^{\prime}}}=x_{{k^{\prime}}}]$.
More precisely, given $x_{1},\ldots,x_{{k^{\prime}}}$ we want to sample
uniformly from all $y\in\\{\pm 1\\}^{n}$ that satisfy
$y_{j_{1}}=x_{1},y_{j_{2}}=x_{2},\ldots,y_{j_{k^{\prime}}}=x_{{k^{\prime}}}$
and apply $f$ on this $y$.

The following algorithm that runs in $\poly(k,\log(1/\delta))$ time samples
$y$ from such a distribution.

Input: $f$ (target function), $\mathcal{D}=\\{g_{1},\ldots,g_{k^{\prime}}\\}$
(coordinate oracles), $(x_{1},\ldots,x_{{k^{\prime}}})\in\\{\pm
1\\}^{{k^{\prime}}}$

Output: A vector $y\in\\{\pm 1\\}^{n}$ with
$(g_{1}(y),\ldots,g_{k^{\prime}}(y))=(x_{1},\ldots,x_{k^{\prime}})$

1Sample $y\sim\\{\pm 1\\}^{n}$ and let $z\in\\{\pm 1\\}^{k^{\prime}}$ be the
vector of evaluations of $\\{g_{1},\ldots,g_{k^{\prime}}\\}$ on $y$;

2 while  _$z\neq x$_ do

3 repeat

4 Let $y^{\prime}$ be a copy of $y$, but flip each bit independently with
probability $\frac{1}{{k^{\prime}}}$;

5 Let $z^{\prime}$ be the vector of evaluations of
$\\{g_{1},\ldots,g_{k^{\prime}}\\}$ on $y^{\prime}$;

6 until  _$\dist(x,z^{\prime}) <\dist(x,z)$_

7 $y=y^{\prime}$;

8 $z=z^{\prime}$;

return _$y$_

Algorithm 1 Sampling a uniformly random input consistent with the oracles’
values

######  Theorem 4.8.

Algorithm 1 with probability $1-\delta$ runs in time
$\poly({k^{\prime}},\log(1/\delta))$.

###### Proof.

We focus on the number of iterations of the inner repeat loop. Given $(y,z)$
with $z\neq x$ we analyze the time it takes to find a
$(y^{\prime},z^{\prime})$ with $\dist(z^{\prime},x)<\dist(z,x)$. Since $x\neq
z$ without loss of generality we can assume that $x_{1}\neq z_{1}$. To get
$(y^{\prime},z^{\prime})$ with $\dist(z^{\prime},x)<\dist(z,x)$, it suffices
to sample a vector $y^{\prime}$ with $y^{\prime}_{j_{1}}=x_{1}$ and
$y^{\prime}_{j_{2}}=y_{j_{2}},y^{\prime}_{j_{3}}=y_{j_{3}},\ldots,y^{\prime}_{j_{k^{\prime}}}=y_{j_{k^{\prime}}}$.
Indeed, since we are flipping each coordinate with probability
$1/{k^{\prime}}$ the probability of sampling such a $y^{\prime}$ is exactly
$1/{k^{\prime}}\cdot(1-1/{k^{\prime}})^{{k^{\prime}}-1}\geq
1/(e{k^{\prime}})$. Thus, we get that the runtime of the repeat loop is
stochastically dominated by a geometric random variable with success
probability $1/(e{k^{\prime}})$. Thus with probability at least
$1-\delta/{k^{\prime}}$, it finishes after
$O({k^{\prime}}\cdot\log({k^{\prime}}/\delta))$ iterations. We run the inner
repeat loop at most ${k^{\prime}}$-times, thus by union bound, with
probability at least $1-\delta$ the entire process end after at most
$O({k^{\prime}}^{2}\cdot\log({k^{\prime}}/\delta))$ executions of line 5. We
note that execution line 5 actually requires ${k^{\prime}}$ queries to
$g_{1},\ldots,g_{k^{\prime}}$, each of them takes
$\poly(k)=\poly({k^{\prime}})$ time. thus overall, with probability at least
$1-\delta$, our algorithm run in time $\poly({k^{\prime}},\log(1/\delta))$. ∎

######  Theorem 4.9.

Algorithm 1 samples uniformly from the set of inputs
$\\{y^{\prime}:(g_{1}(y^{\prime}),\ldots,g_{k^{\prime}}(y^{\prime}))=(x_{1},\ldots,x_{k^{\prime}}))\\}$.

###### Proof.

Let $U=\\{j_{1},\ldots,j_{k^{\prime}}\\}$ be the set of coordinates for which
$\\{g_{1},\ldots,g_{k^{\prime}}\\}$ are oracles to. Algorithm 1 certainly
samples a vector $y$ with
$y_{j_{1}}=x_{1},\ldots,y_{j_{k^{\prime}}}=x_{k^{\prime}}$. We want to show
additionally that Algorithm 1 samples $y_{\overline{U}}$ uniformly at random.
In fact, at any point in the algorithm the distribution over
$y_{\overline{U}}$ is uniform. This is clearly true in the first step where
$y\sim\\{\pm 1\\}^{n}$, and remains true along the algorithm as we apply
independent noise to coordinates in $\overline{U}$ and decide whether to apply
the noise or not according to the value of $y_{U}$ which is independent of
$y_{\overline{U}}$. ∎

We will consider algorithms computing non-Boolean function like $g=f_{\avg,S}$
for some subset $S\subseteq[n]$. Note that $g$ is a function whose range in
$[-1,1]$, but not necessarily a Boolean function.

######  Theorem 4.10 (Formal version of Theorem 1.5).

Let $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$,
$\mathcal{D}=\\{g_{1},\ldots,g_{k^{\prime}}\\}$ be a set of coordinate
oracles. Let $g$ be a function from $\\{\pm 1\\}^{k^{\prime}}\to[-1,1]$
defined by $g(x)=\mathop{\bf
E\/}[f(y)|g_{1}(y)=x_{1},\ldots,g_{k^{\prime}}(y)=x_{k^{\prime}}]$. Then $g$
has a randomized algorithm in the sense of Definition 2.10 computing it that
runs in expected time $\poly(k^{\prime})$.

###### Proof.

Given $x=(x_{1},\ldots,x_{k^{\prime}})$ apply Algorithm 1 on $f$,
$\mathcal{D}$ and $x$ to get a vector $y\in\\{\pm 1\\}^{n}$. Return $f(y)$. It
is clear that since $y$ is a uniform input subject to
$g_{1}(y)=x_{1},\ldots,g_{k^{\prime}}(y)=x_{k^{\prime}}$ that our algorithm is
a randomized algorithm for $g$. ∎

###  4.3 Influential Coordinate Oracles

As above, denote as $\mathcal{S}$ the superset of the low-degree influential
coordinates of $f$, and $\mathcal{D}$ as the set of approximate oracles to
said coordinates, obtained via Corollary 4.3 with parameter $\nu=0.1$. As we
discussed in Section 4.1, we assume (with a small loss in error probability,
and a small multiplicative factor on query complexity) that we have exact
access to dictators for each influential coordinate. We work towards proving
the following improved version of a corollary that appeared in [DMN19]:

The idea will be to take $\mathcal{D}$, a set of
$k^{\prime}=\poly\left(k,\frac{1}{\varepsilon}\right)$ coordinate oracles, and
somehow “prune” it down to a set $\mathcal{D}^{\prime}$ of at most
$O(\frac{k}{\varepsilon^{2}})$ coordinate oracles, such that that the loss in
the most correlated junta on this smaller set of coordinates is at most
$\varepsilon$

$\max_{g\in\mathcal{J}_{\mathcal{D},k}}\mathop{\bf
E\/}[fg]-\max_{g\in\mathcal{J}_{\mathcal{D}^{\prime},k}}\mathop{\bf
E\/}[fg]\leq\varepsilon.$

###  4.4 Reducing the Number of Oracles to Consider

Starting with a set of $\poly(k/\varepsilon)$ set of oracles $\mathcal{D}$ for
a set $\mathcal{S}$ containing the influential coordinates of $f$, our goal in
this section is to prune the number of oracles to $O(k/\varepsilon^{2})$ in a
way that incurs only a small loss in correlation with the nearest $k$-junta.
[DMN19] achieved their theorem by noting that applying a standard noise
operator to $f$ did not affect its proximity to the nearest $k$-junta
significantly, while also guaranteeing that at most
$\frac{k^{2}}{\varepsilon^{2}}$ coordinates could have large influence. They
then were able to estimate the influence of every coordinate in $\mathcal{D}$
despite only having (approximate) oracle access to the influential
coordinates, and thus were able to determine which oracles were actually
oracles to influential coordinates, of which there were less than
$k^{2}/\varepsilon^{2}$.

Our approach, as explained at a high level in Section 3, is to estimate the
normalized influence of each coordinate in $\mathcal{S}$, which is done via a
sequence of random restrictions to $f$. In words, the below algorithm
estimates for each coordinate $i\in\mathcal{S}$ the quantity
$\lambda_{i}^{\approx 2^{d}}=\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{2^{-d}}}[\widehat{f_{\bar{J}\to
z}}(\\{i\\})^{2}]$, where $(J,z)\sim\mathcal{R}_{2^{-d}}$ parameterize a
$2^{-d}$-random restriction to $f$. Then, $\lambda_{i}$ is defined to be sum
over a series of random restrictions $d=0,...,\log 10k$ of
$\lambda_{i}^{\approx 2^{d}}$. The core idea of our algorithm is that this sum
over Fourier coefficients on the first level of restricted versions of $f$ is
a proxy for ${\mathbf{NInf}}_{i}[f]$. In other words, we have the following
theorem:

######  Theorem 4.11.

Let $f:\\{\pm 1\\}^{{k^{\prime}}}\to\mathbb{R}$, where
${k^{\prime}}=|\mathcal{D}|$. Let $i\in[{k^{\prime}}]$. Let

$\lambda_{i}[f]=\sum_{m=0}^{\log(10k)}\lambda_{i}^{\approx
2^{m}}[f],\qquad\text{where}\qquad\lambda_{i}^{\approx 2^{m}}[f]=\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{2^{-m}}}[\widehat{f_{\bar{J}\to
z}}(\\{i\\})^{2}].$

Then, $\frac{1}{2}{\mathbf{NInf}}_{i}^{\leq k}[f]\leq\lambda_{i}[f]\leq
2{\mathbf{NInf}}_{i}[f]$.

We postpone the proof of Theorem 4.11 to Section 4.5. The definition of
$\lambda_{i}$ naturally gives rise to an algorithm for estimating
$\lambda_{i}$ that we present next. The algorithm would return for each
$i\in[{k^{\prime}}]$ an estimate $\widetilde{\lambda}_{i}$ that would be close
to $\lambda_{i}$ with high probability.

Input: $f:\\{\pm 1\\}^{k^{\prime}}\to[-1,1]$ along with randomized algorithm A
computing $f$ (recall Def. 2.10). Parameters $1-\delta$ (confidence),
$\varepsilon$ (additive error) and $k$.

Output: Estimates
$(\widetilde{\lambda_{1}},\ldots,\widetilde{\lambda_{k^{\prime}}})$ for
$(\lambda_{1},\ldots,\lambda_{k^{\prime}})$.

1 Let $m=\poly(k,k^{\prime},1/\varepsilon,\log(1/\delta))$

2 Initialize $\widetilde{\lambda_{i}}=0$ for all $i\in[k^{\prime}]$;

3 for  _$d=0$ to $\log 10k$_ do

4 Initialize $\widetilde{\lambda}_{i}^{\approx 2^{d}}=0$ for all
$i\in[k^{\prime}]$;

5

6 repeat  _$m$_ times

7 Let $(J,z)\sim\mathcal{R}_{2^{-d}}$ be a $2^{-d}$-random restriction.

8

9 Estimate $\widehat{f_{\bar{J}\to z}}(\\{j\\})$ for all $j\in J$ up to
additive error $\frac{\varepsilon}{6\log(10k)}$ with probability
$1-\delta/\poly(k,k^{\prime},m)$ using 2.11 and algorithm A.

10 Denote by $\widetilde{f_{\bar{J}\to z}}(\\{j\\})$ the estimated Fourier
coefficient.

11 Update $\widetilde{\lambda}_{j}^{\approx
2^{d}}=\widetilde{\lambda}_{j}^{\approx 2^{d}}+\widetilde{f_{\bar{J}\to
z}}(\\{j\\})^{2}$ for all $j\in J$.

12 Let $\widetilde{\lambda}_{i}^{\approx
2^{d}}=\widetilde{\lambda}_{i}^{\approx 2^{d}}/m$ for all $i\in[k^{\prime}]$;

13Let $\widetilde{\lambda_{i}}=\sum_{d}\widetilde{\lambda}_{i}^{\approx
2^{d}}$;

return
_$(\widetilde{\lambda_{1}},\widetilde{\lambda_{2}},\ldots,\widetilde{\lambda_{k^{\prime}}})$_

Algorithm 2 Estimating $\lambda_{i}$

######  Lemma 4.12.

With probability at least $1-\delta$ we have that for all $i\in[k^{\prime}]$
it holds that $|\widetilde{\lambda}_{i}-\lambda_{i}|\leq\varepsilon$.

###### Proof.

If $j\notin J$ the Fourier coefficient of $\widehat{f_{\bar{J}\to z}}$ is $0$
and so our estimate is correct in that case. In the case $j\in J$, each
estimation of the Fourier coefficient is correct up to additive error
$\eta=\varepsilon/6\log(10k)$ with probability at least
$1-\delta/\poly(k,k^{\prime},m)$. Thus, we get that $\widetilde{f_{\bar{J}\to
z}}(\\{j\\})^{2}=(\widehat{f_{\bar{J}\to
z}}(\\{j\\})\pm\eta)^{2}=\widehat{f_{\bar{J}\to z}}(\\{j\\})^{2}\pm
2\eta|\widehat{f_{\bar{J}\to z}}(\\{j\\})|\pm\eta^{2}=\widehat{f_{\bar{J}\to
z}}(\\{j\\})^{2}\pm 3\eta$. Furthermore, we have that $\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{2^{-d}}}[\widehat{f_{\bar{J}\to
z}}(\\{j\\})^{2}]=\lambda_{j}^{\approx 2^{d}}$, thus by 2.1 we have that the
empirical mean of
$m=\poly(1/\varepsilon,\log(k),\log(k^{\prime}),\log(1/\delta))$ copies of
$\widetilde{f_{\bar{J}\to z}}(\\{j\\})^{2}$ is within additive error
$\varepsilon/(2\log(10k))$ from $\lambda_{j}^{\approx 2^{d}}$ with probability
at least $1-\delta/(k^{\prime}\log(10k))$. By union bound, all these estimates
are within the error bound, and we get that $|\widetilde{\lambda}_{j}^{\approx
2^{d}}-\lambda_{j}^{\approx 2^{d}}|\leq
3\eta+\varepsilon/(2\log(10k))\leq\varepsilon/(\log(10k))$. Overall, we get
that $|\widetilde{\lambda}_{j}-\lambda_{j}|\leq\varepsilon$ for all
$j\in[k^{\prime}]$ with probability at least $1-\delta$. ∎

With Algorithm 2 in hand, we are ready to present the pruning procedure.

1

Input: $f$ (target function), $\mathcal{D}$ (influential coordinate oracles,
where $\mathcal{D}$ are oracles for $\mathcal{S}$). Parameters $\varepsilon$
and $\delta$.

Output: A subset $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ of size
$O(\frac{k}{\varepsilon^{2}})$ such that we lose at most $\varepsilon$ in
correlation with $f$.

2

3Initialize $\mathcal{D}^{\prime}=\emptyset$;

4 Let $m=O((k+\log(1/\delta))/\varepsilon^{2})$

5 repeat  _$m$_ times

6 Let $\\{g_{1},\ldots,g_{k^{\prime}}\\}=\mathcal{D}-\mathcal{D}^{\prime}$,
and $\\{g_{k^{\prime}+1},\ldots,g_{|\mathcal{D}|}\\}=\mathcal{D}^{\prime}$

7 Sample $z\in\\{\pm 1\\}^{|\mathcal{D}^{\prime}|}$. Let $f^{\prime}:\\{\pm
1\\}^{k^{\prime}}\to\mathbb{R}$ be the function defined by
$f^{\prime}(x_{1},\ldots,x_{k^{\prime}})=\mathop{\bf E\/}_{y\sim\\{\pm
1\\}^{n}}[f(y)|g_{1}(y)=x_{1},\ldots,g_{k^{\prime}}(y)=x_{k^{\prime}},g_{k^{\prime}+1}(y)=z_{1},\ldots,g_{k^{\prime}+|\mathcal{D}^{\prime}|}(y)=z_{|\mathcal{D}^{\prime}|}].$
and let A be the randomized algorithm for $f^{\prime}$ from Theorem 4.10.

8 Apply Algorithm 2 on $f^{\prime}$ using the randomized algorithm A for
$f^{\prime}$ with confidence $1-\frac{\delta}{2m}$ and accuracy
$\frac{\varepsilon^{2}}{48\cdot|\mathcal{S}|}$
$\implies\widetilde{\lambda}=(\widetilde{\lambda}_{1},\ldots,\widetilde{\lambda}_{k^{\prime}})$.

9 Let our distribution $P$ be defined by $\widetilde{\lambda}$, normalized
appropriately.

10 Sample $i\sim P$, and add $g_{i}$ to $\mathcal{D}^{\prime}$.

11

12

13return _$\mathcal{D}^{\prime}$_

14

Algorithm 3 Reduce Number of Oracles

######  Lemma 4.13.

With probability at least $1-\delta$, Algorithm 3 returns a set of oracles
$\mathcal{D}^{\prime}$ to a subset of coordinates
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$, such that

$\max_{g\in\mathcal{J}_{\mathcal{S},k}}\mathop{\bf
E\/}[fg]-\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime},k}}\mathop{\bf
E\/}[fg]\leq\varepsilon.$

To prove Lemma 4.13, which tells us our algorithm succeeds and directly
implies Theorem 1.4, we will need a few more lemmas.

We denote the event $\mathcal{E}$ that in the entire execution of Algorithm 3
all $\widetilde{\lambda}_{i}$ were $\varepsilon^{2}/(48\cdot|\mathcal{S}|)$
close to the real $\lambda_{i}$. We note that by union bound this event
happens with probability at least $1-\delta/2$.

Suppose $T$ is the (unknown) set of $k$ oracles for which the best-$k$ junta
approximating $f$ is a junta on $T$. We want to show that our algorithm either
samples all the coordinates in $T$, or it samples a subset $T^{\prime}$ of $T$
that captures all but $\varepsilon^{2}/4$ of the Fourier mass of $f$ on $T$.

######  Claim 4.14.

Assume the event $\mathcal{E}$ happens. Then, with probability at least
$1-\delta/2$, after $m$ iterations, we will have either:

  1. 1.

sampled $i$ for all $i\in T$, our target set;

  2. 2.

sampled $i$ for all $i\in T^{\prime}\subseteq T$, where $\sum_{S\subseteq
T^{\prime}}\widehat{f}(S)^{2}\geq\sum_{S\subseteq
T}\widehat{f}(S)^{2}-\varepsilon^{2}/4$.

###### Proof.

In each iteration, assume we have not yet satisfied either items. Let $V$ be
the subset of coordinates in $T$ that we have not yet sampled. Let
$T^{\prime}=T\setminus V$. By assumption,

$\varepsilon^{2}/4<\sum_{S\subseteq T}\widehat{f}(S)^{2}-\sum_{S\subseteq
T^{\prime}}\widehat{f}(S)^{2}=\sum_{S\subseteq T:S\cap
V\neq\emptyset}\widehat{f}(S)^{2}.$

Let $\mathcal{S}^{\prime\prime}=\mathcal{S}\setminus\mathcal{S}^{\prime}$. We
have that $|\mathcal{S}^{\prime\prime}|=k^{\prime}$. Now note that up to
relabeling of coordinates $f^{\prime}$ from Algorithm 3 is the same as
$(f_{\avg,\mathcal{S}})_{\mathcal{S}^{\prime}\to z}$, where $z$ was randomly
chosen. For brevity, denote by
$f_{z}=(f_{\avg,\mathcal{S}})_{\mathcal{S}^{\prime}\to z}$. Note that for any
fixed $z$, $f_{z}$ is a function that depends only on the coordinates in
$\mathcal{S}^{\prime\prime}$.

By 2.14, we have

$\displaystyle\mathop{\bf E\/}_{z}\left[\sum_{\emptyset\neq S\subseteq
V}\widehat{f_{z}}(S)^{2}\right]=\sum_{R:\emptyset\neq(R\cap\mathcal{S}^{\prime\prime})\subseteq
V}\widehat{f_{\avg,\mathcal{S}}}(R)^{2}=\sum_{\begin{subarray}{c}R\subseteq\mathcal{S}:\\\
\emptyset\neq(R\cap\mathcal{S}^{\prime\prime})\subseteq
V\end{subarray}}\widehat{f}(R)^{2}$ $\displaystyle\geq\sum_{R\subseteq T:R\cap
V\neq\emptyset}\widehat{f}(R)^{2}$ $\displaystyle>\varepsilon^{2}/4.$ (2)

Next, by applying Theorem 4.11, for any fixed $z$, we have

$\sum_{i\in V}\lambda_{i}[f_{z}]\geq\frac{1}{2}\sum_{i\in
V}{\mathbf{NInf}}_{i}^{\leq k}[f_{z}]\geq\frac{1}{2}\sum_{\emptyset\neq
S\subseteq V}\widehat{f_{z}}(S)^{2}.$

By the assumption that $\mathcal{E}$ happens, the $\widetilde{\lambda_{i}}$
are $\frac{\varepsilon^{2}}{48\cdot|\mathcal{S}|}$-accurate, and we get that

$\sum_{i\in V}\widetilde{\lambda_{i}}[f_{z}]\geq\frac{1}{2}\sum_{\emptyset\neq
S\subseteq
V}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48\cdot|\mathcal{S}|}\cdot|V|\geq\frac{1}{2}\sum_{\emptyset\neq
S\subseteq V}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48}.$

On the other hand by applying Theorem 4.11 again we see that

$\sum_{i\in\mathcal{S}^{\prime\prime}}\lambda_{i}[f_{z}]\leq
2\cdot\sum_{i\in\mathcal{S}^{\prime\prime}}{\mathbf{NInf}}_{i}[f_{z}]=2\cdot\mathop{\bf
Var\/}[f_{z}]\leq 2$

and thus $\sum_{i\in\mathcal{S}^{\prime\prime}}\widetilde{\lambda}_{i}[f]\leq
2+k^{\prime}\cdot\frac{\varepsilon^{2}}{48\cdot|\mathcal{S}|}\leq
2+\frac{\varepsilon^{2}}{48}\leq 3$ (under the assumption that $\mathcal{E}$
happens). Overall, the probability to sample an element from $V$ is at least

$\frac{1}{3}\cdot\left(\frac{1}{2}\sum_{\emptyset\neq S\subseteq
V}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48}\right)=\frac{1}{6}\sum_{\emptyset\neq
S\subseteq V}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{3\cdot 48}$

By taking expectation over $z$, and using Equation 2 we see that the
probability to sample an element from $V$ overall is at least

$\mathop{\bf E\/}_{z}\left[\frac{1}{6}\sum_{\emptyset\neq S\subseteq
V}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{3\cdot
48}\right]\geq\frac{1}{6}\cdot\frac{\varepsilon^{2}}{4}-\frac{\varepsilon^{2}}{3\cdot
48}>\frac{\varepsilon^{2}}{30}.$

We get that in each iteration as long as we don’t satisfy Items (1) and (2)
above, we sample an element from $i\in T$ with probability at least
$\varepsilon^{2}/30$. By repeating the process
$m=O(\frac{k+\log(1/\delta)}{\varepsilon^{2}})$ times we would sample all of
$T$, or get stuck at some $T^{\prime}$ satisfying Item (2), with probability
at least $1-\delta/2$, using 2.1. ∎

Next, we show that finding $T^{\prime}$ is almost as good as finding $T$ in
the sense that the best correlation by juntas-on-$T^{\prime}$ with $f$ is up
to small additive error the best correlation by juntas-on-$T$ with $f$.

######  Lemma 4.15.

Suppose we have some subset $T$ such that $\sum_{S\subseteq
T}\widehat{f}(S)^{2}=c$, and we then identified a subset $T^{\prime}\subseteq
T$ such that $\sum_{S\subseteq T^{\prime}}\widehat{f}(S)^{2}\geq
c-\frac{\varepsilon^{2}}{4}$. Then

$\left|\max_{g\in\mathcal{J}_{T,k}}\mathop{\bf
E\/}[fg]-\max_{g\in\mathcal{J}_{T^{\prime},k}}\mathop{\bf
E\/}[fg]\right|\leq\varepsilon$

###### Proof.

We know that $\textrm{argmax}_{g\in\mathcal{J}_{T,k}}E[fg]=\sgn(f_{\avg,T})$
and similarly
$\textrm{argmax}_{g\in\mathcal{J}_{T^{\prime},k}}E[fg]=\sgn(f_{\avg,T^{\prime}})$.
Then we have that

$\displaystyle\left|\max_{g\in\mathcal{J}_{T,k}}\mathop{\bf
E\/}[fg]-\max_{g\in\mathcal{J}_{T^{\prime},k}}\mathop{\bf E\/}[fg]\right|$
$\displaystyle=\mathop{\bf
E\/}[f(x)(\sgn(f_{\avg,T}(x_{T}))-\sgn(f_{\avg,T^{\prime}}(x_{T^{\prime}}))]$
$\displaystyle=\mathop{\bf E\/}_{x_{T}}\left[\mathop{\bf
E\/}_{x_{\overline{T}}}[f(x_{T},x_{\overline{T}})]\left(\sgn(f_{\avg,T}(x_{T}))-\sgn(f_{\avg,T^{\prime}}(x_{T^{\prime}})\right)\right]$
$\displaystyle=\mathop{\bf
E\/}_{x_{T}}\left[f_{\avg,T}(x_{T})\left(\sgn(f_{\avg,T}(x_{T}))-\sgn(f_{\avg,T^{\prime}}(x_{T^{\prime}})\right)\right]$
$\displaystyle\leq 2\mathop{\bf
E\/}_{x_{T}}\left[\left|f_{\avg,T}(x_{T})-f_{\avg,T^{\prime}}(x_{T^{\prime}})\right|\right]$
(Since $z(\sgn(z)-\sgn(z^{\prime}))\leq 2|z-z^{\prime}|$ for all
$z,z^{\prime}\in\mathbb{R}$) $\displaystyle\leq 2\sqrt{\mathop{\bf
E\/}_{x_{T}}\left[\left(f_{\avg,T}(x_{T})-f_{\avg,T^{\prime}}(x_{T^{\prime}})\right)^{2}\right]}$
$\displaystyle=2\sqrt{\sum_{S\subseteq T}\widehat{f}(S)^{2}-2\sum_{S\subseteq
T^{\prime}}\widehat{f}(S)^{2}+\sum_{S\subseteq T^{\prime}}\widehat{f}(S)^{2}}$
$\displaystyle\leq 2\sqrt{\frac{\varepsilon^{2}}{4}}=\varepsilon\;.\qed$

###### Proof of Lemma 4.13.

Let $g$ be the $k$-junta that maximizes $\mathop{\bf E\/}[fg]$ among all
$k$-juntas on $\mathcal{S}$. Let $T$ be the set of variables on which $g$
depends. By Claim 4.14 we either sample oracles to all of $T$ or to a subset
$T^{\prime}$ for which

$\sum_{S\subseteq T^{\prime}}\widehat{f}(S)^{2}\geq\sum_{S\subseteq
T}\widehat{f}(S)^{2}-\varepsilon^{2}/4.$

In the second case, by Lemma 4.15, we incur a loss in correlation of at most
$\varepsilon$ with our nearest $k$-junta. In the first case, we lose no
correlation with the closest $k$-junta, and by a union bound our probability
of failure is at most $\delta$. ∎

The above concludes the proof of Lemma 4.13. Finally, Theorem 1.4 is implied
by Lemma 4.13, as shown below.

######  Theorem 4.16 (Theorem 1.4, restated).

Let $\varepsilon>0$, $k\in\mathbb{N}$, and $k^{\prime}=C(k/\varepsilon^{2})$
for some universal constant $C$. Then, there exists an algorithm that given
$f,k,\varepsilon$ makes at most $poly(k,1/\varepsilon)$ queries to $f$ and
returns a number $\alpha$ such that with probability at least $0.99$

  1. 1.

$\alpha\leq\max_{g\in\mathcal{J}_{n,k^{\prime}}}\mathop{\bf
E\/}[fg]+O(\varepsilon)$

  2. 2.

$\alpha\geq\max_{g\in\mathcal{J}_{n,k}}\mathop{\bf E\/}[fg]-O(\varepsilon)$

###### Proof.

Set $\delta=2^{-\poly(k,1/\varepsilon)}$. We first apply Corollary 4.3 from
[DMN19]. This gives us
$\poly(k,\frac{1}{\varepsilon},\log(1/\delta))=\poly(k/\varepsilon)$
coordinate oracles $\mathcal{D}$ to coordinates $\mathcal{S}$ that includes
all coordinates $i$ with ${\mathbf{Inf}}_{i}^{\leq
k}[f]\geq\frac{\varepsilon^{2}}{k}$. By 4.6 we see that

$\max_{g\in\mathcal{J}_{\mathcal{S},k}}\mathop{\bf
E\/}[fg]\geq\max_{g\in\mathcal{J}_{n,k}}\mathop{\bf E\/}[fg]-\varepsilon$

Next, we apply Algorithm 3 to get a subset
$\mathcal{D}^{\prime}\subseteq\mathcal{D}$ to coordinates
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that with high probability

$\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime},k}}\mathop{\bf
E\/}[fg]\geq\max_{g\in\mathcal{J}_{\mathcal{S},k}}\mathop{\bf
E\/}[fg]-\varepsilon$

We take $\alpha$ to be the estimation of the correlation of the best junta on
$\mathcal{S}^{\prime}$ with $f$. By 2.7 we have that
$\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime}}}\mathop{\bf E\/}[fg]=\mathop{\bf
E\/}[|f_{\avg,\mathcal{S}^{\prime}}(x)|]$. To estimate the latter, we use a
randomized algorithm that computes $f_{\avg,\mathcal{S}^{\prime}}$ given by
Theorem 4.10. We randomly sample $O(1/\varepsilon^{2})$ many values for $x$
and estimate for each of them $|f_{\avg,\mathcal{S}^{\prime}}(x)|$ up to
additive error $\varepsilon/2$ via the randomized algorithm with expected
value $f_{\avg,\mathcal{S}^{\prime}}(x)$.

Assume that $\alpha$ is a $\varepsilon$-additive approximation to
$\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime}}}\mathop{\bf E\/}[fg]$. In this
case, we claim that $\alpha$ satisfies both items from the theorem’s
statement. Indeed,

  1. 1.

$\alpha\leq\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime}}}\mathop{\bf
E\/}[fg]+\varepsilon\leq\max_{g\in\mathcal{J}_{n,k^{\prime}}}\mathop{\bf
E\/}[fg]+\varepsilon$.

  2. 2.

$\alpha\geq\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime}}}\mathop{\bf
E\/}[fg]-\varepsilon\geq\max_{g\in\mathcal{J}_{\mathcal{S}^{\prime},k}}\mathop{\bf
E\/}[fg]-\varepsilon\geq\max_{g\in\mathcal{J}_{\mathcal{S},k}}\mathop{\bf
E\/}[fg]-2\varepsilon\geq\max_{g\in\mathcal{J}_{n,k}}\mathop{\bf
E\/}[fg]-3\varepsilon$.

Next, we analyze the number of queries of our algorithm. Obtaining the initial
set of coordinate oracles $\mathcal{D}$ takes
$\poly(k,1/\varepsilon,\log(1/\delta))=\poly(k,1/\varepsilon)$ queries. Then,
we go on to run Algorithm 3 that makes
$m=O((k+\log(1/\delta))/\varepsilon^{2})$ iterations, each making
$\poly(k,1/\varepsilon,\log(1/\delta))$ queries. Next, to estimate
$\mathop{\bf E\/}[|f_{\avg,\mathcal{S}^{\prime}}(x)|]$ we require
$\poly(1/\varepsilon)$ samples from randomized algorithm for
$f_{\avg,\mathcal{S}^{\prime}}(x)$ each such sample translate to
$\poly(k,1/\varepsilon)$ samples to $f$. Finally, we note that each “query” to
an oracle incurs an overhead of $\poly(\log(k,1/\varepsilon))$ queries to $f$
along with an $o(1)$ additive loss in confidence by Corollary 4.7. Overall, we
make $\poly(k,1/\varepsilon)$ queries. ∎

###  4.5 Proof of Theorem 4.11

We now present the proof of Theorem 4.11.

###### Proof of Theorem 4.11.

We express $\lambda_{i}$ in terms of the Fourier spectrum of $f$. Using 2.14,

$\displaystyle\lambda_{i}$ $\displaystyle=\sum_{m=0}^{\log(10k)}\sum_{S:S\ni
i}\widehat{f}(S)^{2}\cdot\mathop{\bf
Pr\/}_{J\subseteq_{2^{-m}}[{k^{\prime}}]}[S\cap J=\\{i\\}]$
$\displaystyle=\sum_{m=0}^{\log(10k)}\sum_{S:S\ni
i}\widehat{f}(S)^{2}\cdot\mathop{\bf
Pr\/}_{J\subseteq_{2^{-m}}[{k^{\prime}}]}[|S\cap J|=1]\cdot\frac{1}{|S|}$
$\displaystyle=\sum_{S:S\ni
i}\frac{\widehat{f}(S)^{2}}{|S|}\cdot\sum_{m=0}^{\log(10k)}\mathop{\bf
Pr\/}_{J\subseteq_{2^{-m}}[{k^{\prime}}]}[|S\cap J|=1]$

It therefore suffices to show that for any non-empty set $S$ such that
$|S|\leq k$ it holds that

$\frac{1}{2}\leq\sum_{m=0}^{\log(10k)}\mathop{\bf
Pr\/}_{J^{(m)}\subseteq_{2^{-m}}[{k^{\prime}}]}[|S\cap J^{(m)}|=1]\leq 2\;.$
(3)

From which it is clear that $\lambda_{i}\leq 2\cdot\sum_{S:S\ni
i}\frac{\widehat{f}(S)^{2}}{|S|}=2\cdot{\mathbf{NInf}}_{i}[f]$ and similarly
$\lambda_{i}\geq\frac{1}{2}\sum_{\begin{subarray}{c}S\ni i,\\\ |S|\leq
k\end{subarray}}\frac{\widehat{f}(S)^{2}}{|S|}=\frac{1}{2}{\mathbf{NInf}}_{i}^{\leq
k}[f]$.

We move to prove Equation 3. The first observation is that an equivalent way
to sample $J^{(m)}\subseteq_{2^{-m}}[{k^{\prime}}]$ is to sample $m$
independent set $J^{(m)}_{1},\ldots,J^{(m)}_{m}\subseteq_{1/2}[{k^{\prime}}]$
and take their intersection $J^{(m)}=J^{(m)}_{1}\cap\cdots\cap J^{(m)}_{m}$.
Furthermore, by linearity of expectation

$\sum_{m=0}^{\infty}\mathop{\bf
Pr\/}_{J^{(m)}\subseteq_{2^{-m}}[{k^{\prime}}]}[|S\cap
J|=1]=\sum_{m=0}^{\infty}\mathop{\bf
E\/}_{\begin{subarray}{c}J_{1}^{(m)}\subseteq_{1/2}[{k^{\prime}}],\\\
J_{2}^{(m)}\subseteq_{1/2}[{k^{\prime}}],\\\
\ldots\end{subarray}}\left[\mathbbm{1}_{|S\cap J_{1}^{(m)}\cap\cdots\cap
J_{m}^{(m)}|=1}\right]=\mathop{\bf
E\/}_{\begin{subarray}{c}J_{1}\subseteq_{1/2}[{k^{\prime}}],\\\
J_{2}\subseteq_{1/2}[{k^{\prime}}],\\\
\ldots\end{subarray}}\left[\sum_{m=0}^{\infty}\mathbbm{1}_{|S\cap
J_{1}\cap\cdots\cap J_{m}|=1}\right]$

which in essence means that the choices for $J_{1}^{(1)},J_{1}^{(2)},\ldots$
can be the same set $J_{1}$, and similarly for any $J_{i}$.

To analyze the latter expectation, we note that it can be described as the
expected value of the following random process:

1 $X\leftarrow 0$

2 for  _$i=1,2,\ldots,\log(10k)$_ do

3 if  _$S=\emptyset$_ then

4 halt!;

5 if  _$|S|=1$_ then

6 increment $X$;

7 Sample $J_{i}\subseteq_{1/2}[{k^{\prime}}]$;

8 $S\leftarrow S\cap J_{i}$;

9

It therefore suffices to show that the expected value of the above random
process is bounded in $[1/2,2]$. In the analysis, we consider also the
infinite horizon process that keeps on going until $S=\emptyset$. We observe
that the expected values of both processes depend only on the size of the
initial $S$ from symmetry. For any $t\in\\{0,1,\ldots,{k^{\prime}}\\}$, denote
by $F_{t}$ the expected value of the infinite horizon process starting with a
set $S$ of size $t$. For the finite horizon process with $i$ iterations, we
let the expected value be denoted by $F_{t}^{(i)}$. We observe that $F_{0}=0$,
and furthermore that $F_{1}=2$ since starting from a set of size $1$ the
random variable $X$ would behave like geometric random variable with $p=1/2$.
Similarly, $F_{1}^{(i)}=2-\frac{1}{2^{i-1}}$ as it is the minimum of $i$ and a
geometric random variable with $p=1/2$.

Furthermore, for the infinite horizon process, we observe that we have the
following recurrence

$F_{t}=\sum_{a=0}^{t}\frac{\binom{t}{a}}{2^{t}}\cdot F_{a},$

for $t\geq 2$ or equivalently

$F_{t}\cdot(1-2^{-t})=\sum_{a=0}^{t-1}\frac{\binom{t}{a}}{2^{t}}\cdot F_{a}.$

We show by induction that $1/2<F_{t}^{(\log 10k)}\leq 2$ for $t\geq 1$. The
base case $t=1$ was discussed above. Applying the induction hypothesis we have

$F_{t}\cdot(1-2^{-t})=\sum_{a=0}^{t-1}\frac{\binom{t}{a}}{2^{t}}\cdot
F_{a}\leq\sum_{a=0}^{t-1}\frac{\binom{t}{a}}{2^{t}}\cdot 2\leq(1-2^{-t})\cdot
2.$

Dividing both sides by $(1-2^{-t})$ gives the inequality $F_{t}\leq 2$, which
implies that $F_{t}^{(\log 10k)}\leq 2$.

For the lower bound, we consider the indicator random variable $Y_{t}^{(i)}$,
where $t=|S|$, which equals 1 if $|S|=1$ at some point during the above
process before iteration $i$. We note that $Y_{t}^{(\log 10k)}$ is a lower
bound for the value of $X$ in the finite horizon process, and $Y_{t}$ is a
lower bound for the value of $X$ at the end of the infinite horizon process.
First, we claim that $\mathop{\bf E\/}[Y_{t}]=\mathop{\bf Pr\/}[Y_{t}=1]\geq
2/3$ for all $t\geq 1$. The base case of $t=1$ is certainly true, and we also
have, similar to before, that

$\displaystyle\mathop{\bf E\/}[Y_{t}]\cdot(1-2^{-t})$
$\displaystyle=\sum_{a=0}^{t-1}\frac{\binom{t}{a}}{2^{t}}\mathop{\bf
E\/}[Y_{a}]$ $\displaystyle\geq
0\cdot\frac{1}{2^{t}}+1\cdot\frac{t}{2^{t}}+\frac{2}{3}\cdot\underbrace{\sum_{a=2}^{t-1}\frac{\binom{t}{a}}{2^{t}}}_{1-\frac{2+t}{2^{t}}}$
$\displaystyle=\frac{2}{3}+\frac{t-\frac{2}{3}(2+t)}{2^{t}}\geq\frac{2}{3}+\frac{t/3-4/3}{2^{t}}\geq\frac{2}{3}-\frac{2/3}{2^{t}}=\frac{2}{3}\cdot(1-2^{-t})$

which holds for all $t\geq 2$, and thus $\mathop{\bf Pr\/}[Y_{t}=1]\geq 2/3$.
However, this only holds for the infinite horizon random process. Let $A$ be
the event that $S=\emptyset$ by iteration $\log 10k$, and note that
$\mathop{\bf Pr\/}[A]=\mathop{\bf
Pr\/}[\textrm{Bin}(|S|,\frac{1}{10k})=0]\geq\mathop{\bf
Pr\/}[\textrm{Bin}(k,\frac{1}{10k})=0]=\left(1-\frac{1}{10k}\right)^{k}\geq
1-\frac{k}{10k}=0.9$. Finally, we claim that for all $t\geq 2$ we have that
$\mathop{\bf Pr\/}[Y_{t}^{(\log 10t)}]\geq 1/2$. Note that for $Y_{t}$ to
happen, it must be the case that either $\overline{A}$ happens or
$Y_{t}^{(\log 10t)}$ happens. Thus, by a union bound

$\displaystyle\tfrac{2}{3}\leq\mathop{\bf Pr\/}[Y_{t}=1]\leq\mathop{\bf
Pr\/}[Y_{t}^{(\log 10t)}=1]+\mathop{\bf Pr\/}[\overline{A}]\leq\mathop{\bf
Pr\/}[Y_{t}^{(\log 10t)}=1]+0.1\;,$

which implies $\mathop{\bf Pr\/}[Y_{t}^{(\log 10t)}=1]>1/2$. Finally,
$F_{t}^{(\log 10t)}\geq\mathop{\bf Pr\/}[Y_{t}^{(\log 10t)}=1]>1/2$ as
desired. ∎

##  5 A $2^{\tilde{O}(\sqrt{k})}$-query Tolerant Junta Tester

In this section, we prove Theorem 1.2. Throughout this section, we assume that
we already applied Algorithm 3 to reduce the number of coordinate oracles to
$O(k/\varepsilon^{2})$. We denote by $\mathcal{D}$ the set of oracles we get,
and by $\mathcal{S}\subseteq[n]$ the set of coordinate to which they are
oracles to. Suppose that the best $k$-junta approximation of $f$ is a junta-
on-$T$, for a set $T\subseteq\mathcal{S}$ of size $k$. We call $T$ the “target
set”. Note that $T$ is unknown to the algorithm, and in fact, identifying $T$
(or a close approximation to $T$) from all subsets of size $k$ of
$\mathcal{S}$ is the crux of the problem.

We start with the observation that if we were somehow able to identify all of
the variables of $T$ that capture most of the Fourier mass above level
$\kappa$, then we could simply restrict $f$ by randomly fixing these
variables, leaving us with the task of identifying the best $k$-junta
approximation of $f$, given that we know the best $k$-junta has most its
Fourier mass below level $\kappa$. For the latter case, there are only
$\binom{|\mathcal{S}|}{\kappa}$ Fourier coefficients to estimate, and
estimating these to sufficient accuracy allows one to estimate the the
correlation $f$ has with any subset $U\subseteq\mathcal{S}$ such that $|U|\leq
k$.

We are now ready to present the details of the algorithm. The algorithm can be
broken down into two main steps. First, we find, with high probability, a set
$B\subseteq T$ that captures almost all Fourier mass of $T$ above level
$\kappa$. This first step, which we call “phase one”, closely resembles the
techniques in Section 4 in that we utilize a series of random restrictions to
estimate normalized influences. The main difference is that rather than
considering normalized influences of individual coordinates, we now consider
normalized influences of sets of size $\kappa$. The goal of phase one is to
produce at least one subset $B$ of our target set $T$ which effectively
captures most of the Fourier mass within $T$ above level $\kappa$. Once we
have done that, we have reduced to the scenario of the closest $k$-junta to
$f$ having most of its Fourier mass below level $\kappa$, which can be solved
via estimating all of the Fourier coefficients below level $\kappa$.

###  5.1 Phase One: The Higher Levels

First, we prove an analogous theorem to Theorem 4.11, which relates
$\lambda_{U}[f]$ to ${\mathbf{NInf}}_{U}[f]$ for all $U$:

######  Theorem 5.1.

Let $f:\\{\pm 1\\}^{\ell}\to\mathbb{R}$. Let $U\subseteq[\ell]$, where
$\ell=|\mathcal{D}|$ and $|U|\leq k$. Let

$\lambda_{U}[f]=\sum_{m=0}^{2|U|\log(10k)}\lambda_{U}^{\approx
p^{-m}}[f],\qquad\text{where}\qquad\lambda_{U}^{\approx p^{-m}}[f]=\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{p^{m}}}[\widehat{f_{\bar{J}\to z}}(U)^{2}]$

for $p=1-\frac{1}{2|U|}$. Then, $\frac{1}{2}\cdot{\mathbf{NInf}}_{U}^{\leq
k}[f]\leq\lambda_{U}[f]\leq 3\cdot{\mathbf{NInf}}_{U}[f]$.

Again, we postpone the proof of this to the end of this section in Section
5.3. The definition of $\lambda_{U}[f]$ is naturally algorithmic, and
therefore we can design the following algorithm to approximate the values of
$\lambda_{U}[f]$ for all sets $U$ of size $\kappa=\sqrt{\varepsilon k}$.

Input: $f:\\{\pm 1\\}^{k^{\prime}}\to[-1,1]$ along with a randomized algorithm
A computing $f$ (recall Def. 2.10). Parameters $1-\delta$ (confidence),
$\varepsilon$ (additive error) and $k$.

Output: Estimates $\\{\tilde{\lambda}_{U}\\}_{|U|=\kappa}$ for
$\\{\lambda_{U}\\}_{|U|=\kappa}$.

1 Let $m=\poly(k,k^{\prime},1/\varepsilon,\log(1/\delta))$

2 Initialize $\widetilde{\lambda}_{U}=0$ for all $U\subseteq[k^{\prime}]$,
$|U|=\kappa=\sqrt{\varepsilon k}$

3 Let $p=\left(1-\frac{1}{2\kappa}\right)$

4 for  _$d=0$ to $2\kappa\log 10k$_ do

5 Initialize $\widetilde{\lambda}_{U}^{\approx p^{-d}}=0$ for all
$U\subseteq[k^{\prime}]$ such that $|U|=\kappa$

6

7 repeat  _$m$_ times

8 Let $(J,z)\sim\mathcal{R}_{p^{d}}$ be a $p^{d}$-random restriction.

9

10 Estimate $\widehat{f_{\bar{J}\to z}}(U)$ for all $U\subseteq J$ of size
$\kappa$ up to additive error $\frac{\varepsilon}{12\kappa\log(10k)}$ with
probability $1-\frac{\delta}{\binom{k^{\prime}}{\kappa}m\cdot
2\kappa\log(10k)}$ using 2.11 and algorithm A. Denote by
$\widetilde{f_{\bar{J}\to z}}(U)$ the estimated Fourier coefficient.

11 Update $\widetilde{\lambda}_{U}^{\approx
p^{-d}}=\widetilde{\lambda}_{U}^{\approx p^{-d}}+\widetilde{f_{\bar{J}\to
z}}(U)^{2}$ for all $U\subseteq J$ of size $\kappa$.

12 Let $\widetilde{\lambda}_{U}^{\approx
p^{-d}}=\widetilde{\lambda}_{U}^{\approx p^{-d}}/m$ for all $U\subseteq J$ of
size $\kappa$;

13Let $\widetilde{\lambda}_{U}=\sum_{d}\widetilde{\lambda}_{U}^{\approx
p^{-d}}$;

return _$\\{\tilde{\lambda}_{U}\\}_{|U|=\kappa}$_

Algorithm 4 Estimating $\lambda_{U}$’s

######  Lemma 5.2.

With probability at least $1-\delta$ we have that for all
$U\subseteq[k^{\prime}]$ of size $\kappa$ it holds that
$|\widetilde{\lambda}_{U}-\lambda_{U}[f]|\leq\varepsilon$.

###### Proof.

This proof closely follows that of Lemma 4.12. If $U\not\subseteq J$ the
Fourier coefficient of $\widehat{f_{\bar{J}\to z}}(U)$ is $0$ and so our
estimate is correct in that case. In the case $U\subseteq J$, each estimation
of the Fourier coefficient is correct up to additive error
$\eta=\frac{\varepsilon}{12\kappa\log(10k)}$ with probability at least
$1-\delta/\exp(k,k^{\prime},m)$. Thus, we get that $\widetilde{f_{\bar{J}\to
z}}(U)^{2}=(\widehat{f_{\bar{J}\to z}}(U)\pm\eta)^{2}=\widehat{f_{\bar{J}\to
z}}(U)^{2}\pm 2\eta|\widehat{f_{\bar{J}\to
z}}(U)|\pm\eta^{2}=\widehat{f_{\bar{J}\to z}}(U)^{2}\pm 3\eta$. Furthermore,
we have that $\mathop{\bf
E\/}_{(J,z)\sim\mathcal{R}_{p^{d}}}[\widehat{f_{\bar{J}\to
z}}(U)^{2}]=\lambda_{U}^{\approx p^{-d}}$, thus by 2.1 we have that the
empirical mean of
$m=\poly(1/\varepsilon,\poly(k),\poly(k^{\prime}),\log(1/\delta))$ copies of
$\widetilde{f_{\bar{J}\to z}}(U)^{2}$ is within additive error
$\varepsilon/(4\kappa\log(10k))$ from $\lambda_{U}^{\approx p^{-d}}$ with
probability at least $1-\frac{\delta}{\binom{k^{\prime}}{\kappa}m\cdot
2\kappa\log(10k)}$. By union bound, all these estimates are within the error
bound, and we get that

$\left|\widetilde{\lambda}_{U}^{\approx p^{-d}}-\lambda_{U}^{\approx
p^{-d}}\right|\leq
3\eta+\varepsilon/(4\kappa\log(10k))\leq\varepsilon/(2\kappa\log(10k)).$

Overall, we get that $|\widetilde{\lambda}_{U}-\lambda_{U}[f]|\leq\varepsilon$
for all $|U|=\kappa$ with probability at least $1-\delta$. ∎

Since we are sampling sets of size $\kappa$, we need to sample at most
$k/\kappa=\sqrt{k/\varepsilon}=:\alpha$ distinct subsets of $T$ of size
$\kappa$ in order to capture all the potential mass of $T$ above level
$\kappa$.

1

Input: $f$ (target function), $\mathcal{D}$ (where $\mathcal{D}$ are
coordinate oracles for $\mathcal{S}$) a current depth $t$, a current subset
$\mathcal{D}^{\prime}\subseteq\mathcal{D}$ of coordinate oracles,
$\varepsilon$, $\delta$

Output: Return collection of subsets of $\mathcal{D}$ of size at most $k$.

2 Let $\alpha=k/\kappa=\sqrt{k/\varepsilon}$

3 Let $r=O(1/\varepsilon^{2})$ and $\ell=2(r+1)^{3\alpha+\log(2/\delta)}$

/* $r+1$ is the branching factor, and $\ell$ is an upper bound on the number
of nodes in the branching process (the process depth is
$3\alpha+\log(2/\delta)$). */

4 if  _$t=3\alpha+\log(2/\delta)$ or $|\mathcal{D}^{\prime}|>k-\kappa$_ then

5 return _$\\{\mathcal{D}^{\prime}\\}$_

6Let $\\{g_{1},...,g_{k^{\prime}}\\}=\mathcal{D}-\mathcal{D}^{\prime}$ and
$\\{g_{k^{\prime}+1},...,g_{|\mathcal{D}|}\\}$ where
$k^{\prime}=|\mathcal{D}|-|\mathcal{D}^{\prime}|$

7 Sample $z\in\\{\pm 1\\}^{|\mathcal{D}^{\prime}|}$. Let $f^{\prime}:\\{\pm
1\\}^{k^{\prime}}\to\mathbb{R}$ be the function defined by
$f^{\prime}(x_{1},\ldots,x_{k^{\prime}})=\mathop{\bf E\/}_{y\sim\\{\pm
1\\}^{n}}[f(y)|g_{1}(y)=x_{1},\ldots,g_{k^{\prime}}(y)=x_{k^{\prime}},g_{k^{\prime}+1}(y)=z_{1},\ldots,g_{|\mathcal{D}|}(y)=z_{|\mathcal{D}^{\prime}|}],$
and let A be the randomized algorithm for $f^{\prime}$ from Theorem 4.10.

8Apply Algorithm 4 on $f^{\prime}$ using the randomized algorithm A for
$f^{\prime}$ with confidence $1-\frac{\delta}{2\ell}$ and accuracy
$\frac{\varepsilon^{2}}{48\cdot\binom{|\mathcal{D}|}{\kappa}}$
$\implies\widetilde{\lambda}=\\{\widetilde{\lambda}_{U}\\}_{|U|=\kappa}$.

9 Let our distribution $P$ be defined by $\widetilde{\lambda}$, normalized
appropriately

10 Sample $M_{1},...,M_{r}\sim\tilde{\lambda}$

11

12Let $\mathcal{L}=\\{\\}$.

13 for  _$M=\emptyset,M_{1},...,M_{r}$_ do

14
$\mathcal{L}=\mathcal{L}\cup\text{BranchingProcess}(f,\mathcal{D},t+1,\mathcal{D}^{\prime}\cup\\{g_{i}:i\in
M\\},\varepsilon,\delta)$

15return _$\mathcal{L}$_

Algorithm 5 Branching Process

######  Lemma 5.3.

With probability at least $1-\delta$, at least one of the subsets Algorithm 5
returns is a set of coordinate oracles to $B\subseteq T$ such that

$\mathop{\bf E\/}_{z}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq T\setminus
B\\\ |S|>\kappa\end{subarray}}\widehat{f_{B\to
z}}(S)^{2}\Bigg{]}\leq\varepsilon^{2}/4.$ (4)

The reason for Equation 4 becomes clear in Section 5.2, where we show that
assuming the inequality, we lose at most an additive error of $\varepsilon/2$
to the nearest $k$-junta if we ignore the Fourier mass above level $\kappa$
after restricting $B$. As before, in order to prove the above lemma, we prove
a claim capturing the algorithm’s progress towards satisfying Equation 4.

We denote the event $\mathcal{E}$ that in the entire execution of Algorithm 5
all of the $\widetilde{\lambda}_{U}$ were
$\varepsilon^{2}/48\cdot\binom{|\mathcal{D}|}{\kappa}$ close to the real
$\lambda_{U}$. We note that by a union bound, this happens with probability at
least $1-\delta/2$.

Suppose again that $T$ is the (unknown) set of $k$ coordinates for which the
best $k$-junta approximating $f$ is a junta on $T$. If $T$ has Fourier mass
less than $\varepsilon^{2}/4$ above level $\kappa$ then one of the subsets
that Algorithm 5 will return is the empty set, which satisfies the claim.
Therefore, henceforth we assume that $T$ has at least $\varepsilon^{2}/4$
Fourier mass above level $\kappa$. We show that in such a case, each $M_{i}$
for $i=1,\ldots,r$ will be a subset of $T$ with probability at least
$\Omega(\varepsilon^{2})$.

######  Claim 5.4.

Assume $\mathcal{D}^{\prime}$ are coordinate oracles to
$\mathcal{S}^{\prime}\subseteq T$. Suppose also that

$\mathop{\bf E\/}_{z}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq
T\setminus\mathcal{S}^{\prime}\\\
|S|>\kappa\end{subarray}}\widehat{f_{\mathcal{S}^{\prime}\to
z}}(S)^{2}\Bigg{]}>\varepsilon^{2}/4.$

Then, conditioned on $\mathcal{E}$, when running the Branching Process on
$\mathcal{D}^{\prime}$, each $M_{i}$ will be with probability at least
$\varepsilon^{2}/40$ a collection of $\kappa$ new coordinate oracles to
coordinates in $T$.

###### Proof.

Similar to the proof of 4.14, denote by
$f_{z}=(f_{\avg,\mathcal{S}})_{\mathcal{S}^{\prime}\to z}$, and note that
$f^{\prime}$ is up to relabeling of coordinates the same function as $f_{z}$.
Denote $V\subseteq T$ as the part of the target set we have not yet sampled,
so $V=T\setminus\mathcal{S}^{\prime}$. Then, using our assumption, we have
that

$\displaystyle\varepsilon^{2}/4$ $\displaystyle<\mathop{\bf
E\/}_{z}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|>\kappa\end{subarray}}\widehat{f_{\mathcal{S}^{\prime}\to
z}}(S)^{2}\Bigg{]}$ $\displaystyle=\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|>\kappa\end{subarray}}\;\;\sum_{\begin{subarray}{c}R\subseteq[n]:\\\
R\cap\overline{\mathcal{S}^{\prime}}=S\end{subarray}}\widehat{f}(R)^{2}$
(2.14) $\displaystyle=\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|>\kappa\end{subarray}}\;\;\sum_{\begin{subarray}{c}R\subseteq\mathcal{S}:\\\
R\cap\overline{\mathcal{S}^{\prime}}=S\end{subarray}}\widehat{f}(R)^{2}$ (if
$R\not\subseteq\mathcal{S}$ then $R\cap\overline{\mathcal{S}^{\prime}}\neq S$
) $\displaystyle=\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|>\kappa\end{subarray}}\;\;\sum_{\begin{subarray}{c}R\subseteq\mathcal{S}:\\\
R\cap\overline{\mathcal{S}^{\prime}}=S\end{subarray}}\widehat{f_{\avg,\mathcal{S}}}(R)^{2}$
$\displaystyle=\mathop{\bf E\/}_{z}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq
V\\\ |S|>\kappa\end{subarray}}\widehat{f_{z}}(S)^{2}\Bigg{]}.$

Next, by applying Theorem 5.1, we have that

$\displaystyle\sum_{\begin{subarray}{c}U\subseteq V\\\
|U|=\kappa\end{subarray}}\lambda_{U}[f_{z}]$
$\displaystyle\geq\frac{1}{2}\sum_{U\subseteq V}{\mathbf{NInf}}_{U}^{\leq
k}[f_{z}]\geq\frac{1}{2}\sum_{U\subseteq V:|U|=\kappa}\;\sum_{S:U\subseteq
S\subseteq
V}\frac{\widehat{f_{z}}(S)^{2}}{\binom{|S|}{|U|}}=\frac{1}{2}\sum_{\begin{subarray}{c}|S|>\kappa\\\
S\subseteq V\end{subarray}}\widehat{f_{z}}(S)^{2}$

Then, using the assumption that $\mathcal{E}$ happens, the
$\widetilde{\lambda_{U}}$ are
$\frac{\varepsilon^{2}}{48\cdot\binom{|\mathcal{S}|}{\kappa}}$-accurate, and
we get that

$\sum_{\begin{subarray}{c}U\subseteq V\\\
|U|=\kappa\end{subarray}}\tilde{\lambda_{U}}[f_{z}]\geq\frac{1}{2}\sum_{\begin{subarray}{c}|S|>\kappa\\\
S\subseteq
V\end{subarray}}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48\cdot\binom{|\mathcal{S}|}{\kappa}}\cdot\binom{k}{\kappa}\geq\frac{1}{2}\sum_{\begin{subarray}{c}|S|>\kappa\\\
S\subseteq V\end{subarray}}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48}.$

On the other hand, again by applying Theorem 5.1, we have that

$\sum_{\begin{subarray}{c}U\subseteq\mathcal{S}\\\
|U|=\kappa\end{subarray}}\lambda_{U}[f_{z}]\leq
3\sum_{\begin{subarray}{c}U\subseteq\mathcal{S}\\\
|U|=\kappa\end{subarray}}{\mathbf{NInf}}_{U}[f_{z}]\leq
3\mathbf{W}^{\geq\kappa}[f_{z}]\leq 3.$

This implies that $\sum_{U}\widetilde{\lambda_{U}}\leq
3+\frac{\varepsilon^{2}}{48\cdot\binom{|\mathcal{S}|}{\kappa}}\cdot\binom{|\mathcal{S}|}{\kappa}\leq
4$. Overall, the probability to sample $U\subseteq V$ is at least

$\frac{1}{4}\left(\frac{1}{2}\sum_{\begin{subarray}{c}|S|>\kappa\\\ S\subseteq
V\end{subarray}}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{48}\right)=\frac{1}{8}\sum_{\begin{subarray}{c}|S|>\kappa\\\
S\subseteq
V\end{subarray}}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{4\cdot 48}.$

Taking an expectation over $z$, we see that the probability to sample a subset
of $V$ is at least

$\mathop{\bf E\/}_{z}\Bigg{[}\frac{1}{8}\sum_{\begin{subarray}{c}|S|>\kappa\\\
S\subseteq
V\end{subarray}}\widehat{f_{z}}(S)^{2}-\frac{\varepsilon^{2}}{4\cdot
48}\Bigg{]}\geq\frac{1}{8}\cdot\frac{\varepsilon^{2}}{4}-\frac{\varepsilon^{2}}{4\cdot
48}\geq\frac{\varepsilon^{2}}{40}.\qed$

We are now ready to prove Lemma 5.3.

###### Proof of Lemma 5.3.

By 5.4, if our special set $T$ has at least $\varepsilon^{2}/4$ mass on the
levels above $\kappa$, then if we sample according to our distribution
$\widetilde{\lambda}=\\{\widetilde{\lambda}_{U}\\}_{|U|=\kappa}$, we will see
$U\subseteq T$ with probability at least $\varepsilon^{2}/40$. Then, if we
sample $r=O(\varepsilon^{-2})$ subsets in Algorithm 5, applying the
multiplicative Chernoff bound in 2.1, we see at least one subset of $T$ with
probability at least $p\geq 0.9$ each time we sample $M_{1},...,M_{r}$ in
Algorithm 5. In order for Algorithm 5 to successfully find $B_{i}$ with the
desired property, it suffices to have sampled from $T$ at least $\alpha$ times
in our branching process. Therefore, we can treat our
$N:=(3\alpha+\log(2/\delta))$ depth branching process as a
$X=\textrm{Bin}(N,p)$ random variable. Applying a standard Chernoff bound
(second case in 2.1), we have that our probability of failure is

$\displaystyle\mathop{\bf Pr\/}[X<\alpha]=$ $\displaystyle\mathop{\bf
Pr\/}[\overline{X}<\tfrac{\alpha}{N}]$ $\displaystyle=$
$\displaystyle\mathop{\bf Pr\/}[\overline{X}<0.9-(0.9-\tfrac{\alpha}{N})]$
$\displaystyle\leq$ $\displaystyle\exp(-2N(0.9-\tfrac{\alpha}{N})^{2})$ (Using
2.1) $\displaystyle\leq$ $\displaystyle\exp(-2N(0.81-2\tfrac{\alpha}{N}))$
$\displaystyle\leq$ $\displaystyle\exp(-1.5N+4\alpha)$ $\displaystyle\leq$
$\displaystyle\exp(-\log(2/\delta))=\delta/2.$

This shows that, by a union bound with event $\mathcal{E}$, one of the
branches of our algorithm find’s a $B_{i}$ satisfying Equation 4 with
probability at least $1-\delta$. ∎

######  Claim 5.5.

The query complexity of phase one of the algorithm for constant $\delta$
(failure probability) is $2^{\widetilde{O}(\sqrt{k/\varepsilon})}$.

###### Proof.

All of our queries to $f$ in phase one come from estimating fourier
coefficients using 2.11 in Algorithm 4. We require that the estimated Fourier
coefficients be accurate to within $1/\poly(k,1/\varepsilon)$ with confidence
$1-O(1/\ell)=1-2^{-\widetilde{\Omega}(\sqrt{k/\varepsilon})}$, which is
possible via 2.1 with query complexity $\poly(k/\varepsilon)$. However, we do
this $O(\ell)=2^{\widetilde{O}(\sqrt{k/\varepsilon}})$ times during the
branching process, which yields the final overall query complexity. ∎

###  5.2 Phase Two: The Lower Levels

Now, we are ready to use Algorithm 5. Our strategy will be to take the subsets
outputted from Algorithm 5 one at time, randomly fixing those coordinates, and
then treating this restricted version of $f$ as if all its Fourier mass were
below level $\kappa$ (recall that $\kappa=\sqrt{\varepsilon k}$). Let $T$ be
the target set of size $k$ on which there exists a $k$-junta which best
approximates $f$. Assume that the first part of the algorithm is successful in
yielding at least one $B\subseteq T$ such that:

$\mathop{\bf E\/}_{z\in\\{\pm
1\\}^{B}}\Bigl{[}\sum_{\begin{subarray}{c}S\subseteq T\setminus B\\\
|S|>\kappa\end{subarray}}\widehat{f_{B\to
z}}(S)^{2}\Bigr{]}\leq\varepsilon^{2}/4.$ (5)

Let $g$ be the maximizer of $\max_{g^{\prime}\in\mathcal{J}_{T}}\mathop{\bf
E\/}[fg^{\prime}]$. Recall that by 2.7 we have that $g=\sgn(f_{\avg,T})$ and

$\displaystyle\mathsf{corr}(f,\mathcal{J}_{T})=\mathop{\bf
E\/}[fg]=\mathop{\bf E\/}_{y\in\\{\pm 1\\}^{T}}[|f_{\avg,T}(y)|]$
$\displaystyle=\mathop{\bf E\/}_{z\in\\{\pm 1\\}^{B}}\mathop{\bf
E\/}_{x\in\\{\pm 1\\}^{T\setminus B}}\bigg{|}(f_{\avg,T})_{B\to z}(x)\bigg{|}$
(6) $\displaystyle=\mathop{\bf E\/}_{z\in\\{\pm 1\\}^{B}}\mathop{\bf
E\/}_{x\in\\{\pm 1\\}^{T\setminus B}}\bigg{|}\sum_{S\subseteq T\setminus
B}\widehat{f_{B\to z}}(S)\chi_{S}(x)\bigg{|}$ (7)

Furthermore, using the assumption in Eq. (5) it is an easy calculation to show
that (7) equals

$\mathop{\bf E\/}_{z\in\\{\pm 1\\}^{B}}\mathop{\bf E\/}_{x\in\\{\pm
1\\}^{T\setminus B}}\bigg{|}\sum_{S\subseteq T\setminus
B,|S|\leq\kappa}\widehat{f_{B\to z}}(S)\chi_{S}(x)\bigg{|}\pm\varepsilon/2.$

Similarly, for any set $U\subseteq\mathcal{S}$ of size $k$ containing $B$
(think of $U$ as a candidate for $T$) we have that the best correlation
between a junta-on-$U$ and $f$ is

$\mathsf{corr}(f,\mathcal{J}_{U})=\mathop{\bf E\/}_{z\in\\{\pm
1\\}^{B}}\mathop{\bf E\/}_{x\in\\{\pm 1\\}^{U\setminus
B}}\bigg{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\bigg{|}.$ (8)

Now, however, the right hand side in Eq. (8) is not necessarily approximated
by the low-degree counterpart as above for $T$. Indeed, we would like to
estimate Eq. (8) for all candidates $U\subseteq\mathcal{S}$ of size $k$
containing $B$, and pick the set with best estimated correlation. Based on our
assumption on $T$, we can replace $\sum_{S\subseteq U\setminus
B}\widehat{f_{B\to z}}(S)\chi_{S}(x)$ with its low-degree part
$\sum_{S\subseteq U\setminus B,|S|\leq\kappa}\widehat{f_{B\to
z}}(S)\chi_{S}(x)$ for $U=T$, but its not clear whether we can do it in
general.

In particular, if $U$ satisfies

$\mathop{\bf E\/}_{z\in\\{\pm
1\\}^{B}}\Bigl{[}\sum_{\begin{subarray}{c}S\subseteq U\setminus B,\\\
|S|>\kappa\end{subarray}}\;\widehat{f_{B\to
z}}(S)^{2}\Bigr{]}>\varepsilon^{2}/4,$ (9)

then taking the low-degree part can give an overestimate to the correlation
with the best junta on $U$.555To see a simple example of how this can happen,
consider $f(x,y)=1-x-y+xy$. Then one can verify that $\mathop{\bf
E\/}[|f(x,y)|]=1<1.5=\mathop{\bf E\/}[|1-x-y|]$. We settle for an estimate
that is $\varepsilon$-accurate for the target set $T$ assuming it satisfies
Equation 5, and is not overestimating by more than $\varepsilon$ for any other
set $U\supseteq B$ of size $k$. Towards this goal, we first apply a noise
operator that would essentially eliminate most of the contribution from sets
larger than $\sqrt{k/\varepsilon}\log(1/\varepsilon)$ regardless of whether
$U$ satisfies Eq. (15) or not. This is captured by the following claim.

######  Claim 5.6.

Let $\rho=1-\sqrt{\varepsilon/k}$, $z\in\\{\pm 1\\}^{B}$ and denote by
$h=f_{B\to z}$ and
$h^{\mathsf{low}}=h^{\leq(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)}$
(i.e., $h^{\mathsf{low}}$ is the truncated Fourier expansion of $h$ that
zeroes out all Fourier coefficients above level
$(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)$). For any $U:B\subseteq
U\subseteq\mathcal{S}$ it holds that

$\bigg{|}\mathsf{corr}\left(T_{\rho}h,\mathcal{J}_{U}\right)-\mathsf{corr}\left(T_{\rho}h^{\mathsf{low}},\mathcal{J}_{U}\right)\bigg{|}\leq\varepsilon.$

###### Proof.

We have

$\displaystyle\bigg{|}\mathsf{corr}\left(T_{\rho}h,\mathcal{J}_{U}\right)-\mathsf{corr}\left(T_{\rho}h^{\mathsf{low}},\mathcal{J}_{U}\right)\bigg{|}$
$\displaystyle=\Bigg{|}\mathop{\bf E\/}_{\begin{subarray}{c}x\in\\{\pm
1\\}^{U\setminus B}\end{subarray}}\Big{|}\sum_{S\subseteq U\setminus
B}\widehat{h}(S)\chi_{S}(x)\rho^{S}\Big{|}\;-\;\mathop{\bf
E\/}_{\begin{subarray}{c}x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{\begin{subarray}{c}S\subseteq U\setminus B,\\\
|S|\leq(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)\end{subarray}}\widehat{h}(S)\chi_{S}(x)\rho^{S}\Big{|}\Bigg{|}$
$\displaystyle\leq\mathop{\bf E\/}_{\begin{subarray}{c}x\in\\{\pm
1\\}^{U\setminus B}\end{subarray}}\Bigg{|}\sum_{\begin{subarray}{c}S\subseteq
U\setminus B,\\\
|S|>(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)\end{subarray}}\widehat{h}(S)\chi_{S}(x)\rho^{|S|}\Bigg{|}$
$\displaystyle\leq\sqrt{\mathop{\bf E\/}_{\begin{subarray}{c}x\in\\{\pm
1\\}^{U\setminus B}\end{subarray}}\Bigg{(}\sum_{\begin{subarray}{c}S\subseteq
U\setminus B,\\\
|S|>(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)\end{subarray}}\widehat{h}(S)\chi_{S}(x)\rho^{|S|}\Bigg{)}^{2}}$
$\displaystyle=\sqrt{\sum_{\begin{subarray}{c}S\subseteq U\setminus B,\\\
|S|>(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)\end{subarray}}\widehat{h}(S)^{2}\rho^{2|S|}}\leq\sqrt{\rho^{2(\sqrt{k/\varepsilon})\cdot\log(1/\varepsilon)}}\leq\varepsilon.\qed$

Next, we show that applying a noise operator to $f$ does not affect its
correlation with a set $U$ of size $k$, under the condition that most of the
Fourier mass of $f_{B\to z}$ falls on the lower levels, i.e., $\mathop{\bf
E\/}_{z}\Bigl{[}\sum_{\begin{subarray}{c}S\subseteq U\setminus
B,|S|\geq\sqrt{k}\end{subarray}}\;\widehat{f_{B\to
z}}(S)^{2}\Bigr{]}\leq\varepsilon^{2}/4.$ Recall that this is what was
guaranteed with high probability from the output of Algorithm 5 for our target
set $T$.

######  Claim 5.7.

Let $\rho=1-\sqrt{k/\varepsilon}$. Given $U:B\subseteq U\subseteq\mathcal{S}$
such that $\mathop{\bf E\/}_{z}\Bigl{[}\sum_{\begin{subarray}{c}S\subseteq
U\setminus B,\\\ |S|\geq\kappa\end{subarray}}\;\widehat{f_{B\to
z}}(S)^{2}\Bigr{]}\leq\varepsilon^{2}/4,$ we have that

$\left|\mathop{\bf E\/}_{z}\mathsf{corr}(T_{\rho}(f_{B\to
z}),\mathcal{J}_{U})-\mathop{\bf E\/}_{z}\mathsf{corr}(f_{B\to
z},\mathcal{J}_{U})\right|\leq 1.2\varepsilon.$

###### Proof.

Similar to the proof of 5.6, we have

$\displaystyle\Bigg{|}\mathop{\bf E\/}_{\begin{subarray}{c}z\in\\{\pm
1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\Big{|}\;-\;\mathop{\bf E\/}_{\begin{subarray}{c}z\in\\{\pm
1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{\begin{subarray}{c}S\subseteq U\setminus
B\end{subarray}}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\cdot\rho^{|S|}\Big{|}\Bigg{|}$ $\displaystyle\leq\mathop{\bf
E\/}_{\begin{subarray}{c}z\in\\{\pm 1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Bigg{|}\sum_{\begin{subarray}{c}S\subseteq U\setminus
B\end{subarray}}\widehat{f_{B\to z}}(S)\chi_{S}(x)(1-\rho^{|S|})\Bigg{|}$
$\displaystyle\leq\sqrt{\mathop{\bf E\/}_{\begin{subarray}{c}z\in\\{\pm
1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\left(\sum_{\begin{subarray}{c}S\subseteq U\setminus
B\end{subarray}}\widehat{f_{B\to z}}(S)\chi_{S}(x)(1-\rho^{|S|})\right)^{2}}$
$\displaystyle=\sqrt{\mathop{\bf E\/}_{z\in\\{\pm
1\\}^{B}}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq U\setminus
B\end{subarray}}\widehat{f_{B\to z}}(S)^{2}\cdot(1-\rho^{|S|})^{2}\Bigg{]}}$
$\displaystyle\leq\sqrt{\mathop{\bf E\/}_{z\in\\{\pm
1\\}^{B}}\Bigg{[}\sum_{\begin{subarray}{c}S\subseteq U\setminus
B:|S|\leq\kappa\end{subarray}}\widehat{f_{B\to
z}}(S)^{2}\cdot(1-\rho^{|S|})^{2}+\sum_{\begin{subarray}{c}S\subseteq
U\setminus B:|S|>\kappa\end{subarray}}\widehat{f_{B\to
z}}(S)^{2}\cdot(1-\rho^{|S|})^{2}\Bigg{]}}$
$\displaystyle\leq\sqrt{(1-\rho^{\kappa})^{2}+\varepsilon^{2}/4}\leq\sqrt{\varepsilon^{2}+\varepsilon^{2}/4}\leq
1.2\cdot\varepsilon.\qed$

The next lemma gives an algorithm that on any $B$, satisfying Equation 5,
outputs $U:B\subseteq U\subseteq\mathcal{S}$ with
$\mathsf{corr}(f,\mathcal{J}_{U})\geq\mathsf{corr}(f,\mathcal{J}_{T})-O(\varepsilon)$,
with high probability.

######  Lemma 5.8 (Algorithm and Analysis for Phase-Two).

Let $\varepsilon,\delta>0$. There’s an algorithm that with probability at
least $1-\delta$, gives $\varepsilon$-accurate estimates $\widetilde{c_{U}}$
to

${c_{U}}=\mathop{\bf E\/}_{z\in\\{\pm 1\\}^{B}}\mathop{\bf E\/}_{x\in\\{\pm
1\\}^{T\setminus B}}\bigg{|}\sum_{S\subseteq U\setminus
B:|S|\leq\sqrt{k/\varepsilon}\cdot\log(1/\varepsilon)}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\rho^{|S|}\bigg{|}$

for all $U:B\subseteq U\subseteq\mathcal{S}$ of size $k$ simultaneously. We
return $(U,\widetilde{c_{U}})$ for the set $U$ with maximal
$\widetilde{c_{U}}$.

Complexity

The procedure uses $\log(1/\delta)2^{\widetilde{O}(\sqrt{k/\varepsilon})}$
queries and runs in time
$\log(1/\delta)2^{k\cdot\widetilde{O}(1/\varepsilon)}$.

Correctness

In the case where all estimates are $\varepsilon$-accurate, the following
holds. If $B\subseteq T$ satisfies Equation 5, the above procedure would
return $(U,\widetilde{c_{U}})$ with
$\widetilde{c_{U}}\geq\mathsf{corr}(f,\mathcal{J}_{T})-3.2\varepsilon$.
Moreover, regardless of whether $T$ and $B$ satisfy Equation 5, we have
$\widetilde{c_{U}}\leq\mathsf{corr}(f,\mathcal{J}_{U})+2\varepsilon$.

###### Proof.

First we show that we can estimate all ${c_{U}}$ up to error $\varepsilon$
simultaneously with high probability using the aforementioned query complexity
and running time. We sample $t=O(\log(1/\delta)/\varepsilon^{2})$ different
$z\in\\{\pm 1\\}^{B}$, and estimate for each value of $z$ the Fourier
coefficients of $\widehat{f_{B\to z}}(S)$ of all sets $S\subseteq\mathcal{S}$
of size at most $\zeta=\sqrt{k/\varepsilon}\cdot\log(\tfrac{2}{\varepsilon})$
up to additive error
$\varepsilon/\binom{k}{\leq\zeta}=2^{-\widetilde{\Omega}(\sqrt{k/\varepsilon})}$
with probability $1-\frac{\delta}{t\cdot\binom{k}{\leq\zeta}}$, which is
possible via 2.1 with $\log(1/\delta)2^{\widetilde{O}(\sqrt{k/\varepsilon})}$
queries. 2.1 guarantees that with probability $1-\delta$ for all sampled $z$,
all estimated low-degree Fourier coefficients are within the additive error
bound, in which case we have estimates for all $c_{U}$ up to error
$\varepsilon$ simultaneously with probability $1-\delta$.

Next, we show the correctness of the procedure. On the one hand, in the
assumed case, i.e., that $T$ satisfies $\mathop{\bf
E\/}_{z}\Bigl{[}\sum_{\begin{subarray}{c}S\subseteq T\setminus
B,|S|\geq\kappa\end{subarray}}\;\widehat{f_{B\to
z}}(S)^{2}\Bigr{]}\leq\frac{\varepsilon^{2}}{4},$ we will have by 5.6 and 5.7
that

$c_{T}\geq\mathsf{corr}(f,\mathcal{J}_{T})-2.2\varepsilon$ (10)

Since we output the set $U$ with maximal $\widetilde{c_{U}}$, and since all
estimates are correct up to $\varepsilon$ we know that we output $U$ with

$\widetilde{c_{U}}\geq\widetilde{c_{T}}\geq c_{T}-\varepsilon.$ (11)

Combining Equations 10 and 11 together we get

$\widetilde{c_{U}}\geq
c_{T}-\varepsilon\geq\mathsf{corr}(f,\mathcal{J}_{T})-3.2\varepsilon.$

We move to prove the furthermore part, i.e., that
$\widetilde{c_{U}}\leq\mathsf{corr}(f,\mathcal{J}_{U})+2\varepsilon$
regardless of whether $T$ and $B$ satisfy Equation 5. We start by showing that
for any set $U$ (whatsoever) we have that
$\mathsf{corr}(f,\mathcal{J}_{U})\geq c_{U}-\varepsilon$. Indeed, by 5.6 we
have

${c_{U}}\approx_{\varepsilon}\mathop{\bf E\/}_{\begin{subarray}{c}z\in\\{\pm
1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\rho^{|S|}\Big{|}$

and since the noise operator can only reduce $\ell_{1}$-norm (see 2.8), we see
that for all $z\in\\{\pm 1\\}^{B}$ it holds that

$\mathop{\bf E\/}_{x\in\\{\pm 1\\}^{U\setminus B}}\Big{|}\sum_{S\subseteq
U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\rho^{|S|}\Big{|}\leq\mathop{\bf E\/}_{x\in\\{\pm
1\\}^{U\setminus B}}\Big{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\Big{|}$

Thus,

$\displaystyle c_{U}$ $\displaystyle\leq\varepsilon+\mathop{\bf
E\/}_{\begin{subarray}{c}z\in\\{\pm 1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\rho^{|S|}\Big{|}$ $\displaystyle\leq\varepsilon+\mathop{\bf
E\/}_{\begin{subarray}{c}z\in\\{\pm 1\\}^{B}\\\ x\in\\{\pm 1\\}^{U\setminus
B}\end{subarray}}\Big{|}\sum_{S\subseteq U\setminus B}\widehat{f_{B\to
z}}(S)\chi_{S}(x)\Big{|}=\varepsilon+\mathsf{corr}(f,\mathcal{J}_{U})$

Since $|c_{U}-\widetilde{c_{U}}|\leq\varepsilon$, we get that
$\widetilde{c_{U}}\leq
c_{U}+\varepsilon\leq\mathsf{corr}(f,\mathcal{J}_{U})+2\varepsilon$. ∎

After phase one, we can apply Lemma 5.8 to each $B$ from phase one, and get a
set $U_{B}:B\subseteq U_{B}\subseteq\mathcal{S}$ of size $k$, along with an
estimate of the correlation of $f$ to $\mathcal{J}_{U_{B}}$. This leads to the
proof of Theorem 1.2 which we restate next.

######  Theorem 5.9.

Given a Boolean function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, it is possible to
estimate the distance of $f$ from the class of $k$-juntas to within additive
error $\varepsilon$ with probability $2/3$ using
$2^{\widetilde{O}(\sqrt{k/\varepsilon})}$ adaptive queries to $f$. In
particular, when $\varepsilon$ is constant, this yields a
$2^{\widetilde{O}(\sqrt{k})}$-query algorithm. However, the algorithm still
requires $\exp(k/\varepsilon)$ time.

###### Proof.

Let $\varepsilon_{0}=\varepsilon/6$

  1. 1.

We first apply the result of [DMN19] to reduce the down to only
$\poly(k,1/\varepsilon_{0})$ coordinates. This incurs a loss in correlation of
at most $\varepsilon_{0}$, and fails with probability at most $\delta_{1}$,
which we can set to be $1/20$, by Corollary 4.3.

  2. 2.

Next, we apply our Theorem 1.4, which reduces the number of oracles we have to
consider down to $O(k/\varepsilon_{0}^{2})$, incurs an additive loss in
correlation of at most $\varepsilon_{0}$, and fails with probability at most
$\delta_{2}=1/20$.

  3. 3.

Then, we run phase 1 of our algorithm, which fails with probability at most
$\delta_{3}=1/20$ by Lemma 5.3.

  4. 4.

Finally, we apply Lemma 5.8 to every $B$ outputted by Algorithm 5 to get a set
$U_{B}$ and an estimate $\widetilde{C_{U_{B}}}$ for the correlation of $f$
with $\mathcal{J}_{U_{B}}$ We iterate on all sets $B$ returned by phase-1 and
return $U_{B}$ with the highest estimate of correlation.

There are
$\ell=O(\frac{1}{\varepsilon_{0}^{2}})^{3\sqrt{k/\varepsilon_{0}}+\log(2/\delta_{3})}=2^{\widetilde{O}(\sqrt{k/\varepsilon_{0}})}$
branches, and thus if we apply the algorithm from lemma 5.8 with
$\delta=1/(20\ell)$, we get that all this step fail with probability at most
$1/20$ by a union bound.

By a union bound, each of these steps succeeds with probability at least
$1-4/20\geq 2/3$. In the case all steps succeeds, we return a set $U$ with
$\widetilde{c_{U}}\geq\mathsf{corr}(f,\mathcal{J}_{n,k})-5.2\varepsilon_{0}$.
In addition, the moreover part in Lemma 5.8 guarantees that
$\widetilde{c_{U}}\leq\mathsf{corr}(f,\mathcal{J}_{U})+2\varepsilon_{0}\leq\mathsf{corr}(f,\mathcal{J}_{n,k})+2\varepsilon_{0}$.
We get that the returned value is within $5.2\varepsilon_{0}<\varepsilon$ of
$\mathsf{corr}(f,\mathcal{J}_{n,k})$. Finally, since
$\dist(f,\mathcal{J}_{n,k})=\frac{1+\mathsf{corr}(f,\mathcal{J}_{n,k})}{2}$ we
get that $\frac{1+\widetilde{c_{U}}}{2}$ is an $\varepsilon/2$-accurate
approximation of $\dist(f,\mathcal{J}_{n,k})$. Finally, we note that the query
complexities of phase 1 and phase 2 are both
$2^{\tilde{O}(\sqrt{k/\varepsilon})}$, but the runtime is exponential due to
lemma 5.8. ∎

Finally, we mention that if our goal is not to estimate to correlation with
the nearest $k$-junta to $f$, but rather to simply estimate the most amount of
Fourier mass any subset of $k$ variables contains, then we have the following
theorem with an improved dependence on $\varepsilon$:

######  Theorem 5.10.

Given a Boolean function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, it is possible to
estimate the most mass any subset of at most $k$ variables of $f$ has to
within additive error $\varepsilon$ with probability $2/3$ using
$2^{\widetilde{O}(\sqrt{k}\log(1/\varepsilon))}$ adaptive queries to $f$. In
particular, when $\varepsilon$ is constant, this yields a
$2^{\widetilde{O}(\sqrt{k})}$-query algorithm. However, the algorithm still
requires $\exp(k\log(1/\varepsilon))$ time.

We leave the proof of this theorem, which involves simple modifications to the
algorithm presented in this section, to Appendix A.

###  5.3 Proof of Theorem 5.1

We now present the proof of Theorem 5.1.

###### Proof of Theorem 5.1.

The proof is very similar to the previous proof of Theorem 4.11, so we explain
how to modify it to this case.

We express $\lambda_{U}$ in terms of the Fourier spectrum of $f$.

$\displaystyle\lambda_{U}$
$\displaystyle=\sum_{m=0}^{2|U|\log(10k)}\sum_{S:S\supseteq
U}\widehat{f}(S)^{2}\cdot\mathop{\bf Pr\/}_{J\subseteq_{p^{m}}[\ell]}[S\cap
J=U]$ $\displaystyle=\sum_{m=0}^{2|U|\log(10k)}\sum_{S:S\supseteq
U}\widehat{f}(S)^{2}\cdot\mathop{\bf Pr\/}_{J\subseteq_{p^{m}}[\ell]}[|S\cap
J|=|U|]\cdot\frac{1}{\binom{|S|}{|U|}}$ $\displaystyle=\sum_{S:S\supseteq
U}\frac{\widehat{f}(S)^{2}}{\binom{|S|}{|U|}}\cdot\sum_{m=0}^{2|U|\log(10k)}\mathop{\bf
Pr\/}_{J\subseteq_{p^{m}}[\ell]}[|S\cap J|=|U|]$

It suffices to show that for any non-empty set $S$ of size at least $|U|$ and
at most $k$ it holds that

$\sum_{m=0}^{2|U|\log(10k)}\mathop{\bf Pr\/}_{J\subseteq_{p^{m}}[\ell]}[|S\cap
J|=|U|]\in[1/2,3]\;.$ (12)

Again, we can analyze the sum on the left hand side of Equation 12 as the
expected final value of $X$ in the following random process:

1$X\leftarrow 0$

2 for  _$i=1,2,\ldots,2|U|\log(10k)$_ do

3 if  _$|S| <|U|$_ then

4 halt!

5 if  _$|S|=|U|$_ then

6 increase $X$

7 Sample $J_{i}\subseteq_{p}[\ell]$

8 $S\leftarrow S\cap J_{i}$

By symmetry the expected value depends only on the size of the initial set
$S$. As before, we denote by $F_{t}$ its expected value starting with a set
$S$ of size $t$ with an infinite horizon, and $F_{t}^{(i)}$ as the expected
value of $X$ at the end of the above process with finite horizon $i$. We start
by analyzing $F_{|U|}$. In this case, $X$ is a geometric random variable with
stopping probability $1-p^{|U|}$. Thus, its expectation is

$F_{|U|}=1/(1-p^{|U|})=1/(1-(1-1/2|U|)^{|U|})\in[2,3].$

This implies that $F_{|U|}^{(2|U|\log(10k))}\leq F_{|U|}\leq 3$. For $t>|U|$
in the infinite horizon case we have the recurrence

$F_{t}=\sum_{a=0}^{t}F_{a}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=a]=\sum_{a=|U|}^{t-1}F_{a}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=a]+F_{t}\cdot\mathop{\bf Pr\/}[\textrm{Bin}(t,p)=t]$
(13)

or equivalently

$F_{t}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<t]=\sum_{a=|U|}^{t-1}F_{a}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=a]$ (14)

We prove by induction that for $t\geq|U|$ it holds that $F_{t}\leq F_{|U|}$.
The claim clearly holds for $t=|U|$. For $t>|U|$ we can apply induction and
get

$F_{t}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<t]\leq\sum_{a=|U|}^{t-1}F_{|U|}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=a]\leq F_{|U|}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<t],$

and thus $F_{t}\leq F_{|U|}$. This immediately implies that
$F_{t}^{(2|U|\log(10k))}\leq F_{t}\leq 3$. On the other hand we prove that
$F_{t}^{(2|U|\log(10k))}\geq 1/2$ as long as $t\leq k$. To do so, we once
again introduce the indicator random variable $Y_{t}^{(i)}$, where $t=|S|$,
and which equals 1 if $|S|=|U|$ at some point during the above process before
iteration $i$. We note that $Y_{t}^{(2|U|\log(10k))}$ is a lower bound for the
value of $X$ in the above process, and $Y_{t}$ is a lower bound for the value
of $X$ at the end of the infinite horizon process. We note that the case
$|U|=1$ was already lower bounded in Section 4.5, where it was shown that
$\mathop{\bf E\/}[Y_{t}^{(\log(10k))}]\geq 1/2$, and therefore $\mathop{\bf
E\/}[Y_{t}^{(2|U|\log(10k))}]\geq 1/2$. It remains to show that the
$\mathop{\bf E\/}[Y_{t}^{(2|U|\log(10k))}]\geq 1/2$ is true for any set
$|U|\geq 2$.

First, we show that $\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<|U|]\leq\frac{1}{2}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]$. Towards this goal, it would suffice to prove
that $3\leq\mathop{\bf Pr\/}[\textrm{Bin}(t,p)=i+1]/\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=i]$ for $i<|U|$ and $t\geq|U|+1$. This would suffice
since in this case

$\sum_{i=0}^{|U|-1}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=i]\leq\sum_{i=0}^{|U|-1}\frac{3^{i}}{3^{|U|}}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]\leq\frac{1}{2}\cdot\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|].$

Indeed, The ratio between the two aforementioned probabilities is

$\frac{\mathop{\bf Pr\/}[\textrm{Bin}(t,p)=i+1]}{\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=i]}=\frac{\binom{t}{i+1}}{\binom{t}{i}}\cdot\frac{p^{i+1}(1-p)^{t-(i+1)}}{p^{i}(1-p)^{t-i}}=\frac{t-i}{i+1}\cdot\frac{p}{1-p}\geq\frac{2}{|U|}\cdot\frac{1-1/2|U|}{1/2|U|}=\frac{2-1/|U|}{1/2}\geq
3$

as needed. Now, we claim that $\mathop{\bf E\/}[Y_{t}]=\mathop{\bf
Pr\/}[Y_{t}=1]\geq 2/3$ for all $t\geq 1$. The base case of $t=1$ is certainly
true. Assuming we have $\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<|U|]\leq\tfrac{1}{2}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]$ we have

$\displaystyle\mathop{\bf E\/}[Y_{t}]\cdot\mathop{\bf Pr\/}[Bin(t,p)<t]$
$\displaystyle=\sum_{a=|U|}^{t-1}\mathop{\bf E\/}[Y_{a}]\cdot
Pr[\textrm{Bin}(t,p)=a]$ $\displaystyle\geq\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]+\sum_{a=|U|+1}^{t-1}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=a]\mathop{\bf E\/}[Y_{a}]$
$\displaystyle\geq\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]+\frac{2}{3}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)\in[|U|+1,t-1]]$ $\displaystyle=\frac{2}{3}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<t]-\frac{2}{3}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<|U|]+\frac{1}{3}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)=|U|]$ $\displaystyle\geq\frac{2}{3}\mathop{\bf
Pr\/}[\textrm{Bin}(t,p)<t]$

which implies that $\mathop{\bf E\/}[Y_{t}]\geq 2/3$. Finally, let $A$ be the
event that $S=\emptyset$ by iteration $2|U|\log(10k)$, and note that

$\displaystyle\mathop{\bf Pr\/}[A]$ $\displaystyle=\mathop{\bf
Pr\/}[\textrm{Bin}(|S|,(1-\tfrac{1}{2|U|})^{2|U|\log(10k)})=0]$
$\displaystyle\geq\mathop{\bf
Pr\/}[\textrm{Bin}(k,e^{-\log(10k)})=0]=\mathop{\bf
Pr\/}[\textrm{Bin}(k,\tfrac{1}{10k})=0]\geq 0.9$

as was shown in the proof for Theorem 4.11 in Section 4.5. Finally, we claim
that for all $t\geq 2$ we have that $\mathop{\bf Pr\/}[Y_{t}^{(2|U|\log
10k)}]\geq 1/2$. Indeed, we have that

$\displaystyle\mathop{\bf Pr\/}[Y_{t}^{(2|U|\log 10k))}=1]$
$\displaystyle\geq\mathop{\bf Pr\/}[Y_{t}=1]-\mathop{\bf
Pr\/}[\overline{A}]\geq\tfrac{2}{3}-0.1\geq\tfrac{1}{2}.$

as desired, provided $|S|\leq k$. ∎

##  6 Conclusions and Open Problems

We conclude by mentioning some future research directions. First, we believe
some of the techniques discussed in this paper could lead to other interesting
work in property testing, learning theory, or Boolean function analysis in
general. In particular, the procedure in Algorithm 1 makes use of a random
process to get access to an underlying junta, a subprocedure that could be
useful in other learning or testing algorithms. In addition, we are able to
approximate the quantities ${\mathbf{NInf}}_{i}$ and ${\mathbf{NInf}}_{U}$,
that serve as key steps in our algorithms. These quantities seems natural on
their own, and would likely find further applications in Analysis of Boolean
functions. In particular, they seem to capture more accurately the intuition
that “influences measures the importance of coordinates”. While the total
influence of a Boolean function can be any number between ${\mathop{\bf
Var\/}}[f]$ and $n\cdot{\mathop{\bf Var\/}}[f]$ the total normalized influence
equals exactly ${\mathop{\bf Var\/}}[f]$, and thus normalized influences can
be seen as a distribution of the variance among the coordinates.

Interestingly, our algorithms strongly resemble certain quantum algorithms. In
particular, the sampling of coordinates is done through the Fourier
distribution, a process which can be done much more efficiently with a quantum
algorithm (querying $f$ in superposition, applying the Hadamard transform, and
measuring). This idea was leveraged in [Amb+16] to provide fast quantum
algorithms for testing juntas in the standard property testing regime. Indeed,
if the nearest $k$-junta to $f$ has its mass on higher levels (say above
$\sqrt{k}$ or even $k/2$), then Fourier sampling is extremely effective and