# Superpolynomial lower bounds for decision tree learning and testing

Caleb Koch
Stanford Carmen Strassle
Stanford Li-Yang Tan
Stanford

###### Abstract

We establish new hardness results for decision tree optimization problems,
adding to a line of work that dates back to Hyafil and Rivest in 1976. We
prove, under the randomized exponential time hypothesis, superpolynomial
runtime lower bounds for two basic problems: given an explicit representation
of a function $f$ and a generator for a distribution $\mathcal{D}$,

  * $\circ$

construct a small decision tree approximator for $f$ under $\mathcal{D}$, and

  * $\circ$

decide if there is a small decision tree approximator for $f$ under
$\mathcal{D}$.

Our results imply new lower bounds for distribution-free PAC learning and
testing of decision trees, settings in which the algorithm only has restricted
access to $f$ and $\mathcal{D}$. Specifically, we get that:

  * $\circ$

$n$-variable size-$s$ decision trees cannot be properly PAC learned in time
$n^{\tilde{O}(\log\log s)}$, and

  * $\circ$

depth-$d$ decision trees cannot be tested in time $\exp(d^{\,O(1)})$.

For learning, the previous best lower bound only ruled out
$\mathrm{poly}(n)$-time algorithms (Alekhnovich, Braverman, Feldman, Klivans,
and Pitassi, 2009). For testing, recent work gives similar though incomparable
lower bounds in the setting where $f$ is random and $\mathcal{D}$ is
nonexplicit (Blais, Ferreira Pinto Jr., and Harms, 2021).

Assuming a plausible conjecture on the hardness of Set-Cover, we show that our
lower bound for properly PAC learning decision trees can be improved to
$n^{\Omega(\log s)}$, matching the best known upper bound of $n^{O(\log s)}$
due to Ehrenfeucht and Haussler (1989).

We obtain our results within a unified framework that leverages recent
progress in two different lines of work: the inapproximability of Set-Cover
and XOR lemmas for query complexity. Our framework is versatile and yields
results for related concept classes such as juntas and DNF formulas.

##  1 Introduction

The algorithmic problem of constructing decision tree representations of
functions is one of the most basic and well-studied problems of computer
science. Greedy decision tree learning heuristics such as ID3, C4.5, and CART,
developed in the 1980s, continue to be indispensable to everyday machine
learning and enjoy empirical success. The data mining textbook [WFHP16]
describes C4.5 as “a landmark decision tree program that is probably the
machine learning workhorse most widely used in practice to date”. In addition
to being extremely fast to evaluate, a key advantage of decision trees is
their simple and easy-to-understand structure, making them the most canonical
example of an interpretable model. The recent survey [RCC+22] lists decision
tree learning as the very first of “10 grand challenges” in the emerging field
of interpretable machine learning.

In terms of algorithms with theoretical guarantees, a classic result of
Ehrenfeucht and Haussler [EH89] gives a quasipolynomial time algorithm for
properly PAC learning decision trees: Given labeled examples
$(\bm{x},f(\bm{x}))$ where $f:\\{0,1\\}^{n}\to\\{0,1\\}$ can be computed by a
size-$s$ decision tree and $\bm{x}$ is drawn from a distribution $\mathcal{D}$
over $\\{0,1\\}^{n}$, their algorithm runs in $n^{O(\log s)}$ time and returns
a decision tree hypothesis that is close to $f$ under $\mathcal{D}$. Numerous
alternative algorithms have since been designed within restricted variants of
the PAC model (e.g. where $\mathcal{D}$ is assumed to be uniform) and by
relaxing the problem (e.g. allowing hypotheses that are not themselves
decision trees111Such improper decision tree learning algorithms do not apply
to the problem of “decision tree learning” as is meant in the context of
machine learning, where it always refers to the problem of constructing
decision tree hypotheses. See e.g. the textbooks [Mit97, Bis06, SSBD14] or the
Wikipedia page for “Decision tree learning”. From a practical perspective,
properness of decision tree algorithms is not just a feature but the entire
point—to produce a decision tree representation of the data. The focus of this
paper will be on proper decision tree learning algorithms.) [Riv87, Blu92,
Han93, KM93, KM96, Bsh93, GLR99, BM02, MR02, JS05, KS06, OS07, GKK08, KST09,
HKY18, CM19, BLQT21], but Ehrenfeucht and Haussler’s algorithm remains state
of the art in the standard PAC model.

Another interesting setting is when an explicit representation of the function
$f$, and possibly also the distribution $\mathcal{D}$, are given to the
algorithm. This easier setting, where the algorithm can “inspect” $f$, models
a popular approach in explainable machine learning known as post-hoc
explanations. The goal here is not to train a decision tree model for an
unknown function $f$, but instead to turn a complicated trained model $f$
(e.g. a neural net) into its decision tree representation. While numerous
algorithms for this task have been proposed in the empirical literature [CS95,
BS96, VAB07, ZH16, BKB17, VLJ+17, FH17, VS20], among those with theoretical
guarantees, the fastest one remains that of Ehrenfeucht and Haussler.

In parallel with these lines of algorithmic work, there has also been a
similarly large body of work on the hardness of decision tree learning [HR76,
GJ79, BFJ+94, HJLT96, KPB99, ZB00, LN04, CPR+07, RRV07, Sie08, ABF+09, AH12,
Rav13, BLT20]. It is interesting to note that the earliest paper here, by
Hyafil and Rivest in 1976, predates Ehrenfeucht and Haussler’s algorithm by
more than a decade; indeed, it even predates the PAC model. Their paper, which
established the NP-completeness of a certain formulation of decision tree
learning with perfect accuracy, reveals that the problem was already
intensively studied and recognized as central in the 1970s. Quoting the
authors, “the importance of this result can be measured in terms of the large
amount of effort that has been put into finding efficient algorithms for
constructing optimal binary decision trees”.

A closely related problem is that of testing decision trees: while in learning
one is interested in constructing small decision trees, here the goal is
simply to decide if one such tree exists. The distribution-free model of
property testing, introduced by Goldreich, Goldwasser, and Ron [GGR98] to
parallel distribution-free PAC learning, has received increasing attention in
recent years [CX16, LCS+18, Bsh19, Bel19, Har19, FY20, RR20, BFPJH21, Bsh22,
BHZ22, ABF+22, CP22, HY22].

##  2 Our results

We establish new hardness results for distribution-free learning and testing
of decision trees. For both problems, our lower bounds hold even when explicit
representations of both the function $f$ and distribution $\mathcal{D}$ are
given to the algorithm; lower bounds in this setting imply lower bounds for
learning and testing.

We obtain our results within a unified framework that brings together two
active lines of research: the inapproximability of Set-Cover [LY94, Fei98,
CHKX06, DS14, Mos15, KLM18, CL19, Lin19, CHK20, KI21] and XOR lemmas for query
complexity [Dru12, BB19, BFPJH21]. Connections between Set-Cover and decision
tree optimization problems, both in terms of algorithms and hardness, date
back to [HR76] and are present in numerous prior works; we leverage recent
progress in both the parameterized and nonparameterized settings. The
connection to XOR lemmas, on the other hand, is new to this work. All our
lower bounds, being computational in nature, are conditioned on the randomized
Exponential Time Hypothesis (ETH). As a byproduct, our lower bounds hold even
against randomized algorithms.

We now give a detailed overview of our results, in tandem with a discussion of
how they compare with prior work.

###  2.1 Lower bounds for DT-Construction

The DT-Construction problem is the variant of decision tree learning where $f$
and $\mathcal{D}$ are both given to the algorithm:

DT-Construction$(s,\varepsilon)$: Given as input a circuit representation of a
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, a generator for a distribution
$\mathcal{D}$ over $\\{0,1\\}^{n}$, parameters $s\in\mathds{N}$ and
$\varepsilon\in(0,1)$, and the promise that $f$ is a size-$s$ decision tree
under $\mathcal{D}$, construct a decision tree $T$ that is $\varepsilon$-close
to $f$ under $\mathcal{D}$.

Our first result is a superpolynomial runtime lower bound for DT Construction:

######  Theorem 1.

Under randomized ETH, for $s=n$ and $\varepsilon=\frac{1}{n}$ any algorithm
for DT-Construction$(s,\varepsilon)$ must take $n^{\tilde{\Omega}(\log\log
s)}$ time.

Prior works also focused on the parameter settings $s=n$ and
$\varepsilon=\frac{1}{n}$, corresponding to strong learning of linear-size
decision trees. Most recently, Alekhnovich, Braverman, Feldman, Klivans, and
Pitassi [ABF+09] ruled out $\mathrm{poly}(n)$ time algorithms under the
assumption that Sat cannot be solved in randomized subexponential time. Before
that, Hancock, Jiang, Li, and Tromp [HJLT96] ruled out $\mathrm{poly}(n)$ time
algorithms that return a decision tree hypothesis of size $n^{1+o(1)}$, under
the assumption that Sat cannot be solved in randomized quasipolynomial time.

Our proof of Theorem 1 opens up a concrete route towards obtaining the optimal
$n^{\Omega(\log s)}$ lower bound. We can also show an $n^{\Omega(\log s)}$
lower bound for the stricter version of DT-Construction where the algorithm
has to return a decision tree of size $s$ (instead of one of any size). We
elaborate on both of these in Section 2.3.

##### Hardness of learning juntas with DNF hypotheses.

We obtain Theorem 1 as a corollary of our first main result, which
simultaneously allows for a stronger promise on the simplicity of the target
function $f$ and for the algorithm to return a more expressive hypothesis:

######  Theorem 2.

Under randomized ETH, for $s=n$ and $\varepsilon=\frac{1}{n}$ any algorithm
for DT-Construction$(s,\varepsilon)$ must take $n^{\tilde{\Omega}(\log\log
s)}$ time, even if $f$ is further promised to be a $(\log s)$-junta under
$\mathcal{D}$ and the algorithm is allowed to return a DNF hypothesis.

We recall the strict inclusions

$\\{\text{$(\log s)$-juntas}\\}\subset\\{\text{size-$s$ decision
trees}\\}\subset\\{\text{size-$s$ DNFs}\\}.$

Each class is exponentially more expressive than the previous one: a size-$s$
decision tree can depend on as many as $s$ variables, and a size-$s$ DNF can
require a decision tree of size $2^{\Omega(s)}$.

The results of [ABF+09, HJLT96] are not known to be amenable to such a
strengthening. [ABF+09] did give lower bounds for DNF-Construction, the
analogue of DT-Construction where the target $f$ is promised to be a DNF under
$\mathcal{D}$ and the algorithm is expected to construct a DNF hypothesis.
They ruled out $\mathrm{poly}(n)$ time algorithms for $s=n$ and
$\varepsilon=\frac{1}{n}$. [ABF+09] gave two separate proofs of hardness for
DT-Construction and DNF-Construction, reducing from Set-Cover for the former
and from Chromatic-Number for the latter. Theorem 2, on the other hand, yields
new lower bounds for both problems via a single proof.

##### Hardness of properly learning juntas.

Implicit in the proofs of Theorems 1 and 2 is a tight connection between
algorithms for Set-Cover and algorithms for properly learning juntas. By
making this connection explicit, we obtain strong lower bounds for the latter
problem that hold even under the promise that the target is a monotone
disjunction:

######  Theorem 3.

Under randomized ETH, for any $k\leq n^{c}$ where $c<1$ is any constant and
$\varepsilon=O(\frac{1}{n})$, there is no algorithm that, given as input a
circuit representation of a function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, a
generator for a distribution $\mathcal{D}$ and the promise that $f$ is a
monotone $k$-disjunction under $\mathcal{D}$, runs in $n^{o(k)}$ time and
constructs a $k$-junta that is $\varepsilon$-close to $f$ under $\mathcal{D}$.
Under randomized SETH, we get a lower bound of $O(n^{k-\lambda})$ for any
constant $\lambda>0$.

These lower bounds nearly match the $O(n^{k}/\varepsilon)$ runtime algorithm
of the trivial algorithm that iterates over all possible $k$-junta hypotheses.
Previously, [ABF+09] ruled out $\mathrm{poly}(n)$-time algorithms for $k\leq
O(\log n)$.

###  2.2 Lower bounds for DT-Estimation

The second problem that we consider, DT-Estimation, is a variant of
distribution-free decision tree testing where $f$ and $\mathcal{D}$ are both
given to the algorithm:222It will be more convenient for us to measure the
complexity of decision trees by their depth in this section, though there are
direct analogues of our results for size instead of depth.

DT-Estimation$(d,\varepsilon)$: Given as input a circuit representation of a
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, a generator for a distribution
$\mathcal{D}$ over $\\{0,1\\}^{n}$, and parameters
$d\in\mathds{N},\varepsilon\in(0,1)$, distinguish between the following cases:
$\circ$ Yes: $f$ is a depth-$d$ decision tree under $\mathcal{D}$. $\circ$ No:
$f$ is $\varepsilon$-far from every depth-$d$ decision tree under
$\mathcal{D}$.

Our second main result is an exponential lower bound for DT-Estimation:

######  Theorem 4.

Under randomized ETH, any algorithm for DT-Estimation$(d,\varepsilon)$ must
take $\exp(d^{\,\Omega(1)})$ time. This holds even if
$\varepsilon=\frac{1}{2}-\exp(-d^{\,\Omega(1)})$ and the No case satisfies the
stronger promise that $f$ is $\varepsilon$-far from every decision tree of
depth $\Omega(d\log d)$ under $\mathcal{D}$.

Recent work of Blais, Ferreira Pinto Jr., and Harms [BFPJH21] gives an
$\tilde{\Omega}(2^{d})$ lower bound on the query complexity testing of
depth-$d$ decision trees. This lower bound, however, only applies in the
setting where both $f$ and $\mathcal{D}$ are unknown to the algorithm, since
it is based on a random function $f$ and a nonexplicit distribution
$\mathcal{D}$.333This nonexplicit distribution is derived from lower bounds on
the sample complexity of estimating distribution support size [WY19]. In
contrast, our proof of Theorem 4 is constructive: it is based on an $f$ that
is a depth-$3$ circuit (with $\\{\oplus,\vee\\}$ gates) and a similarly simple
generator for $\mathcal{D}$. Furthermore, [BFPJH21]’s lower bound only holds
when $\varepsilon$ is a sufficiently small constant, whereas ours holds for
$\varepsilon$ being exponentially close to $\frac{1}{2}$, and with a gap
between the decision tree depths of the Yes and No cases.

As for upper bounds, Bshouty and Haddad-Zaknoon [BHZ22] give a distribution-
free tester that runs in $2^{O(d)}n$ time and distinguishes depth-$d$ decision
trees from those that are $\varepsilon$-far from decision trees of depth
$d^{2}$. Under the uniform distribution, Blanc, Lange, and Tan [BLT22] give an
algorithm that runs in $\mathrm{poly}(d,1/\varepsilon)\cdot n\log n$ time and
distinguishes depth-$d$ decision trees from those that are $\varepsilon$-far
from decision trees of depth $O(d^{3}/\varepsilon^{3})$.

###  2.3 Towards stronger lower bounds for DT-Construction

We show two ways in which the lower bounds of Theorems 1 and 2 can be further
improved to $n^{\Omega(\log s)}$. First, we consider the stricter version of
DT-Construction where the algorithm has to return a size-$s$ decision tree:

######  Theorem 5.

Under randomized ETH, for $s=\exp(\tilde{O}(\log\log n))$ and
$\varepsilon=\frac{1}{n}$ any algorithm for DT-Construction$(s,\varepsilon)$
must take $n^{\Omega(\log s)}$ time if the algorithm has to return a size-$s$
decision tree. As in Theorem 2, this holds even if $f$ is further promised to
be a $(\log s)$-junta under $\mathcal{D}$ and the algorithm is allowed to
return a size-$s$ DNF hypothesis.

This more stringent version of DT-Construction corresponds to the notion of
strictly proper learning of size-$s$ decision trees, where the algorithm has
to return a hypothesis that falls within the concept class. Ehrenfeucht and
Haussler’s algorithm is not strictly proper. On the other hand, for size-$s$
decision trees of depth $O(\log s)$, there is a simple dynamic programming
algorithm that runs in $n^{O(\log s)}$ time and is strictly proper [GLR99,
MR02]. Since every $(\log s)$-junta is a decision tree of depth $\log s$, this
matches the lower bound of Theorem 5.

Finally, we show how an optimal lower bound of $n^{\Omega(\log s)}$ for the
original version of DT-Construction, matching the runtime of Ehrenfeucht and
Haussler’s algorithm, would follow from a natural and well-studied conjecture
about Set-Cover:

######  Conjecture 1 (Optimal inapproximability of parameterized Set-Cover).

There exists constants $\alpha,\beta<1$ such that for $k\leq N^{\alpha}$,
there is no $N^{o(k)}$ time algorithm that, given a size-$N$ set cover
instance, distinguishes between:

  * $\circ$

Yes: There is a set cover of size $k$.

  * $\circ$

No: Every set cover has size at least $k\cdot(1-\beta)\ln N$.

There is a simple and efficient $\ln N$-approximation algorithm for Set-Cover,
and various hardness results are known for the problem of achieving a better
approximation ratio [LY94, Fei98, DS14, Mos15, CHK20]. 1 states that this
hardness carries over to the parameterized setting. Existing ETH-based lower
bounds for parameterized Set-Cover [CHKX06, KLM18, CL19, Lin19, KI21] are
evidence in favor of it, and it is plausible that 1 can be shown to hold under
ETH.444See [MPW19, GKMP20] for further discussions of this conjecture and its
implications for proof complexity. We show:

######  Theorem 6.

Under 1, for $s=n$ and $\varepsilon=\frac{1}{n}$ any algorithm for DT-
Construction$(s,\varepsilon)$ must take $n^{\Omega(\log s)}$ time. As in
Theorem 2, this holds even if $f$ is further promised to be a $(\log s)$-junta
under $\mathcal{D}$ and the algorithm is allowed to return a DNF hypothesis.

Table 1 summarizes our results for DT-Construction and shows how they compare
with the prior state of the art.

Table 1: Algorithms and lower bounds for DT-Construction. All our results are conditioned on randomized ETH, the lower bounds of Theorems 5 and 6 are optimal. Reference | Target |  Hypothesis | Time complexity
---|---|---|---
[ABF+09] | size-$s$ DT | DT |  $n^{\omega(1)}$ lower bound
[ABF+09] | size-$s$ DNF | DNF | $n^{\omega(1)}$ lower bound
[EH89] |  size-$s$ DT | DT |  $n^{O(\log s)}$ upper bound
Theorem 2 |  $(\log s)$-junta | DNF |  $n^{\tilde{\Omega}(\log\log s)}$ lower bound
Theorem 5 |  $(\log s)$-junta | size-$s$ DNF |  $n^{\Omega(\log s)}$ lower bound
Theorem 6 |  $(\log s)$-junta | DNF |  |  $n^{\Omega(\log s)}$ lower bound
---
under 1

##  3 Our techniques

The starting point of all our reductions is the parameterized version of Set-
Cover. For a set cover instance $\mathcal{S}$, we write
$\mathrm{opt}(\mathcal{S})$ to denote the size of the smallest set cover.

######  Definition 1.

The $(k,k^{\prime})$-Set-Cover problem is the following. Given as input a set
cover instance $\mathcal{S}$ and parameters $k,k^{\prime}\in\mathds{N}$,
output Yes if $\mathrm{opt}(\mathcal{S})\leq k$ and No if
$\mathrm{opt}(\mathcal{S})>k^{\prime}$.

##### Reducing from Set-Cover to juntas vs. DNFs.

Our key lemma, which is the crux of our lower bounds for both DT-Construction
and DT-Estimation, is a reduction from $(k,k^{\prime})$-Set-Cover to the
problem of distinguishing small juntas from large DNF formulas, where “small”
and “large” are functions of $k$ and $k^{\prime}$ respectively:

######  Lemma 3.1.

There is an algorithm that, given a size-$N$ instance $\mathcal{S}$ of
$(k,k^{\prime})$-Set-Cover with $n$ sets and a parameter $\ell\leq N$, runs in
$\mathrm{poly}(N)$ time and outputs a circuit representation of a function
$f:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ and a generator for a distribution
$\mathcal{D}$ over $(\\{0,1\\}^{\ell})^{n}$ satisfying:

  * $\circ$

If $\mathrm{opt}(\mathcal{S})\leq k$, then $f$ is a $k\ell$-junta under
$\mathcal{D}$.

  * $\circ$

If $\mathrm{opt}(\mathcal{S})>k^{\prime}$, then any DNF of size
$\leq\exp(O(k^{\prime}\ell))$ is $\Omega(\frac{1}{N})$-far from $f$ under
$\mathcal{D}$.

We obtain Theorems 1, 2 and 5 by combining Lemma 3.1 with a recent result on
the ETH-hardness of $(k,k^{\prime})$-Set-Cover for
$k^{\prime}=\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}$, where
$N$ is the size of the instance [Lin19]. Similarly, we obtain Theorem 6 by
combining Lemma 3.1 with 1. For Theorem 3, we only need a simpler special case
of Lemma 3.1, which we combine with the ETH- and SETH-hardness of
$(k,k+1)$-Set-Cover (i.e. the hardness of solving parameterized Set-Cover
exactly) [CHKX06, PW10].

$0$$n$$0$$2^{n}$$0$$2^{n}$$\mathrm{opt}\leq
k$$\mathrm{opt}>k^{\prime}$size-$k^{\prime}$ DTsize-$k$
DTsize-$2^{\Omega({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k^{\prime}}\ell)}$
DNF$k\ell$-junta(Gap amplification)(Easy reduction)Set cover sizeComplexity of
$f$ under $\mathcal{D}$ $(k,k^{\prime})$-Set-Cover on $n$ vertices requires
time  $t(n,k)$ Learning juntas with DNF hypotheses requires time
$\min\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}t(n,k)},2^{\Omega(k^{\prime}\ell)}\\}$
$\Rightarrow$ Figure 1: An illustration of Lemma 3.1 as a gap amplification
technique. We take an instance of $(k,k^{\prime})$-Set-Cover where the gap
between $k$ and $k^{\prime}$ is small and first construct a distribution and a
function whose decision tree complexity under the distribution exactly
reflects the set cover gap. Then we amplify the distribution and the function
to obtain an even more drastic gap in the complexity of the function under the
distribution. Lemma 3.1 is quite versatile and underlies the proofs of
Theorems 1, 2, 6, 4 and 5.

##### Gap amplification.

We view Lemma 3.1 as a gap amplification procedure. Specifically, given a
$(k,k^{\prime})$-Set-Cover instance it is straightforward to construct an
instance of DT-Construction, a target function $f$ and distribution
$\mathcal{D}$, where the decision tree complexity of $f$ under $\mathcal{D}$
exactly reflects the gap $(k,k^{\prime})$: if $\mathrm{opt}(\mathcal{S})\leq
k$ then $f$ is a size-$k$ decision tree under $\mathcal{D}$, and otherwise $f$
requires decision trees of size $\geq k^{\prime}$. To obtain stronger lower
bounds we amplify this gap into a much larger gap in the complexity of $f$
under $\mathcal{D}$: if $\mathrm{opt}(\mathcal{S})\leq k$ then $f$ is a small
junta under $\mathcal{D}$, and if $\mathrm{opt}(\mathcal{S})>k^{\prime}$ then
$f$ is a large-size DNF under $\mathcal{D}$. This reduction enables us to
translate lower bounds for $(k,k^{\prime})$-Set-Cover into strong lower bounds
for DT-Construction. See Figure 1 for an illustration of this gap
amplification.

##### Building hard instances of DT-Construction.

Our construction of $f$ and $\mathcal{D}$ in Lemma 3.1 is based on the one in
[ABF+09], which in turn builds on [Hau88, HJLT96]. [ABF+09] also gave a gap
amplifying reduction from $(k,k^{\prime})$-Set-Cover to the problem of
distinguishing whether $f$ has small or large decision tree complexity under
$\mathcal{D}$. Lemma 3.1 is a strengthening of their reduction where the same
gap in set cover sizes leads to a more dramatic gap in $f$’s complexity under
$\mathcal{D}$. While the construction of $f$ and $\mathcal{D}$ is similar to
the one in [ABF+09], our analysis is entirely different and is, in our
opinion, simpler. Notably, our analysis enables us to obtain lower bounds even
against DNF hypotheses whereas previous works relied crucially on the
hypothesis being a decision tree. In addition to yielding our stronger
conclusion, our analysis overcomes technical challenges that arise when we
have to modify Lemma 3.1 in the context of DT-Estimation, which we now
discuss.

##### Hardness amplification using XOR lemmas for query complexity.

For our lower bounds for DT-Estimation, we begin by observing that Lemma 3.1,
when combined with existing results on the inapproximability of
nonparameterized Set-Cover [DS14, Mos15], already implies a mild form of
hardness of DT-Estimation:

######  Corollary 3.2 (Mild hardness for DT-Estimation).

Under ETH, there is no $\exp(d^{\,\Omega(1)})$ time algorithm that, given as
input the circuit representation of a function $f:\\{0,1\\}^{n}\to\\{0,1\\}$,
a generator for a distribution $\mathcal{D}$ over $\\{0,1\\}^{n}$, a parameter
$d\in\mathds{N}$, distinguishes between:

  * $\circ$

Yes: $f$ is a depth-$d$ decision tree under $\mathcal{D}$.

  * $\circ$

No: $f$ is $\Omega(\frac{1}{n})$-far from every decision tree of depth
$\Omega(d\log d)$ under $\mathcal{D}$.

We amplify this mild hardness ($\varepsilon=O(\frac{1}{n})$) to very strong
hardness ($\varepsilon=$ exponentially close to $\frac{1}{2}$) by considering
$f^{\oplus m}:(\\{0,1\\}^{n})^{m}\to\\{0,1\\}$, the $m$-fold XOR composition
of $f$:

$f^{\oplus m}(x^{(1)},\ldots,x^{(m)})\coloneqq f(x^{(1)})\oplus\cdots\oplus
f(x^{(m)})$

and the corresponding distribution $\mathcal{D}^{m}$ over
$(\\{0,1\\}^{n})^{m}$. In the Yes case of Corollary 3.2, it is easy to see
that $f^{\oplus m}$ is a decision tree of depth $\leq dm$ under
$\mathcal{D}^{m}$. To analyze the No case, we prove the following lemma:

######  Lemma 3.3 (Hardness amplification for DT Estimation).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $\mathcal{D}$ be such that $f$ is
$\varepsilon$-far from every depth-$d$ decision tree under $\mathcal{D}$. For
any $\gamma>0$, by taking $m=\Theta(\log(1/\gamma)/\varepsilon)$, we get that
$f^{\oplus m}$ is $(\frac{1}{2}-\gamma)$-far from every decision tree of depth
$\Omega(dm)$ under $\mathcal{D}^{m}$.

Our proof of Lemma 3.3 combines existing XOR lemmas for distributional query
complexity [Dru12, BB19, BKLS20]. Specifically, we first use one due to Brody,
Kim, Lerdputtipongporn, and Srinivasulu [BKLS20] to amplify from
$\varepsilon=O(\frac{1}{n})$ to $\Theta(1)$, and then one due to Drucker
[Dru12] to amplify from $\Theta(1)$ to exponentially close to $\frac{1}{2}$.
The quantitative parameters of these lemmas are incomparable, and we show how
they can be applied in tandem in our setting.

##### Handling aborts.

Lemma 3.3 as stated is actually not quite what we prove; see Lemma 7.4 for the
actual version. For technical reasons, the XOR lemma of [BKLS20] (and hence
Lemma 3.3) requires a stronger assumption, that $f$ is $\varepsilon$-far from
every depth-$d$ decision tree that is allowed to abort with probability
$\delta$, and distance is measured with respect to non-aborts. [BKLS20]’s
lemma requires $\delta=\Theta(1)$ whereas $\varepsilon=O(\frac{1}{n})$ in our
setting, so this is a significantly stronger assumption. To satisfy this
stronger assumption, we have to prove a strengthening of Corollary 3.2 where
the No case maps to an $f$ that is $\Omega(\frac{1}{n})$-far from decision
trees that are allowed to abort with constant probability; this in turn
necessitates a corresponding strengthening of Lemma 3.1. With these in hand,
Theorem 4 then follows fairly easily.

##  4 Discussion and future work

Our work makes new progress on the longstanding open problem of determining
the complexity of properly PAC learning decision trees. A natural avenue for
future work is to close the remaining gap between our lower bound of
$n^{\tilde{\Omega}(\log\log s)}$ and the $n^{O(\log s)}$ runtime of
Ehrenfeucht and Haussler’s algorithm. Our techniques point to an approach
towards an $n^{\Omega(\log s)}$ lower bound via 1, which adds further
motivation to the study of parameterized Set-Cover.

As for our testing lower bounds, a notable feature is that they hold in the
regime where $\varepsilon=\frac{1}{2}-o(1)$, which we obtain from an initial
hardness for $\varepsilon=\Omega(\frac{1}{n})$ via XOR lemmas for query
complexity. It would be interesting to further develop such hardness
amplification techniques in property testing. For example, can the
communication-complexity-based lower bound technique of Blais, Brody, and
Matulef [BBM12] be fruitfully combined with the large body of work on XOR
lemmas, and direct-product-type results more generally, for communication
complexity?

More broadly, there is a growing and concerted effort within the machine
learning community to design algorithms that produce simple hypotheses, such
as decision trees, especially in the context of high-stakes applications where
interpretability is paramount; see e.g. the position paper [Rud19]. Our lower
bounds show that interpretability can come at the price of computational
intractability, even under strong assumptions on the target function. There is
substantial practical motivation for the development of a theoretical
understanding of such tradeoffs and how they can be mitigated. For example, a
concrete next step from our work is to identify reasonable assumptions under
which our lower bounds can be circumvented; one could consider monotone target
functions, a common assumption in both theory and practice.

##  5 Preliminaries

##### Set Cover.

Given a bipartite graph $\mathcal{S}=(S,U,E)$ on $N$-vertices, the Set-Cover
problem is to find a minimum size subset $C\subseteq S$ such that every vertex
in $U$ is adjacent to some vertex in $C$.555Typically, the set cover problem
is cast as a combinatorial problem: given subsets
$S_{1},\ldots,S_{m}\subseteq[n]$ of some universe $[n]$, find the minimum size
subcollection $S_{i_{1}},\ldots,S_{i_{k}}$ whose union is $[n]$. We consider
the graph theoretic formulation because it makes the connection to the hitting
set problem more transparent. We write
$\mathrm{opt}(\mathcal{S})\in\mathds{N}$ to denote the size of the smallest
set cover for $\mathcal{S}$. We will often write $n$ to denote the size of
$|S|\leq N$. The set of neighbors of a vertex $u\in U$ is
$\mathcal{N}_{\mathcal{S}}(u)=\\{s\in S:(s,u)\in E\\}$. We identify a vertex
$u\in U$ with its neighborhood set $\mathcal{N}_{\mathcal{S}}(u)$. Each set
$\mathcal{N}_{\mathcal{S}}(u)$ can be viewed as a string in $\\{0,1\\}^{|S|}$
where a $1$ in the string indicates an edge between $u$ and the corresponding
vertex $s\in S$. Hence, each vertex $u\in U$ can likewise be encoded as a
string in $\\{0,1\\}^{|S|}$.666We assume without loss of generality that each
$\mathcal{N}_{\mathcal{S}}(u)$ is unique so that a vertex $u$ can be
identified by its neighborhood set $\mathcal{N}_{\mathcal{S}}(u)$ (if
$\mathcal{N}_{\mathcal{S}}(u)=\mathcal{N}_{\mathcal{S}}(u^{\prime})$ for
$u\neq u^{\prime}$ we can simply delete $u^{\prime}$ without affecting the set
cover complexity)

##### Hitting Set.

Given a bipartite graph $\mathcal{H}=(S,U,E)$, the Hitting-Set problem is to
find a minimum size subset $I\subseteq U$ which “hits” every vertex $s\in S$:
$\mathcal{N}_{\mathcal{S}}(s)\cap I\neq\varnothing$ for all $s\in S$. We write
$\mathrm{opt}(\mathcal{H})$ for the size of the smallest hitting set.

An instance $\mathcal{H}=(S,U,E)$ of Hitting-Set can equivalently be viewed as
an instance $\mathcal{H}=(U,S,E)$ of Set-Cover.

######  Fact 5.1 (Set-Cover and Hitting-Set are equivalent).

Set-Cover and Hitting-Set are equivalent to each other under approximation-
preserving reductions. In particular, any instance $\mathcal{S}$ of Set-Cover
can be transformed in linear-time into an instance $\mathcal{H}$ of hitting
set such that $\mathrm{opt}(\mathcal{S})=\mathrm{opt}(\mathcal{H})$ and vice
versa.

The results of [ABF+09] are formulated in terms of hitting set. Though for
consistency, in this work we will only refer to Set-Cover. See Figure 2 for an
illustration of a set cover instance and a hitting set instance on a single
bipartite graph.

$S$ $U$

(a) A set cover of size 3 for $G$ highlighted in teal

$S$ $U$

(b) A hitting set of size $2$ for $G$ highlighted in purple

Figure 2: A bipartite graph $G=(S,U,E)$ viewed on the left as a set cover
instance and on the right as a hitting set instance.

##### Decision trees.

For a decision tree $T:\\{0,1\\}^{n}\to\\{0,1\\}$, we write $L\in T$ to denote
that $L$ is a leaf of $T$. The size of $T$ is its number of leaves and is
denoted $|T|$. For an input $x\in\\{0,1\\}^{n}$, we write
$0pt_{T}(x)\in\mathds{N}$ to denote the depth of $x$ in $T$, the number of
variables queried on the root-to-leaf path consistent with $x$.

##### DNF formulas.

A literal is a variable or its negation. A term is a conjunction ($\land$) of
literals. A DNF formula $F:\\{0,1\\}^{n}\to\\{0,1\\}$ is a disjunction
($\lor$) of terms, denoted $F=t_{1}\lor\cdots\lor t_{s}$. The size of the DNF
formula is $|F|=s$, the number of terms. The width of a term $|t_{i}|$ is the
number of literals in it. The width of an input $x\in\\{0,1\\}^{n}$ is defined
as the width of the smallest width term accepting $x$ and $0$ if no term
accepts $x$:

$\mathrm{width}_{F}(x)\coloneqq\begin{cases}\underset{t_{i}(x)=1}{\min}|t_{i}|&F(x)=1\\\
0&F(x)=0.\end{cases}$

##### Circuits.

We consider Boolean circuits $\mathcal{C}:\\{0,1\\}^{n}\to\\{0,1\\}$ with AND,
OR, NOT, and PARITY gates: $\\{\land,\lor,\lnot,\oplus\\}$. The size of a
circuit $|\mathcal{C}|$ is the number of gates in it. The depth of a circuit
is the longest directed path from an input node to an output node.

#####  $k$-juntas.

A function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ is a $k$-junta if its output depends
on $\leq k$ bits. Hence, if $f$ is a $k$-junta it can be completely specified
by a table of size $2^{k}$ corresponding to all possible assignments to the
$k$ relevant variables. In particular, every $k$-junta is a size-$2^{k}$
decision tree and every size-$s$ decision tree is an $s$-junta.

##### Distributions.

We use boldface letters e.g. $\bm{x},\bm{y}$ to denote random variables. For a
distribution $\mathcal{D}$, we write
$\mathrm{dist}_{\mathcal{D}}(f,g)=\operatorname{{Pr}}_{x\sim\mathcal{D}}[f(\bm{x})\neq
g(\bm{x})]$. A function $f$ is $\varepsilon$-close to $g$ if
$\mathrm{dist}_{\mathcal{D}}(f,g)\leq\varepsilon$. When $\varepsilon=0$, we
drop the $\varepsilon$ and simply say $f$ computes $g$ over $\mathcal{D}$.
Often $f$ is viewed as one of the combinatorial objects above and $g$ is a
generic function, e.g. a decision tree $T:\\{0,1\\}^{n}\to\\{0,1\\}$ computes
$g$ over $\mathcal{D}$ if $\mathrm{dist}_{\mathcal{D}}(T,g)=0$. Similarly, $f$
is $\varepsilon$-far from $g$ if
$\mathrm{dist}_{\mathcal{D}}(f,g)>\varepsilon$. We write $\mathcal{U}_{b}$ for
the uniform distribution on $b$ bits. A generator for a distribution
$\mathcal{D}$ over $\\{0,1\\}^{n}$ is an algorithm
$G:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ which takes $n$ uniform random bits as input
and outputs $n$ bits distributed according to $\mathcal{D}$:
$\operatorname{{Pr}}_{\bm{x}\sim\mathcal{U}_{n}}[G(\bm{x})=x]=\operatorname{{Pr}}_{\bm{x}\sim\mathcal{D}}[\bm{x}=x]$
for all $x\in\\{0,1\\}^{n}$.

##### Learning.

See Appendix C for the definitions of learning that we use. All learning
algorithms we consider are proper learning algorithms. When referring to
“learning decision trees” we mean properly learning the concept class
$\mathcal{T}=\\{T:\\{0,1\\}^{n}\to\\{0,1\\}\mid T\text{ is a decision
tree}\\}$. Likewise, when referring to “learning size-$s$ decision trees”, we
mean properly learning the concept class
$\mathcal{T}_{s}=\\{T:\\{0,1\\}^{n}\to\\{0,1\\}\mid T\text{ is a size-}s\text{
decision tree}\\}$. When discussing algorithms for learning $k$-juntas, we
assume the output of the learning algorithm is a table of size $2^{k}$ (as in
e.g. [MOS04]).

##### Complexity-theoretic assumptions.

Many results on the hardness of Set-Cover are conditioned on the exponential
time hypothesis.

######  Hypothesis 1 (Exponential time hypothesis (ETH) [Tov84, IP01, IPZ01]).

There exists a constant $\delta>0$ such that $3$-SAT on $n$ variables cannot
be solved in $O(2^{\delta n})$ time.

Since we are proving hardness against randomized algorithms, we will use a
randomized variant of ETH.

######  Hypothesis 2 (Randomized ETH, see [CIKP08, DHM+14]).

There exists a constant $\delta>0$ such that $3$-SAT on $n$ variables cannot
be solved by a randomized algorithm in $O(2^{\delta n})$ time with error
probability at most $1/3$.

We will also use two additional hypotheses.

######  Hypothesis 3 (Strong exponential time hypothesis (SETH) [IP01,
IPZ01]).

For every $\delta>0$, there exists a $k\in\mathds{N}$ such that $k$-CNF-SAT on
$n$ variables cannot be solved in time $O(2^{n(1-\delta)})$.

######  Hypothesis 4 ($W[1]\neq\textnormal{FPT}$, see [DF13, CFK+15]).

For any computable function $f:\mathds{N}\to\mathds{N}$, no algorithm can
decide if a graph $G=(V,E)$ contains a $k$-clique in
$f(k)\cdot\mathrm{poly}(|V|)$ time.

As with randomized ETH, randomized SETH and randomized
$W[1]\neq\textnormal{FPT}$ are the respective versions of these hypotheses
against randomized algorithms. Also, we remark that $W[1]\neq\textnormal{FPT}$
is a weaker assumption than ETH which itself is weaker than SETH. If
$W[1]=\textnormal{FPT}$, then SAT is solvable in subexponential time.

###  5.1 Existing results on the hardness of Set-Cover

Throughout, we use several different hardness results for Set-Cover and
approximating Set-Cover. We start with the following theorem due to [Lin19]
about the hardness of approximating set cover. We have slightly modified the
theorem from its original form to fit our setting. We discuss Lin’s original
theorem and our modifications in Appendix A.

######  Theorem 7 ([Lin19]).

Assuming randomized ETH, there is a constant $c\in(0,1)$ such that for any
$k\in\mathds{N}$ with $k\leq\frac{1}{2}\cdot\frac{\log\log N}{\log\log\log
N}$, there is no randomized $N^{ck}$ time algorithm that can solve
$\left(k,\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}\right)$-Set-
Cover on $N$ vertices with high probability.

We will also use results on the inapproximability of unparameterized Set-
Cover:

######  Theorem 8 ([DS14, Mos15]).

Under randomized ETH, for every $0<\beta<1$, any algorithm that approximates
size-$N$ instances of Set-Cover to within $(1-\beta)\ln N$ w.h.p. requires
$2^{N^{\Omega(\beta)}}$ time.

By a standard search-to-decision reduction, Theorem 8 implies the following
lower bound for $(k,k^{\prime})$-Set-Cover where, unlike in the parameterized
setting, $k$ is no longer guaranteed to be “small”:

######  Theorem 9.

Under randomized ETH, for every $0<\beta<1$, there exists $k\leq N$ such that
any algorithm that solves size-$N$ instances of $(k,k^{\prime})$-Set-Cover
where $k^{\prime}=k(1-\beta)\ln N$ w.h.p. requires $2^{N^{\Omega(\beta)}}$
time.

Finally, we will also use existing lower bounds in the ungapped setting:

######  Theorem 10 (Ungapped hardness of Set-Cover from
$W[1]\neq\textnormal{FPT}$ [CHKX06, Theorem 5.6]).

Assuming $W[1]\neq\textnormal{FPT}$, for all constants $c\in(0,1)$ and for all
$k\leq n^{c}$, any $(k,k+1)$-Set-Cover instance $\mathcal{S}=(S,U,E)$ cannot
be solved in time $|S|^{o(k)}$.

Furthermore, there are even stronger set cover lower bounds assuming SETH.

######  Theorem 11 (Ungapped hardness of Set-Cover from SETH [PW10, Theorem
2.3]).

Assuming SETH, for all constants $c,\delta\in(0,1)$ and for all $k\leq n^{c}$,
any $(k,k+1)$-Set-Cover instance $\mathcal{S}=(S,U,E)$ cannot be solved in
time $O(|S|^{k-\delta})$.

##  6 Lower bounds for DT-Construction

In this section we prove Lemma 3.1 and use it to derive Theorems 2 and 3. The
high-level idea behind Lemma 3.1 is to show how, given a set cover instance
$\mathcal{S}$, we can construct a function $f$ and a distribution
$\mathcal{D}$ such that the optimal set cover size for $\mathcal{S}$ is
reflected in the the complexity of $f$ under $\mathcal{D}$.

######  Definition 2 ($\Gamma_{\mathcal{S}}$ and $\mathcal{D}_{\mathcal{S}}$).

Let $\mathcal{S}=(S,U,E)$ be a set cover instance with $|S|=n$. We identify
each universe element $u\in U$ with a vector $\\{0,1\\}^{n}$, the indicator
vector of its neighborhood set $\mathcal{N}_{\mathcal{S}}(u)$ (i.e. the
indicator vector of the sets that contain $u$). We define the partial function
$\Gamma_{\mathcal{S}}:\\{0,1\\}^{n}\to\\{0,1\\}$ as follows:

$\Gamma_{\mathcal{S}}(x)=\begin{cases}0&\text{$x=0^{n}$}\\\ 1&\text{$x=u$,
$u\in U$}.\end{cases}$

The distribution $\mathcal{D}_{\mathcal{S}}$ over the support of
$\Gamma_{\mathcal{S}}$ is given by the pmf

$\mathcal{D}_{\mathcal{S}}(x)=\begin{cases}\frac{1}{2}&\text{$x=0^{n}$}\\\
\frac{1}{2|U|}&\text{$x=u,u\in U$}.\end{cases}$

When $\mathcal{S}$ is clear from context we will drop the subscript and simply
write $\Gamma$ and $\mathcal{D}$. We observe that given any set cover
$C\subseteq S$, the monotone disjunction of the variables in $C$ computes
$\Gamma$ over $\mathcal{D}$. In particular, we have:

######  Fact 6.1.

If $\mathrm{opt}(\mathcal{S})\leq k$ then $\Gamma$ is a monotone disjunction
of $k$ variables under $\mathcal{D}$.

We now define a “parity-amplified” version of $\Gamma$. While $\Gamma$ is a
function over the domain $\\{0,1\\}^{n}$, this new function will be over the
domain $(\\{0,1\\}^{\ell})^{n}$ for some parameter $\ell\in\mathds{N}$.

##### Notation.

For a string $y\in(\\{0,1\\}^{\ell})^{n}$, we write $y_{i}\in\\{0,1\\}^{\ell}$
to denote the $i$th block of $y$, and $(y_{i})_{j}$ to denote the $j$th entry
of the $i$th block. We define the function
$\textnormal{BlockwisePar}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}^{n}$:

$\textnormal{BlockwisePar}(y)\coloneqq(\oplus y_{1},\ldots,\oplus y_{n}),$

where $\oplus y_{i}$ denotes the parity of the bits in $y_{i}$.

######  Definition 3 ($\Gamma_{\oplus\ell}$ and $\mathcal{D}_{\oplus\ell}$).

For $\Gamma$ and $\mathcal{D}$ as defined in Definition 2 and an integer
$\ell\in\mathds{N}$, we define the partial function
$\Gamma_{\oplus\ell}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$,

$\Gamma_{\oplus\ell}(y)=\Gamma(\textnormal{BlockwisePar}(y)).$

The distribution $\mathcal{D}_{\oplus\ell}$ over the support of
$\Gamma_{\oplus\ell}$ is defined as follows: to sample from
$\mathcal{D}_{\oplus\ell}$,

  1. 1.

First sample $\bm{x}\sim\mathcal{D}$.

  2. 2.

For each $i\in[n]$, sample $\bm{y}_{i}\sim\\{0,1\\}^{\ell}$ u.a.r. among all
strings satisfying $\oplus\bm{y}_{i}=\bm{x}_{i}$. Equivalently, sample
$\bm{y}\sim(\\{0,1\\}^{\ell})^{n}$ u.a.r. among all strings satisfying
$\textnormal{BlockwisePar}(\bm{y})=\bm{x}$.

######  Fact 6.2 (Blockwise parity of $\mathcal{D}_{\oplus\ell}$ induces
$\mathcal{D}$).

For $\bm{y}\sim\mathcal{D}_{\oplus\ell}$, we have that
$\textnormal{BlockwisePar}(\bm{y})$ is distributed according to $\mathcal{D}$.

We have the following analogue of 6.1:

######  Fact 6.3.

If $\mathrm{opt}(\mathcal{S})\leq k$ then $\Gamma_{\oplus\ell}$ is a
$k\ell$-junta (a disjunction of $k$ many parities, each over $\ell$ variables)
under $\mathcal{D}_{\oplus\ell}$.

##### An equivalent way of sampling from $\mathcal{D}_{\oplus\ell}$.

For our proof of Lemma 3.1, it will be useful for us consider a different, but
equivalent, way of sampling from $\mathcal{D}_{\oplus\ell}$. For
$z\in(\\{0,1\\}^{\ell-1})^{n}$, $x\in\\{0,1\\}^{n}$, and $j\in[\ell]$, we
write $\textnormal{ParComplete}_{j}(z,x)$ to denote the string
$y\in(\\{0,1\\}^{\ell})^{n}$ where for each block $i\in[n]$,

  * $\circ$

All except the $j$th coordinate of $y_{i}\in\\{0,1\\}^{\ell}$ are filled in
according to $z_{i}\in\\{0,1\\}^{\ell-1}$.

$((y_{i})_{1},\ldots,(y_{i})_{j-1},(y_{i})_{j+1},\ldots,(y_{i})_{\ell})=((z_{i})_{1},\ldots,(z_{i})_{\ell-1}).$

  * $\circ$

The $j$th coordinate of $y_{i}$ is filled in with the unique bit so that
$\oplus y_{i}=x_{i}$.

##### Example.

Consider $n=4$ and $\ell=3$ and $j=2$. Then, we can view
$z=(z_{1},\ldots,z_{4})\in(\\{0,1\\}^{2})^{4}$ as a $4\times 2$ matrix where
the $i$th row is $z_{i}$. In this case, we may have for example:

$z=\begin{bmatrix}{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\end{bmatrix}\quad
x=\begin{bmatrix}1\\\ 1\\\ 0\\\
1\end{bmatrix}\quad\longrightarrow\quad\textnormal{ParComplete}_{j}(z,x)=\begin{bmatrix}{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{\bf
0}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{\bf
1}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{\bf
0}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}\\\
{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{1}}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{\bf
0}}&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}{0}}\end{bmatrix}.$

Note that the first and third columns of $\textnormal{ParComplete}_{j}(z,x)$,
colored teal, are exactly the first and second columns of $z$ respectively,
and that the second column of $\textnormal{ParComplete}_{j}(z,x)$, colored
purple, is filled in so that parity of each row of matches the corresponding
row of $x$.

######  Definition 4 (The distribution $\mathcal{D}_{\oplus\ell}^{j}$).

For $j\in[\ell]$, the distribution $\mathcal{D}_{\oplus\ell}^{j}$ is obtained
via the following sampling procedure: sample $\bm{x}\sim\mathcal{D}$,
$\bm{z}\sim(\\{0,1\\}^{\ell-1})^{n}$ u.a.r., and output
$\textnormal{ParComplete}_{j}(\bm{z},\bm{x})$.

The following proposition on the equivalence between
$\mathcal{D}_{\oplus\ell}$ and $\mathcal{D}_{\oplus\ell}^{j}$ can be easily
verified. We defer the calculation to Appendix B.

######  Proposition 6.4 ($\mathcal{D}_{\oplus\ell}^{j}$ is equivalent to
$\mathcal{D}_{\oplus\ell}$).

For all $j\in[\ell]$ and $y\in(\\{0,1\\}^{\ell})^{n}$,

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{\bm{y}=y}\right]=\underset{\bm{y}\sim\mathcal{D}^{j}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{\bm{y}=y}\right].$

### Constructiveness of $\Gamma_{\oplus\ell}$ and $\mathcal{D}_{\oplus\ell}$

We can efficiently compute both a circuit representation of
$\Gamma_{\oplus\ell}$ and a generator for the distribution
$\mathcal{D}_{\oplus\ell}$ from a given set cover instance.

######  Lemma 6.5 (Constructiveness of $\Gamma_{\oplus\ell}$ and
$\mathcal{D}_{\oplus\ell}$).

Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex set cover instance with $|S|=n$ and
let $\ell\leq N$ be a parameter. Then there is an algorithm that runs in
$\mathrm{poly}(N)$ time and outputs a circuit representation of
$\Gamma_{\oplus\ell}$ over $\mathcal{D}_{\oplus\ell}$ and a generator for the
distribution $\mathcal{D}_{\oplus\ell}$.

default preamble= for tree= circle, minimum size=0.7cm, inner sep=0.1pt, draw,
align=center, anchor=north, fill=white, l sep=1cm, s sep=0.5cm,
[$\lor$,name=lormain, s sep=0.5cm, calign=center, [,name=oplus1, s sep=0.1cm,
inner sep=-0.0cm,circle split, [$(y_{1})_{1}$,name=y11,tier=inputl,draw=white]
[,name=ldots21,draw=white,tier=inputl]
[$\ldots$,name=ldots22,draw=white,tier=inputl]
[,name=ldots23,draw=white,tier=inputl]
[$(y_{1})_{\ell}$,name=y1l,tier=inputl,draw=white] ]
[,name=ldots1,draw=white,before computing xy=s=-35]
[$\ldots$,name=ldots2,draw=white,before computing xy=s=0]
[,name=ldots3,draw=white,before computing xy=s=35] [,name=oplus2,s
sep=0.1cm,inner sep=-0.0cm,circle split,
[$(y_{n})_{1}$,name=yn1,tier=inputl,draw=white]
[,name=ldots31,draw=white,tier=inputl]
[$\ldots$,name=ldots32,draw=white,tier=inputl]
[,name=ldots33,draw=white,tier=inputl]
[$(y_{n})_{\ell}$,name=ynl,tier=inputl,draw=white] ] ] [black] (-1.75,-0.75)
.. controls +(south east:1cm) and +(south west:1cm) .. (1.75,-0.75); [black]
(-3.5,-2.75) .. controls +(south east:0.5cm) and +(south west:0.5cm) ..
(-1.5,-2.75); [xshift=-0.65cm,yshift=0.25cm] at (-2,-0.75) fan-in $n$;
[xshift=-0.75cm,yshift=0.25cm] at (-3.6,-2.75) fan-in $\ell$;
[draw,black,circle split,rotate=90,inner sep=-0.0cm,minimum size=0.7cm] at
(oplus2) ; [draw,black,circle split,rotate=90,inner sep=-0.0cm,minimum
size=0.7cm] at (oplus1) ; [draw,black,circle,inner sep=-0.0cm,minimum
size=0.7cm] at (lormain) ;

Figure 3: A depth-$2$ circuit for $\Gamma_{\oplus\ell}$ consisting of one top
gate that is an OR connected to $n$ PARITY gates, each of which is connected
to a disjoint block of $\ell$ input variables.

###### Proof.

We separate the proof into two parts. First, we give a circuit representation
of $\Gamma_{\oplus\ell}$, then we give a generator for
$\mathcal{D}_{\oplus\ell}$.

##### A circuit for $\Gamma_{\oplus\ell}$.

Recall that a circuit $\mathcal{C}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$
represents $\Gamma_{\oplus\ell}:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ over
$\mathcal{D}_{\oplus\ell}$ if
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(\mathcal{C},\Gamma_{\oplus\ell})=0$.
The function $\Gamma:\\{0,1\\}^{n}\to\\{0,1\\}$ is computed over $\mathcal{D}$
by the disjunction of all $n$ variables. That is,
$\mathrm{dist}_{\mathcal{D}}(\Gamma,x_{1}\lor\cdots\lor x_{n})=0$.777This
observation can equivalently be viewed as an application of 6.1 plus the fact
that $\mathrm{opt}(\mathcal{S})\leq|S|=n$ holds for all $\mathcal{S}$.
Therefore, for
$y=(y_{1},\ldots,y_{n})\in\mathrm{supp}(\mathcal{D}_{\oplus\ell})$,

$\displaystyle\Gamma_{\oplus\ell}(y)$ $\displaystyle=\Gamma(\oplus
y_{1},\ldots,\oplus y_{n})$ (Definition of $\Gamma_{\oplus\ell}$)
$\displaystyle=(\oplus y_{1})\lor\ldots\lor(\oplus y_{n})$
($\textnormal{BlockwisePar}(y)\in\mathrm{supp}(\mathcal{D})$)

It follows that the circuit given by

$\mathcal{C}(y)\coloneqq\bigvee_{i\in[n]}\bigoplus_{j\in[\ell]}(y_{i})_{j}$

computes $\Gamma_{\oplus\ell}$ over $\mathcal{D}_{\oplus\ell}$. See Figure 3
for an illustration of $\mathcal{C}$. Since this circuit has size $n\cdot\ell$
and depth $3$, the first part of the lemma statement follows.

##### A generator for $\mathcal{D}_{\oplus\ell}$.

Recall that a generator for a distribution takes uniform random bits as input
and outputs bits distributed according to the desired distribution. First, we
observe that there is an efficient generator for $\mathcal{D}$ using
$1+\log|U|$ uniform random bits. Specifically, use $1$ uniform random bit to
decide between the two cases:

  1. (1)

output $0^{n}$

  2. (2)

output $u\in U$ uniformly at random.

The second case can be accomplished with $\log|U|$ uniform random bits. Then
the following procedure generates the distribution
$\mathcal{D}_{\oplus\ell}^{1}$:

  1. (1)

use $n(\ell-1)$ uniform random bits to select $z\in(\\{0,1\\}^{\ell-1})^{n}$

  2. (2)

use $1+\log|U|$ bits to sample $\bm{x}\sim\mathcal{D}$

  3. (3)

output $\textnormal{ParComplete}_{1}(\bm{z},\bm{x})$.

By Proposition 6.4, this procedure equivalently generates the distribution
$\mathcal{D}_{\oplus\ell}$. The procedure uses $n(\ell-1)+1+\log|U|$ bits. We
can assume without loss of generality that $1+\log|U|\leq|S|=n$888If
$|S|<1+\log|U|$, we just replicate sets until $|U|\leq|S|$. This change at
most doubles $N$ and does not affect $\mathrm{opt}(\mathcal{S})$. so that
$n(\ell-1)+1+\log|U|\leq n\ell$. It follows that this procedure efficiently
generates $\mathcal{D}_{\oplus\ell}$ from $n\ell$ uniform random bits. ∎

###  6.1 Warmup for Lemma 3.1: Lower bounds against decision tree hypotheses

We will prove Lemma 3.1 with the function being $\Gamma_{\oplus\ell}$ and the
distribution being $\mathcal{D}_{\oplus\ell}$. The first bullet of the lemma
statement is given by 6.3, and so the bulk of the remaining work goes into
establishing the second bullet of the lemma statement.

We begin with a warmup, showing the weaker statement that
$\Gamma_{\oplus\ell}$ is far from any small decision tree under
$\mathcal{D}_{\oplus\ell}$. This proof will illustrate many of the key ideas
in the actual proof for DNFs, which we give in the next subsection.
Furthermore, this lower bound is already sufficient to establish Theorem 1,
and will be the starting point of our lower bounds for DT-Estimation that we
prove in the next section.

######  Lemma 6.6.

Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex set cover instance and let
$\ell\geq 2$. If $T:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a decision tree of
size $|T|<2^{\mathrm{opt}(\mathcal{S}){\ell}/8}$, then
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(T,\Gamma_{\oplus\ell})\geq 1/(4N)$.

##### High level idea.

There are three main steps:

  1. 1.

No decision tree with small average depth can approximate $\Gamma$ under
$\mathcal{D}$ (6.7).

  2. 2.

Any decision tree with small average depth that approximates
$\Gamma_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$ can be used to
construct decision tree of much smaller average depth that approximates
$\Gamma$ under $\mathcal{D}$ (6.8). This is the key claim.

  3. 3.

Any small size decision tree must have small average depth with respect to
$\mathcal{D}_{\oplus\ell}$ (6.10).

Together, these three claims imply that no small size decision tree can
approximate $\Gamma_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$, thereby
yielding Lemma 6.6.

Set cover $C$Decision tree
$T$${{x_{8}}}$${{x_{3}}}$${\vdots}$${{x_{17}}}$${\vdots}$${0}$${\vdots}$
Figure 4: Any decision tree for $\Gamma$ implicitly defines a set cover of
$\mathcal{S}$ consisting of the variables highlighted in red.

######  Claim 6.7 (Good approximators for $\Gamma$ require large depth).

Let $T:\\{0,1\\}^{n}\to\\{0,1\\}$ be a decision tree and $\mathcal{S}=(S,U,E)$
be an $N$-vertex set cover instance with $|S|=n$. If
$\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{x})]<\mathrm{opt}(\mathcal{S})/2$
then $\mathrm{dist}_{\mathcal{D}}(T,\Gamma)\geq 1/(2N)$.

###### Proof.

Let $T$ be a decision tree satisfying $\underset{\bm{x}\sim
D}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{x})]<\mathrm{opt}(\mathcal{S})/2$.
We actually prove the stronger claim that
$\mathrm{dist}_{\mathcal{D}}(T,\Gamma)\geq 1/(2|U|)$. Suppose for
contradiction that $\mathrm{dist}_{\mathcal{D}}(T,\Gamma)<1/(2|U|)$. Each
$x\in\mathrm{supp}(\mathcal{D})$ has mass $\geq 1/(2|U|)$ under $\mathcal{D}$
and so we must have $\mathrm{dist}_{\mathcal{D}}(T,\Gamma)=0$. Let
$C\subseteq[n]=S$ be the set of vertices that $T$ queries in the computation
of $0^{n}$ (equivalently, $C$ is the leftmost root-to-leaf path in $T$). See
Figure 4 for an illustration of $C$. Since
$\mathrm{dist}_{\mathcal{D}}(T,\Gamma)=0$, we have that
$T(0^{n})=\Gamma(0^{n})=0$.

We claim $C$ is a valid set cover for $\mathcal{S}$. Indeed, if some $u\in U$
is not covered by $C$, then $\mathcal{N}_{\mathcal{S}}(u)\cap C=\varnothing$,
and $u$ would follow this same path $C$ as $0^{n}$ in $T$. This would imply
that $0=T(u)\neq\Gamma(u)=1$, contradicting the fact that
$\mathrm{dist}_{\mathcal{D}}(T,\Gamma)=0$.

Since $C$ is a valid set cover, it follows that
$|C|\geq\mathrm{opt}(\mathcal{S})$ and so:

$\displaystyle\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{x})]$
$\displaystyle\geq\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{Pr}}}[\bm{x}=0^{n}]\cdot|C|$
($0pt_{T}({\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{0^{n}}})=|C|$)
$\displaystyle=\frac{|C|}{2}$ ($\mathcal{D}$ places weight $\frac{1}{2}$ on
$0^{n}$) $\displaystyle\geq\frac{\mathrm{opt}(\mathcal{S})}{2}$

which contradicts our original assumption on the average depth of $T$. ∎

Our high-level proof strategy for the next claim is loosely inspired by
[BKLS20] (which itself built on [BB19]). This proof also crucially relies on
Proposition 6.4.

######  Claim 6.8 (Good approximators for $\Gamma_{\oplus\ell}$ yield good
approximators for $\Gamma$).

Let $T:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ be a decision tree such that

$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(T,\Gamma_{\oplus\ell})\leq\varepsilon\quad\text{and}\quad\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{y})]\leq
d.$

Then there is a restriction $T^{*}:\\{0,1\\}^{n}\to\\{0,1\\}$ of $T$
satisfying

$\mathrm{dist}_{\mathcal{D}}(T^{*},\Gamma)\leq
2\varepsilon\quad\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T^{*}}(\bm{x})]\leq\frac{2d}{\ell}.$

###### Proof.

Recalling the notation from Definition 4, when
$\underline{z}\in(\\{0,1\\}^{\ell-1})^{n}$ and $\underline{j}\in[\ell]$ are
fixed, the function
$x\mapsto\textnormal{ParComplete}_{\underline{j}}(\underline{z},x)$ is a
function from $\\{0,1\\}^{n}$ to $(\\{0,1\\}^{\ell})^{n}$. Our proof proceeds
by finding a suitable $\underline{z}$ and $\underline{j}$ so that $x\mapsto
T(\textnormal{ParComplete}_{\underline{j}}(\underline{z},x))$ is a tree of
much smaller average depth and computes $\Gamma$ accurately over
$\mathcal{D}$. Restricting $T$ according to the values specified by
$\underline{z}$ and $\underline{j}$ yields the desired decision tree.

For $j\in[\ell]$ and $y\in(\\{0,1\\}^{\ell})^{n}$, write $q_{j}(y)$ for the
number of times that $T$, on the input $y$, queries $(y_{i})_{j}$ for some
$i\in[n]$. Thus, $0pt_{T}(y)=\sum_{j\in[\ell]}q_{j}(y)$ and likewise

$\sum_{j\in[\ell]}\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[q_{j}(\bm{y})]=\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{y})]\leq
d.$

Let $\underline{j}\in[\ell]$ be the index that minimizes
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[q_{j}(\bm{y})]$.
By averaging, this $\underline{j}$ must satisfy
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[q_{\underline{j}}(\bm{y})]\leq
d/\ell$. By Proposition 6.4, we can write

$\displaystyle\frac{d}{\ell}$
$\displaystyle\geq\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[q_{\underline{j}}(\bm{y})]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}^{\underline{j}}}[q_{\underline{j}}(\bm{y})]$
(Proposition 6.4)
$\displaystyle=\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{\mathds{E}}}}\left[\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\right]\right].$
(Definition of $\mathcal{D}_{\oplus\ell}^{j}$)

Similarly, we also have:

$\displaystyle\varepsilon$
$\displaystyle\geq\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}[T(\bm{y})\neq\Gamma_{\oplus\ell}(\bm{y})]$
$\displaystyle=\underset{\bm{y}\sim\mathcal{D}^{\underline{j}}_{\oplus\ell}}{\operatorname{{Pr}}}[T(\bm{y})\neq\Gamma_{\oplus\ell}(\bm{y})]$
(Proposition 6.4)
$\displaystyle=\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{\mathds{E}}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\Gamma(\bm{x})\right]\right].$
(Definition of $\mathcal{D}_{\oplus\ell}^{j}$)

Applying Markov’s inequality twice, we have

$\displaystyle\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\Gamma(\bm{x})\right]>2\varepsilon\right]<\frac{1}{2}$
$\displaystyle\text{and}\quad\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\right]>\frac{2d}{\ell}\right]<\frac{1}{2}.$

And thus by a union bound, there is some fixed
$\underline{z}\in\\{0,1\\}^{n(\ell-1)}$ satisfying

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\neq\Gamma(\bm{x})\right]\leq
2\varepsilon\quad\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\right]\leq\frac{2d}{\ell}.$

The tree $T^{*}$ is formed by restricting $T$ according to $\underline{z}$ and
$\underline{j}$. Also, this tree $T^{*}$ satisfies
$0pt_{T^{*}}(x)=q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},x))$
by construction. The claim then follows. ∎

To prove 6.10, we first need a simple proposition stating that the probability
a string $\bm{y}\sim\mathcal{D}_{\oplus\ell}$ matches some fixed substring
decays exponentially with the length of the substring.

######  Proposition 6.9 ($\mathcal{D}_{\oplus\ell}$ is uniform-like).

Let $\ell\geq 2$. For all $R\subseteq[\ell]$, $r\in\\{0,1\\}^{|R|}$,
$i\in[n]$, and $b\in\\{0,1\\}$, we have

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}[(\bm{y}_{i})_{R}=r\mid\oplus\bm{y}_{i}=b]\leq
2^{-|R|/2}$

where $(\bm{y}_{i})_{R}\in\\{0,1\\}^{|R|}$ is the substring of
$\bm{y}_{i}\in\\{0,1\\}^{\ell}$ consisting of the coordinates specified by
$R$.

###### Proof.

We first consider the case when $|R|<\ell$. By the definition of
$\mathcal{D}_{\oplus\ell}$, the conditional distribution in question is the
uniform distribution over all strings in $\\{0,1\\}^{\ell}$ whose parity is
$b$. The marginal distribution of this distribution over any set of $|R|<\ell$
coordinates is uniform, and therefore:

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[(\bm{y}_{i})_{R}=r\mid\oplus\bm{y}_{i}=b]=2^{-|R|}.$

If $|R|=\ell$, then depending on whether the parity of the bits in $r$ match
$b$, we have:

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[\bm{y}_{i}=r\mid\oplus\bm{y}_{i}=b]=\begin{cases}0&\text{if
$\oplus r\neq b$}\\\ 2^{-|R|+1}&\text{if $\oplus r=b$}.\end{cases}$

In either case, we have the desired probability bound. ∎

######  Claim 6.10 (Small trees have small average depth).

Let $T$ be a size-$s$ decision tree, then

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[0pt_{T}(\bm{y})\right]\leq
2\log s.$

###### Proof.

We start by upper bounding $\operatorname{{Pr}}[\text{$\bm{y}$ reaches $L$}]$
for any fixed leaf $L$ of $T$. For each block $i\in[n]$, we write $R_{i}(L)$
to denote the variables from the $i$th block queried on the root-to-$L$ path,
and $r_{i}(L)\in\\{0,1\\}^{R_{i}(L)}$ to denote the values that the path
assigns to these variables. Note that $\sum_{i\in[n]}|R_{i}(L)|=|L|$, the
depth of $L$ in $T$. With this notation in hand, for any fixed
$x\in\\{0,1\\}^{n}$, we have

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[\text{$\bm{y}$
reaches $L$}\mid\textnormal{BlockwisePar}(\bm{y})=x]$
$\displaystyle=\prod_{i\in[n]}\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[(\bm{y}_{i})_{R_{i}(L)}=r_{i}(L)\mid\textnormal{BlockwisePar}(\bm{y})=x]$
(Independence of the $\bm{y}_{i}$’s for fixed $x$)
$\displaystyle=\prod_{i\in[n]}\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[(\bm{y}_{i})_{R_{i}(L)}=r_{i}(L)\mid\oplus\bm{y}_{i}=x_{i}]$
$\displaystyle\leq\prod_{i\in[n]}2^{-|R_{i}(L)|/2}$ (Proposition 6.9)
$\displaystyle=2^{-|L|/2}.$

Since this holds for every $x$, it follows that

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[\text{$\bm{y}$
reaches $L$}]\leq 2^{-|L|/2}.$ (1)

We therefore conclude that

$\displaystyle\textstyle\frac{1}{2}\cdot\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[0pt_{T}(\bm{y})\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}\left[\log\big{(}2^{0pt_{T}(\bm{y})/2}\big{)}\right]$
$\displaystyle\leq\log\left(\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[2^{0pt_{T}(\bm{y})/2}]\right)$
(Concavity of $\log(\cdot)$) $\displaystyle=\log\left(\sum_{L\in
T}\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[\text{$y$
reaches $L$}]\cdot 2^{|L|/2}\right)$ $\displaystyle\leq\log\left(\sum_{L\in
T}2^{-|L|/2}\cdot 2^{|L|/2}\right)$ (Equation 1) $\displaystyle=\log s.$

Rearranging completes the proof. ∎

##### Putting things together: Proof of Lemma 6.6.

Suppose there is some tree $T$ computing $\Gamma_{\oplus\ell}$ with $|T|\leq
2^{\mathrm{opt}(\mathcal{S})\ell/8}$. We show that
$\mathrm{dist}(T,\Gamma_{\oplus\ell})\geq 1/(4N)$. Suppose for contradiction
that $\mathrm{dist}(T,\Gamma_{\oplus\ell})<1/(4N)$. By 6.10, we have
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{0pt_{T}(\bm{y})}\right]<2\cdot\log\left(2^{\mathrm{opt}(\mathcal{S})\ell/8}\right)=\mathrm{opt}(\mathcal{S})\ell/4$.
Then by 6.8 there is a decision tree $T^{*}$ satisfying

$\mathrm{dist}_{\mathcal{D}}(T^{*},\Gamma)<\frac{1}{2N}\qquad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T^{*}}(\bm{x})]<\frac{\mathrm{opt}(\mathcal{S})}{2}.$

But this contradicts 6.7. $\square$

###  6.2 Proof of Lemma 3.1: Lower bounds against DNF hypotheses

We extend Lemma 6.6 to show that $\Gamma_{\oplus\ell}$ cannot even be
approximated by small DNFs. This extension will allow us to complete the proof
of Lemma 3.1. For this section, we use the negation of $\Gamma$:

$\overline{\Gamma}(x)=\begin{cases}1&x=0^{n}\\\ 0&x=u,u\in U\end{cases}.$

Analogous to 6.1, any set cover $C\subseteq S$ yields a conjunction of $k$
literals which computes $\Gamma$ under $\mathcal{D}$.

######  Fact 6.11.

If $\mathrm{opt}(\mathcal{S})\leq k$, then $\overline{\Gamma}$ is a
conjunction of $k$ literals under $\mathcal{D}$.

The literals in this case are the negation of the variables in the set cover
$C\subseteq S$. We will likewise use the negation of $\Gamma_{\oplus\ell}$:

$\overline{\Gamma}_{\oplus\ell}(y)=\overline{\Gamma}(\textnormal{BlockwisePar}(y)).$

The analogue of 6.3 becomes:

######  Fact 6.12.

If $\mathrm{opt}(\mathcal{S})\leq k$ then $\overline{\Gamma}_{\oplus\ell}$ is
a $k\ell$-junta (a conjunction of $k$ many parities, each over $\ell$
variables) under $\mathcal{D}_{\oplus\ell}$.

Ultimately, this change allows us to prove that
$\overline{\Gamma}_{\oplus\ell}$ cannot be approximated by small-size DNF
formulas. If instead, one were interested in proving hardness against CNF
formulas, one could work directly with the unnegated $\Gamma_{\oplus\ell}$. We
find that working with DNFs is slightly less cumbersome than with CNFs which
is why we focus on the negated function in this section. Specifically, we
prove the following extension of Lemma 6.6.999The lemma is indeed an
“extension” because any size-$s$ decision tree computing $\Gamma_{\oplus\ell}$
yields a size-$s$ decision tree computing $\overline{\Gamma}_{\oplus\ell}$
simply by flipping leaf labels, and so Lemma 6.6 can equivalently be viewed as
a statement about $\overline{\Gamma}_{\oplus\ell}$.

######  Lemma 6.13.

Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex set cover instance and let
$\ell\geq 2$. If $F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a DNF of size
$|F|<2^{\mathrm{opt}(\mathcal{S})\ell/16}$, then
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(\overline{\Gamma}_{\oplus\ell},F)\geq
1/(4N)$.

The high level proof strategy follows that of Lemma 6.6 and can be divided
into the same three steps outlined in Section 6.1. The only difference is that
“average depth” is no longer a well-defined quantity with DNF formulas.
Instead, we consider “average width” which is a generalization of average
depth suited to our purposes.

######  Claim 6.14 (Good approximators for $\overline{\Gamma}$ require large
width).

Let $F:\\{0,1\\}^{n}\to\\{0,1\\}$ be a DNF formula and $\mathcal{S}=(S,U,E)$
be an $N$-vertex set cover instance with $|S|=n$. If
$\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{x})}\right]<\mathrm{opt}(\mathcal{S})/2$,
then $\mathrm{dist}_{\mathcal{D}}(F,\overline{\Gamma})\geq 1/(2N)$.

###### Proof.

Let $F=t_{1}\lor\cdots\lor t_{s}$ be a DNF formula. If $F(0^{n})=0$, then
$\mathrm{dist}_{\mathcal{D}}(F,\overline{\Gamma})\geq 1/2$ since
$\overline{\Gamma}(0^{n})=1$. Otherwise, let $t_{i}$ be the smallest width
term such that $t_{i}(0^{n})=1$ so that $|t_{i}|=\mathrm{width}_{F}(0^{n})$.
Since $t_{i}$ accepts the all $0$s input, it is a conjunction of $|t_{i}|$
negated variables. Let $C\subseteq S$ be the set of variables in $t_{i}$.
Since

$\frac{|t_{i}|}{2}=\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{Pr}}}\left[{\bm{x}=0^{n}}\right]\cdot\mathrm{width}_{F}(0^{n})\leq\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{x})}\right]<\frac{\mathrm{opt}(\mathcal{S})}{2},$

$C$ is not a set cover. Let $u\in U$ be some vertex not covered by $C$:
$\mathcal{N}_{\mathcal{S}}(u)\cap C=\varnothing$. Then, $u$ is encoded with
$0$s for all variables in $C$. It follows that $t_{i}(u)=1$ and $F(u)=1\neq
0=\overline{\Gamma}(u)$. Therefore:

$\mathrm{dist}_{\mathcal{D}}(F,\overline{\Gamma})\geq\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{Pr}}}\left[{\bm{x}=u}\right]=\frac{1}{2|U|}\geq\frac{1}{2N}.\qed$

######  Claim 6.15 (Good approximators for $\overline{\Gamma}_{\oplus\ell}$
yield good approximators for $\overline{\Gamma}$).

Let $F:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ be a DNF formula such that

$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(F,\overline{\Gamma}_{\oplus\ell})\leq\varepsilon\quad\text{and}\quad\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{y})}\right]\leq
w.$

Then there is a restriction $F^{*}:\\{0,1\\}^{n}\to\\{0,1\\}$ of $F$
satisfying

$\mathrm{dist}_{\mathcal{D}}(F^{*},\overline{\Gamma})\leq
2\varepsilon\quad\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F^{*}}(\bm{x})}\right]\leq\frac{2w}{\ell}.$

###### Proof.

The proof is similar to that of 6.8. First, let $q_{j}(y)$ denote the number
of variables of the form $(y_{i})_{j}$ for some $i\in[n]$ appearing in the
smallest width term that accepts $y$ and $0$ if no term accepts $y$. Then,
$\mathrm{width}_{F}(y)=\sum_{j\in[\ell]}q_{j}(y)$ for all
$y\in\mathrm{supp}(D_{\oplus\ell})$. Therefore:

$\sum_{j\in[\ell]}\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{q_{j}(\bm{y})}\right]\leq
w.$

Let $\underline{j}\in[\ell]$ be the index that minimizes
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{q_{j}(\bm{y})}\right]$.
By averaging, $\underline{j}$ satisfies
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{q_{\underline{j}}(\bm{y})}\right]\leq
w/\ell$. Using Proposition 6.4:

$\displaystyle\frac{w}{\ell}$
$\displaystyle\geq\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{q_{\underline{j}}(\bm{y})}\right]$
$\displaystyle=\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}^{\underline{j}}}{\operatorname{{\mathds{E}}}}\left[{q_{\underline{j}}(\bm{y})}\right]$
(Proposition 6.4)
$\displaystyle=\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{\mathds{E}}}}\left[\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[{q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))}\right]\right].$
(Definition of $\mathcal{D}_{\oplus\ell}^{\underline{j}}$)

Similarly:

$\displaystyle\varepsilon$
$\displaystyle\geq\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}[F(\bm{y})\neq\overline{\Gamma}_{\oplus\ell}(\bm{y})]$
$\displaystyle=\underset{\bm{y}\sim\mathcal{D}^{\underline{j}}_{\oplus\ell}}{\operatorname{{Pr}}}[F(\bm{y})\neq\overline{\Gamma}_{\oplus\ell}(\bm{y})]$
(Proposition 6.4)
$\displaystyle=\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{\mathds{E}}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[F(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\overline{\Gamma}(\bm{x})\right]\right].$
(Definition of $\mathcal{D}_{\oplus\ell}^{j}$)

Applying Markov’s inequality twice, we have

$\displaystyle\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[F(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\overline{\Gamma}(\bm{x})\right]>2\varepsilon\right]<\frac{1}{2}$
$\displaystyle\text{and}\quad\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\right]>\frac{2w}{\ell}\right]<\frac{1}{2}.$

And thus by a union bound, there is some fixed
$\underline{z}\in\\{0,1\\}^{n(\ell-1)}$ satisfying

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[F(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\neq\overline{\Gamma}(\bm{x})\right]\leq
2\varepsilon\quad\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\right]\leq\frac{2w}{\ell}.$

The DNF formula $F^{*}$ is formed by restricting $F$ according to the string
$\underline{z}$. Also, this $F^{*}$ satisfies
$\mathrm{width}_{F^{*}}(x)=q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},x))$
by construction. The claim then follows. ∎

######  Claim 6.16 (Small DNFs have small average width).

Let $F$ be a size-$s$ DNF formula for $s\geq 4$ such that
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(F,\overline{\Gamma}_{\oplus\ell})\leq
1/4$, then

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{y})}\right]\leq
4\log(s).$

###### Proof.

Let $F=t_{1}\lor\cdots\lor t_{s}$ be a DNF formula with $s$ terms satisfying
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(F,\overline{\Gamma}_{\oplus\ell})\leq
1/4$. We start by upper bounding the conditional probability
$\operatorname{{Pr}}[t(\bm{y})=1\mid F(\bm{y})=1]$ for any fixed term
$t\in\\{t_{1},\ldots,t_{s}\\}$. We bound the probabilities
$\operatorname{{Pr}}[t(\bm{y})=1]$ and $\operatorname{{Pr}}[F(\bm{y})=1]$
separately.

  1. (1)

$\operatorname{{Pr}}[F(\bm{y})=1]\geq 1/4$. We write

$\displaystyle\frac{1}{4}$
$\displaystyle\geq\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(F,\overline{\Gamma}_{\oplus\ell})$
$\displaystyle\geq\left|\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{F(\bm{y})=1}\right]-\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{\overline{\Gamma}_{\oplus\ell}(\bm{y})=1}\right]\right|$
$\displaystyle=\left|\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{F(\bm{y})=1}\right]-\frac{1}{2}\right|$

which implies $\operatorname{{Pr}}[F(\bm{y})=1]\geq 1/4$.

  2. (2)

$\operatorname{{Pr}}[t(\bm{y})=1]\leq 2^{-|t|/2}$. For each $i\in[n]$, let
$R_{i}(t)$ denote the variables from the $i$th block which appear in the term
$t$ and let $r_{i}(t)\in\\{0,1\\}^{R_{i}(t)}$ denote the values assigned by
those variables (i.e. $1$ if the variable is unnegated in $t$ and $0$ if the
variable is negated in $t$). Then $\sum_{i\in[n]}|R_{i}(t)|=|t|$, the width of
$t$. Using this notation, for any fixed $x\in\mathrm{supp}(\mathcal{D})$:

$\displaystyle\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{t(\bm{y})=1\mid\textnormal{BlockwisePar}(\bm{y})=x}\right]$
$\displaystyle=\prod_{i\in[n]}\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{(\bm{y}_{i})_{R_{i}(t)}=r_{i}(t)\mid\textnormal{BlockwisePar}(\bm{y})=x}\right]$
(Independence of the $\bm{y}_{i}$’s for fixed $x$)
$\displaystyle=\prod_{i\in[n]}\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{(\bm{y}_{i})_{R_{i}(t)}=r_{i}(t)\mid\oplus\bm{y}_{i}=x_{i}}\right]$
$\displaystyle\leq\prod_{i\in[n]}2^{-|R_{i}(t)|/2}$ (Proposition 6.9)
$\displaystyle=2^{-|t|/2}.$

Since this holds for any fixed $x$, it follows that

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{t(\bm{y})=1}\right]\leq
2^{-|t|/2}.$

Together, these two points imply

$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{t(\bm{y})=1\mid
F(\bm{y})=1}\right]=\frac{\operatorname{{Pr}}[t(\bm{y})=1]}{\operatorname{{Pr}}[F(\bm{y})=1]}\leq
2^{-|t|/2+2}.$ (2)

Lastly:

$\displaystyle\frac{1}{2}\cdot\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{y})}\right]-2$
$\displaystyle=\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{\log\left({2^{\mathrm{width}_{F}(\bm{y})/2-2}}\right)}\right]$
$\displaystyle\leq\log\left({\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{2^{\mathrm{width}_{F}(\bm{y})/2-2}}\right]}\right)$
(Concavity of $\log$)
$\displaystyle=\log\left({\sum_{b\in\\{0,1\\}}\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{F(\bm{y})=b}\right]\cdot\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{2^{\mathrm{width}_{F}(\bm{y})/2-2}\mid
F(\bm{y})=b}\right]}\right)$
$\displaystyle\leq\log\left({\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{2^{\mathrm{width}_{F}(\bm{y})/2-2}\mid
F(\bm{y})=1}\right]}\right)$ ($\mathrm{width}_{F}(\bm{y})=0$ if $F(\bm{y})=0$
and $\operatorname{{Pr}}[F(\bm{y})=b]\leq 1$)
$\displaystyle\leq\log\left({\sum_{i\in[s]}2^{|t_{i}|/2}\cdot\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}\left[{t_{i}(\bm{y})=1\mid
F(\bm{y})=1}\right]}\right)$
$\displaystyle=\log\left({\sum_{i\in[s]}2^{|t_{i}|/2-2}\cdot
2^{-|t_{i}|/2+2}}\right)$ (Equation 2) $\displaystyle=\log s.$

Rearranging and applying the assumption that $2\leq\log(s)$ completes the
proof. ∎

##### Putting things together: Proof of Lemma 6.13

Suppose there is some DNF formula $F$ computing
$\overline{\Gamma}_{\oplus\ell}$ with $|F|\leq
2^{\mathrm{opt}(\mathcal{S})\ell/16}$. We show that
$\mathrm{dist}(F,\overline{\Gamma}_{\oplus\ell})\geq 1/(4N)$. Suppose for
contradiction that $\mathrm{dist}(T,\overline{\Gamma}_{\oplus\ell})<1/(4N)\leq
1/4$. If $|F|<4$, we add dummy terms (e.g. by replicating the terms already in
$F$) so that $|F|\geq 4$. We can then apply 6.16:
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{\mathrm{width}_{F}(\bm{y})}\right]<4\cdot\log\left(2^{\mathrm{opt}(\mathcal{S})\ell/16}\right)=\mathrm{opt}(\mathcal{S})\ell/4$.
Then by 6.15, there is a DNF formula $F^{*}$ satisfying

$\mathrm{dist}_{\mathcal{D}}(F^{*},\Gamma)<\frac{1}{2N}\qquad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{F^{*}}(\bm{x})]<\frac{\mathrm{opt}(\mathcal{S})}{2}.$

But such an $F^{*}$ contradicts 6.14. $\square$

##### The last steps: finishing the proof of Lemma 3.1.

We prove the following lemma which immediately implies Lemma 3.1.

######  Lemma 6.17 ($\overline{\Gamma}_{\oplus\ell}$ proves Lemma 3.1).

Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex instance of $(k,k^{\prime})$-Set-
Cover and $\ell\leq N$. Then there is an algorithm that runs in
$\mathrm{poly}(N)$ time and outputs a circuit representation of
$\overline{\Gamma}_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$ and a
generator for $\mathcal{D}_{\oplus\ell}$ which satisfies:

  * $\circ$

If $\mathrm{opt}(\mathcal{S})\leq k$, then $\overline{\Gamma}_{\oplus\ell}$ is
a $k\ell$-junta under $\mathcal{D}_{\oplus\ell}$.

  * $\circ$

If $\mathrm{opt}(\mathcal{S})>k^{\prime}$, then any DNF of size $\leq
2^{k^{\prime}\ell/16}$ is $\frac{1}{4N}$-far from
$\overline{\Gamma}_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$.

###### Proof.

By Lemma 6.5, there is an algorithm that runs in $\mathrm{poly}(N)$ time and
outputs a circuit representation of ${\Gamma}_{\oplus\ell}$ and a generator
for $\mathcal{D}_{\oplus\ell}$. Augmenting the circuit for
${\Gamma}_{\oplus\ell}$ with a single NOT gate yields a circuit for
$\overline{\Gamma}_{\oplus\ell}$. Moreover, we have shown:

  * $\circ$

if $\mathrm{opt}(\mathcal{S})\leq k$, then $\overline{\Gamma}_{\oplus\ell}$ is
a $k\ell$-junta under $\mathcal{D}_{\oplus\ell}$; (6.12)

  * $\circ$

if $\mathrm{opt}(\mathcal{S})>k^{\prime}$, then any DNF of size $\leq
2^{k^{\prime}\ell/16}$ is $\frac{1}{4N}$-far from
$\overline{\Gamma}_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$; (Lemma
6.13)

which completes the proof of the lemma. ∎

###  6.3 Implications of Lemma 3.1

####  6.3.1 Proofs of Theorem 1 and Theorem 2

In this section, we prove the following theorem.

######  Theorem 12.

Let $\mu:\mathds{N}\to\mathds{N}$ be any computable, non-decreasing function
satisfying $\mu(n)=o\left({\frac{\log\log n}{\log\log\log n}}\right)$.
Assuming randomized ETH, there is some constant $\lambda\in(0,1)$, a function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, and distribution $\mathcal{D}$ over
$\\{0,1\\}^{n}$ such that DT-Construction$(s,1/n)$ cannot be solved in time

${s^{\lambda\cdot\left(\frac{\log\log s}{\mu(n)\log\log\log s}\right)}}$

for $f$ and for any $s\leq n^{\mu(n)}$, even if $f$ is promised to be a $(\log
n)$-junta over $\mathcal{D}$ and the algorithm returns a DNF hypothesis.

Theorems 1 and 2 immediately follow as a consequence of this theorem by
choosing $\mu(n)=1$.

###### Proof of Theorem 12.

We give a reduction from gapped set cover. Let $\mathcal{S}=(S,U,E)$ be an
$N$-vertex $\left(k,\frac{1}{2}\left(\frac{\log N}{\log\log
N}\right)^{1/k}\right)$-Set-Cover instance where $k$ is taken to be

$k=\frac{1}{2}\cdot\frac{\log\log N}{\log\log\log N}.$

Using Lemma 6.17 with $\ell=\log(N)/k$, we obtain the target function
$\overline{\Gamma}_{\oplus\ell}:\\{0,1\\}^{N\ell}\to\\{0,1\\}$ and the
distribution $\mathcal{D}_{\oplus\ell}$.101010Technically,
$\overline{\Gamma}_{\oplus\ell}$ is a function defined on $|S|\ell$ bits, but
as $|S|\leq N$ we can pad the inputs to be $N\ell$ bits long.

Let $\mu:\mathds{N}\to\mathds{N}$ be as in the theorem statement. Set
$s\coloneqq(N\ell)^{\mu(N\ell)}$. We show that any algorithm for DT-
Construction$(s,1/(4N))$ running in time
$\displaystyle{s^{\lambda\cdot\left(\frac{\log\log s}{\mu(N\ell)\log\log\log
s}\right)}}$ for $0<\lambda\leq 1/128$ can be used to solve $\mathcal{S}$ in
time $N^{8\lambda\cdot k}$ even if the output of the algorithm is a DNF
formula.

We run the algorithm for DT-Construction$(s,1/(4N))$ on
$\overline{\Gamma}_{\oplus\ell}$ and $\mathcal{D}_{\oplus\ell}$ and terminate
it after

$N^{4\lambda\cdot\left(\frac{\log\log N}{\log\log\log N}\right)}=N^{8\lambda
k}$

times steps. The algorithm outputs some DNF formula $F$. We estimate the error
of $F$ and $\overline{\Gamma}_{\oplus\ell}$ over the distribution
$\mathcal{D}_{\oplus\ell}$ and output “Yes” if the error is $\leq 1/(4N)$ and
“No” otherwise.

##### Runtime.

Constructing the circuit for $\overline{\Gamma}_{\oplus\ell}$ and the
generator for $\mathcal{D}_{\oplus\ell}$ requires $\mathrm{poly}(N)$ time by
Lemma 6.17. We can efficiently sample from the distribution
$\mathcal{D}_{\oplus\ell}$ to efficiently estimate the error of the output
decision tree via random samples. So the overall runtime of our algorithm is
$\leq N^{8\lambda k}$.

##### Correctness.

To prove the reduction is correct, we show that if there is a size $k$ set
cover for $\mathcal{S}$ then we output Yes with high probability and otherwise
if $S$ requires a set cover of size at least

$\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}$

then we output No with high probability.

Yes case: $\mathrm{opt}(S)\leq k$. In this case, by Lemma 6.17,
$\overline{\Gamma}_{\oplus\ell}$ is computed exactly by a
$\mathrm{opt}(S)\ell\leq k\ell=\log N$-junta over $\mathcal{D}_{\oplus\ell}$.
Hence, it is computed by a DNF of width $k\ell$. The size of this DNF is at
most $2^{k\cdot\ell}=N\leq(N\ell)^{\mu(N\ell)}=s$. To upper bound the runtime,
we start by calculating

$\displaystyle\frac{\log\log s}{\log\log\log s}$
$\displaystyle\leq\frac{\log\left({2\mu(N^{2})\log N}\right)}{\log\log\log N}$
$\displaystyle\leq\frac{\log\left({(\log N)^{2}}\right)}{\log\log\log N}$
(Assumption on $\mu$: $2\mu(N^{2})\leq\log N$) $\displaystyle=4k.$ (3)

By our assumption on DT-Construction$(s,1/(4N))$, in the yes case, the
algorithm runs for

$\displaystyle s^{\lambda\cdot\left(\frac{\log\log s}{\mu(N\ell)\log\log\log
s}\right)}$ $\displaystyle\leq s^{4\lambda k/\mu(N\ell)}$ (Equation 3)
$\displaystyle=(N\ell)^{4\lambda k}$ ($s=(N\ell)^{\mu(N\ell)}$)
$\displaystyle\leq N^{8\lambda k}$ ($N\ell\leq N^{2}$)

time steps and outputs a size-$s$ DNF formula with error $\leq 1/(4N)$.
Therefore, our algorithm outputs Yes with high probability (where the
probability is taken over the random sampling procedure).

No case: $\mathrm{opt}(S)>\frac{1}{2}\left(\frac{\log N}{\log\log
N}\right)^{1/k}.$ By Lemma 6.17 any DNF for $\overline{\Gamma}_{\oplus\ell}$
with size at most $2^{\mathrm{opt}(\mathcal{S})\ell/16}$ has error at least
$1/(4N)$. The runtime bound on our algorithm serves as an upper bound on the
size of the DNF built by the DT-Construction algorithm. Therefore, it is
sufficient to show that

$N^{8\lambda\cdot k}<2^{\mathrm{opt}(S)\ell/16}$ (4)

because this bound shows that our DNF must have error at least $1/(4N)$.
Recalling that $k=\frac{1}{2}\cdot\frac{\log\log N}{\log\log\log N}$, we have
$(2k^{2})^{k}<\frac{\log N}{\log\log N}$. We observe

$\displaystyle\mathrm{opt}(\mathcal{S})$
$\displaystyle>\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}$
$\displaystyle>k^{2}$ $\displaystyle\geq 128\lambda k^{2}$ ($128\lambda\leq
1$)

which shows $k\ell(8\lambda k)<\mathrm{opt}(\mathcal{S})\ell/16$.
Exponentiating both sides and using the fact that $N=2^{k\ell}$ completes the
calculation and establishes Equation 4. It follows that our algorithm finds
the error to be $>1/(4N)$ and outputs No with high probability.

##### Refuting randomized ETH.

We now have an algorithm for solving $\left(k,\frac{1}{2}\left(\frac{\log
N}{\log\log N}\right)^{1/k}\right)$-Set-Cover in time $N^{8\lambda k}$ with
high probability. By Theorem 7, there is a constant $c\in(0,1)$ such that
$\left(k,\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}\right)$-Set-
Cover cannot be solved with high probability in time $N^{ck}$. Therefore, we
derive a contradiction for any $\lambda\leq\min\\{c/8,1/128\\}$. ∎

####  6.3.2 PAC learning hardness

In this section, we discuss corollaries of Theorem 12. For a brief background
on PAC learning and the definitions that we use, see Appendix C.

######  Corollary 6.18 (Hardness of learning decision trees, DNFs, and CNFs).

Assuming randomized ETH, there is a constant $\lambda\in(0,1)$ such that
decision trees cannot be distribution-free, properly PAC learned to accuracy
$\varepsilon=1/n$ in time $s^{\lambda\frac{\log\log s}{\log\log\log s}}$ where
$s$ is the size of the target. The same result also holds for properly
learning DNFs and CNFs with size-$s$ targets.

###### Proof.

Let $\mathcal{L}$ be a distribution-free, proper learning algorithm for the
class $\mathcal{T}$ of decision trees. We claim $\mathcal{L}$ can be used to
solve DT-Construction. In particular, let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and
$\mathcal{D}$ be an instance of DT-Construction$(s,1/n)$. We run the learning
algorithm on $f$ and $\mathcal{D}$ and $\varepsilon=1/n$. If $\mathcal{L}$
requests a random sample, we generate $x\sim\mathcal{D}$ using the generator
for $\mathcal{D}$ and evaluate $f(x)$ using the circuit for $f$ and return
$(x,f(x))$ to $\mathcal{L}$. Since generating a sample from $\mathcal{D}$ and
evaluating the circuit for $f$ are both $\mathrm{poly}(n)$-time operations the
overall runtime is dominated by the runtime of $\mathcal{L}$. Theorem 12 then
implies the desired time bound by setting $\mu(n)=1$.

If $\mathcal{L}$ is a learning algorithm for DNFs, we obtain the same hardness
as in the decision tree case since any size-$s$ decision tree target is
equivalently a size-$s$ DNF target. Moreover, Theorem 12 also applies when the
output of the DT-Construction algorithm is a DNF formula. A symmetric argument
works similarly for CNFs. ∎

####  6.3.3 Proof of Theorem 3

In this section, we observe that the number of relevant inputs to
$\Gamma_{\mathcal{S}}$ exactly characterizes the set cover complexity of
$\mathcal{S}$. As a result, hardness of approximating set cover can be
directly translated into hardness of distribution-free, proper PAC learning
$k$-juntas. The next theorem formalizes this observation and was already
implicit in [ABF+09].

######  Theorem 13 (Learning $k$-juntas is as hard as Set-Cover).

Suppose there is a distribution-free PAC learning algorithm that runs in time
$t(n,k)$ and learns the class of $k$-juntas over $\\{0,1\\}^{n}$ to accuracy
$\varepsilon=O(1/n)$ by hypotheses which are $g(k,n)$-juntas for some function
$g:\mathds{N}^{2}\to\mathds{N}$ satisfying $k\leq g(k,n)$. Then
$(k,g(k,n))$-Set-Cover can be solved with high probability in time $t(n,k)$.

###### Proof.

Let $\mathcal{S}=(S,U,E)$ be an instance of $(k,g(k,n))$-Set-Cover. We
construct the function $\Gamma:\\{0,1\\}^{|S|}\to\\{0,1\\}$ and the
distribution $\mathcal{D}$ over $\\{0,1\\}^{|S|}$. Run the learning algorithm
on $\Gamma$ and $\mathcal{D}$ with $\varepsilon=1/(4|S|)$ for $t(k,|S|)$ time
steps. It outputs some truth table representation of a junta. We output Yes if
and only if this truth table has size at most $g(k,n)$ and has error at most
$1/(4|S|)$. The correctness of the reduction follows from 6.1. ∎

######  Corollary 6.19.

There is no distribution-free PAC learning algorithm for properly learning
$k$-juntas to accuracy $\varepsilon=O(1/n)$ over $\\{0,1\\}^{n}$ that runs in
time:

  * $\circ$

$n^{o(k)}$, assuming randomized $W[1]\neq\textnormal{FPT}$;

  * $\circ$

$O(n^{k-\lambda})$, for all $\lambda>0$, assuming randomized SETH.

These results hold in the regime where $k\leq n^{c}$ for some absolute
constant $c<1$.

###### Proof.

By Theorem 13, distribution-free properly PAC learning $k$-juntas is
equivalent to $(k,k+1)$-Set-Cover. The first bullet follows by combining
Theorems 13 and 10. The second bullet follows by combining Theorems 13 and 11.
∎

##  7 Lower bounds for DT-Estimation

For our lower bounds for DT-Estimation, we have to consider decision trees
that are allowed to abort:

######  Definition 5.

A $\delta$-abort decision tree $T$ under a distribution $\mathcal{D}$ is a
decision tree with leaves labeled $\\{0,1,\bot\\}$ satisfying
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[T(\bm{x})=\bot]\leq\delta$.
The distance between such a tree $T:\\{0,1\\}^{n}\to\\{0,1,\bot\\}$ and a
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ under $\mathcal{D}$ is

$\mathrm{dist}_{\mathcal{D}}(T,f)\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[T(\bm{x})\neq
f(\bm{x})\text{ and $T(\bm{x})\neq\bot$}].$

###  7.1 Lemma 6.6 for decision trees that abort

In this section we generalize Lemma 6.6 to $\delta$-abort decision trees:

######  Lemma 7.1 (Lemma 6.6 with aborts).

Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex set cover instance and let
$\ell\in\mathds{N}$. If $T:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ is a decision
tree of size $|T|<2^{\mathrm{opt}(\mathcal{S}){\ell}/40}$ that can abort with
probability $\delta<0.4$, then
$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(T,\Gamma_{\oplus\ell})\geq 1/(20N)$.

Since every depth-$d$ tree is a tree of size $2^{d}$, Lemma 7.1 also holds for
decision trees $T$ of depth $<\mathrm{opt}(\mathcal{S})\ell/40$.

##### Outline of Proof.

As in the non-abort case, there are three main components to the proof of the
above lemma:

  1. 1.

No $\delta$-abort decision tree with small average depth can approximate
$\Gamma$ under $\mathcal{D}$ where $\delta<1/2$ (7.2).

  2. 2.

Any $\delta$-abort decision tree with small average depth that approximates
$\Gamma_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$ can be used to
construct a $\delta$-abort decision tree of much smaller average depth that
approximates $\Gamma$ under $\mathcal{D}$ at the cost of a modest blowup in
the size of $\delta$ (7.3). This is the key claim.

  3. 3.

Any small size decision tree must have small average depth with respect to
$\mathcal{D}_{\oplus\ell}$. This claim is unchanged from the non-abort
version.

Analogous to the non-abort case, these claims together imply that no
$\delta$-abort decision tree with small average depth can approximate
$\Gamma_{\oplus\ell}$ under $\mathcal{D}_{\oplus\ell}$. We need to provide
slightly different claims and proofs for the first two items, but the last
claim is completely independent of aborts, so we need not reprove it.

######  Claim 7.2 (Abort version of 6.7).

Let $T:\\{0,1\\}^{n}\to\\{0,1\\}$ be a $\delta$-abort decision tree with
$\delta<1/2$ and $\mathcal{S}=(S,U,E)$ be an $N$-vertex set cover instance
with $|S|=n$. If
$\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{x})]<\mathrm{opt}(\mathcal{S})/2$
then $\mathrm{dist}_{\mathcal{D}}(T,\Gamma)\geq 1/(2N)$.

###### Proof.

This proof is almost identical to that of 6.7. We provide the start of the
proof and then refer the reader back to 6.7 for the rest.

Suppose that $\mathrm{dist}_{\mathcal{D}}(T,\Gamma)<1/(2N)\leq 1/(2|U|)$. We
note as before that each $x\in\text{supp}(\mathcal{D})$ has mass $\geq
1/(2|U|)$ under $\mathcal{D}$, so it must be that
$\mathrm{dist}_{\mathcal{D}}(T,\Gamma)=0$. Since $0^{n}$ has weight $1/2$
under $\mathcal{D}$, $T(0^{n})\neq\perp$ because $T$ can only abort with
probability $<1/2$. It follows that $T(0^{n})=\Gamma(0^{n})=0$.

The rest of the proof is identical to that of 6.7∎

For the next claim, we reuse the portions of 6.8 that tell us that the
restriction $T^{*}$ of $T$ is distance preserving and has small depth. We must
show that $T^{*}$ also has a small abort probability.

######  Claim 7.3 (Abort version of 6.8).

Let $T:(\\{0,1\\}^{\ell})^{n}\to\\{0,1\\}$ be a decision tree such that

$\mathrm{dist}_{\mathcal{D}_{\oplus\ell}}(T,\Gamma_{\oplus\ell})\leq\varepsilon\quad\text{and}\quad\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}[0pt_{T}(\bm{y})]\leq
d\quad\text{and}\quad\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}\sim\mathcal{D}_{\oplus\ell}}[T(\bm{y})=\bot]\leq\delta.$

Then there is a restriction $T^{*}:\\{0,1\\}^{n}\to\\{0,1\\}$ of $T$
satisfying

$\mathrm{dist}_{\mathcal{D}}(T^{*},\Gamma)\leq
10\varepsilon\quad\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T^{*}}(\bm{x})]\leq\frac{10d}{\ell}\quad\text{and}\quad\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}[T^{*}(\bm{x})=\bot]\leq\frac{5}{4}\delta.$

###### Proof.

Recall the definition of $q_{j}(y)$ in the proof of 6.8. For $j\in[\ell]$,
$q_{j}(y)$ is the number of times that $T$, on input $y$, queries
$(y_{i})_{j}$ for some $i\in[n]$. Refer to Definition 4 for the definitions of
$\mathcal{D}^{j}_{\oplus\ell}$ and $\textnormal{ParComplete}_{j}(z,x)$. The
proof of 6.8 bounds the probabilities that
$\mathrm{dist}_{\mathcal{D}}(T^{*},\Gamma)$ or
$\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T^{*}}(\bm{x})]$
are too large using Markov’s inequality. More concretely, we already know that
for a particular $\underline{j}\in[\ell]$,

$\displaystyle\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\Gamma(\bm{x})\text{
and
}T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\neq\perp\right]>10\varepsilon\right]<\frac{1}{10}$
$\displaystyle\text{and}\quad\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))\right]>\frac{10d}{\ell}\right]<\frac{1}{10}$

where all we have done is change the constant used in the application of
Markov’s inequality.

It remains for us to bound the probability that the tree aborts. We compute

$\displaystyle\delta$
$\displaystyle\geq\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{Pr}}}[T(\bm{y})=\perp]$
$\displaystyle=\underset{\bm{y}\sim\mathcal{D}^{\underline{j}}_{\oplus\ell}}{\operatorname{{Pr}}}[T(\bm{y})=\perp]$
(Proposition 6.4)
$\displaystyle=\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{\mathds{E}}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))=\perp\right]\right].$
(Definition of $\mathcal{D}_{\oplus\ell}^{j}$)

Again, we can apply Markov’s inequality to deduce

$\displaystyle\underset{\bm{z}\sim\mathcal{U}_{n(\ell-1)}}{\operatorname{{Pr}}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))=\perp\right]>\frac{10}{8}\delta\right]<\frac{8}{10}.$

Thus, applying a union bound to all three of our Markov inequalities, we
conclude that there exists a fixed $\underline{z}\in\\{0,1\\}^{n(\ell-1)}$
such that

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\neq\Gamma(\bm{x})\text{
and
}T(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\neq\perp\right]\leq
10\varepsilon$
$\displaystyle\text{and}\quad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}\left[q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))\right]\leq\frac{10d}{\ell}$
$\displaystyle\text{and}\quad\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\underline{z},\bm{x}))=\perp\right]\leq\frac{10}{8}\delta$

The tree $T^{*}$ is formed by restricting $T$ according to $\underline{z}$ and
$\underline{j}$. As before, the depth of an input $x$ is
$\text{depth}_{T^{*}}(x)=q_{\underline{j}}(\textnormal{ParComplete}_{\underline{j}}(\underline{z},x))$.
Thus, the claim follows. ∎

Finally, we can directly apply 6.10 without needing a special version for
aborts. These three claims together allow us to complete the proof.

##### Putting things together: Proof of Lemma 7.1.

Suppose there is some $\delta$-abort tree $T$ computing $\Gamma_{\oplus\ell}$
with $|T|\leq 2^{\mathrm{opt}(\mathcal{S})\ell/40}$ and with $\delta<0.4$. We
show that $\mathrm{dist}(T,\Gamma_{\oplus\ell})\geq 1/(20N)$. Suppose for
contradiction that $\mathrm{dist}(T,\Gamma_{\oplus\ell})<1/(20N)$. By 6.10, we
have
$\underset{\bm{y}\sim\mathcal{D}_{\oplus\ell}}{\operatorname{{\mathds{E}}}}\left[{0pt_{T}(\bm{y})}\right]<2\cdot\log\left(2^{\mathrm{opt}(\mathcal{S})\ell/40}\right)=\mathrm{opt}(\mathcal{S})\ell/20$.
Then by 7.3 there is a decision tree $T^{*}$ satisfying

$\displaystyle\mathrm{dist}_{\mathcal{D}}(T^{*},\Gamma)<\frac{1}{2N}\qquad\underset{\bm{x}\sim\mathcal{D}}{\operatorname{{\mathds{E}}}}[0pt_{T^{*}}(\bm{x})]<\frac{\mathrm{opt}(\mathcal{S})}{2}\qquad\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathcal{D}}\left[T(\textnormal{ParComplete}_{\underline{j}}(\bm{z},\bm{x}))=\perp\right]\leq\frac{5\delta}{4}<\frac{1}{2}.$

But this contradicts 7.2. $\square$

###  7.2 Hardness amplification for DT-Estimation

Next, we amplify the distance given by Lemma 7.1 using the following harndess
amplification lemma:

######  Lemma 7.4 (Precise restatement of Lemma 3.3).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $\mathcal{D}$ be such that $f$ is
$\varepsilon$-far from every depth-$d$ $\delta$-abort decision tree where
$\delta\geq 0.34$ under $\mathcal{D}$. Consider

$f^{\oplus m}(x^{(1)},\ldots,x^{(m)})\coloneqq f(x^{(1)})\oplus\cdots\oplus
f(x^{(m)}),$

the $m$-fold XOR composition of $f$ and $\mathcal{D}^{m}$ be the corresponding
distribution over $(\\{0,1\\}^{n})^{m}$. For any $\gamma>0$, by taking
$m=\Theta(\log(1/\gamma)/\varepsilon)$, we get that $f^{\oplus m}$ is
$(\frac{1}{2}-\gamma)$-far from every decision tree of depth $\Omega(dm)$
under $\mathcal{D}^{m}$.

Note that the probability of error $\varepsilon$ is taken over inputs that _do
not_ abort. Thus, this statement is weaker than that of Lemma 3.3. We need to
allow the possibility of aborting in order to apply [BKLS20]’s lemma. The
proof of Lemma 7.4 consists of two parts, each of which introduces another
layer of XOR composition in order to amplify the error. First, we amplify the
error from $\varepsilon$ to a constant $O(1)$ and then from $O(1)$ to
exponentially close to $\frac{1}{2}$. Each of these two steps uses an XOR
lemma from [BKLS20] and [Dru12] respectively. We now state these lemmas and
then proceed with the proof of Lemma 7.4.

######  Lemma 7.5 (Lemma 1 of [BKLS20]).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $\mathcal{D}$ be such that $f$ is
$\varepsilon$-far from every depth-$d$ $\delta$-abort tree where $\delta\geq
0.34$ under $\mathcal{D}$. By taking $m=\Theta(1/\varepsilon)$, we get that
$f^{\oplus m}$ is $\frac{1}{800}$-far from every decision tree of depth
$\Omega(dm)$ under $\mathcal{D}^{m}$.

######  Lemma 7.6 (Theorem 1.3 of [Dru12]).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and $\mathcal{D}$ be such that $f$ is
$\varepsilon$-far from every depth-$d$ decision tree under $\mathcal{D}$. For
every $m\in\mathds{N}$ and $\alpha\in[0,1]$, we get that $f^{\oplus m}$ is

$\frac{1}{2}\big{(}1-(1-2\varepsilon+6\alpha\ln(2/\alpha)\varepsilon)^{m}\big{)}$

far from every decision tree of depth $\alpha\varepsilon dm$ under
$\mathcal{D}^{m}$.

Note that the original version of Lemma 7.6 in [Dru12] holds for randomized
decision trees rather than deterministic ones; however, the above version is
equivalent. If $f$ is $\varepsilon$-far from all depth-$d$ randomized decision
trees, then clearly it is $\varepsilon$-far from all deterministic ones since
randomness can only add power. On the other hand, suppose $f$ is
$\varepsilon$-far from all depth-$d$ deterministic decision trees. Consider a
depth-$d$ randomized decision tree $T(x,r)$ that in addition to $x$ takes in a
random string $r$. The distance between $T$ and $f$ is given by

$\underset{\bm{r}}{\operatorname{{\mathds{E}}}}[\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}}[T(\bm{x},\bm{r})\neq
f(\bm{x})]].$

For each fixed $r$, we have that $\operatorname{{Pr}}[T(\bm{x},r)\neq
f(\bm{x})]$ must be at least an $\varepsilon$ fraction of total inputs. Thus,
by linearity of expectation, the randomized decision tree must also be
$\varepsilon$-far from $f$.

###### Proof of Lemma 7.4.

Consider $f$ and $\mathcal{D}$ as in the statement of Lemma 7.4, and simply
apply Lemma 7.5 with $m_{1}=\Theta(1/\varepsilon)$. What results is a function
$f^{\oplus m_{1}}$ that is $\frac{1}{800}$-far from every decision tree of
depth $\Omega(dm_{1})$ under $\mathcal{D}^{m_{1}}$. Next, apply Lemma 7.6 to
$f^{\oplus m_{1}}$ with $m_{2}=\Theta(\log(1/\gamma))$,
$\varepsilon=\frac{1}{800}$, and by choosing $\alpha$ such that
$6\alpha\ln(2/\alpha)=1$. Then, simplifying the expression in Lemma 7.6, we
get that $(f^{\oplus m_{1}})^{\oplus m_{2}}$ is

$\displaystyle\frac{1}{2}\big{(}1-\left(1-\textstyle\frac{1}{800}\right)^{m_{2}}\big{)}$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\left(\frac{799}{800}\right)^{\Theta(\log(1/\gamma))}$
$\displaystyle\geq\frac{1}{2}-2^{-\log(1/\gamma)}$
$\displaystyle=\frac{1}{2}-\gamma$

far from every decision tree of depth $\Omega(dm_{1}m_{2})$ under
$(\mathcal{D}^{m_{1}})^{m_{2}}$.

Globally, we define $m=m_{1}\cdot m_{2}=\Theta(\log(1/\gamma)/\varepsilon)$ so
that $(f^{\oplus m_{1}})^{\oplus m_{2}}=f^{\oplus m}$. Then, $f^{\oplus m}$ is
$\frac{1}{2}-\gamma$ far from decision trees of depth
$\Omega(dm)=\Omega(d\log(1/\gamma)/\varepsilon)$ under $\mathcal{D}^{m}$ as
desired. ∎

default preamble= for tree= circle, minimum size=0.7cm, inner sep=0.1pt, draw,
align=center, anchor=north, fill=white, l sep=1cm, s sep=0.2cm,
[,name=topgate, s sep=0.4cm,circle split, [$\lor$,name=lormain1,s sep=0.2cm,
calign=center, [,name=oplus11, s sep=0.4cm, inner sep=-0.0cm,circle split,
[$y_{111}$,name=y111,tier=inputl,draw=white]
[$y_{121}$,name=y1l1,tier=inputl,draw=white] ]
[,name=ldots11,draw=white,before computing xy=s=-30]
[$\ldots$,name=ldots21,draw=white,before computing xy=s=0]
[,name=ldots31,draw=white,before computing xy=s=30] [,name=oplus21,s
sep=0.4cm,inner sep=-0.0cm,circle split,
[$y_{n11}$,name=yn11,tier=inputl,draw=white]
[$y_{n21}$,name=ynl1,tier=inputl,draw=white] ] ]
[,name=ldotsmiddleleft,draw=white,before computing xy=s=-45]
[$\ldots$,name=ldotsmiddle,draw=white,before computing xy=s=0]
[,name=ldotsmiddleright,draw=white,before computing xy=s=45]
[$\lor$,name=lormain2,s sep=0.2cm, calign=center, [,name=oplus12, s sep=0.4cm,
inner sep=-0.0cm,circle split, [$y_{11m}$,name=y112,tier=inputl,draw=white]
[$y_{12m}$,name=y1l2,tier=inputl,draw=white] ]
[,name=ldots12,draw=white,before computing xy=s=-30]
[$\ldots$,name=ldots22,draw=white,before computing xy=s=0]
[,name=ldots32,draw=white,before computing xy=s=30] [,name=oplus22,s
sep=0.4cm,inner sep=-0.0cm,circle split,
[$y_{n1m}$,name=yn12,tier=inputl,draw=white]
[$y_{n2m}$,name=ynl2,tier=inputl,draw=white] ] ] ] [black] (-1.75,-0.75) ..
controls +(south east:1cm) and +(south west:1cm) .. (1.75,-0.75); [black]
(-4.25,-2.75) .. controls +(south east:0.5cm) and +(south west:0.5cm) ..
(-2,-2.75); [xshift=-0.65cm,yshift=0.25cm] at (-2,-0.75) fan-in $m$;
[xshift=-0.75cm,yshift=0cm] at (-4.25,-2.5) fan-in $n$; [draw,black,circle
split,rotate=90,inner sep=-0.0cm,minimum size=0.7cm] at (topgate) ;
[draw,black,circle split,rotate=90,inner sep=-0.0cm,minimum size=0.7cm] at
(oplus21) ; [draw,black,circle split,rotate=90,inner sep=-0.0cm,minimum
size=0.7cm] at (oplus11) ; [draw,black,circle,inner sep=-0.0cm,minimum
size=0.7cm] at (lormain1) ; [draw,black,circle split,rotate=90,inner
sep=-0.0cm,minimum size=0.7cm] at (oplus22) ; [draw,black,circle
split,rotate=90,inner sep=-0.0cm,minimum size=0.7cm] at (oplus12) ;
[draw,black,circle,inner sep=-0.0cm,minimum size=0.7cm] at (lormain2) ;

Figure 5: A depth-$3$ circuit for $(\Gamma_{\oplus 2})^{\oplus m}$ consisting
of one top gate that is a PARITY connected to $m$ independent copies of the
circuit for $\Gamma_{\oplus 2}$.

###  7.3 Proof of Theorem 4

With Lemmas 7.1 and 7.4 in hand, we are now ready to prove Theorem 4. Given a
size-$N$ instance $\mathcal{S}$ of $(k,k^{\prime})$-Set-Cover with $n$ sets,
we apply Lemmas 3.1 and 7.1 with $\ell=2$ to obtain a $\mathrm{poly}(N)$-time
reduction that produces a function $\Gamma_{\oplus
2}:\\{0,1\\}^{2n}\to\\{0,1\\}$ and the generator for a distribution
$\mathcal{D}_{\oplus 2}$ over $\\{0,1\\}^{2n}$ satisfying:

  1. $\circ$

If $\mathrm{opt}(\mathcal{S})\leq k$, then $\Gamma_{\oplus 2}$ is a $2k$-junta
under $\mathcal{D}_{\oplus 2}$.

  2. $\circ$

If $\mathrm{opt}(\mathcal{S})>k^{\prime}$, then for any $\delta<0.4$, any
$\delta$-abort decision tree of depth $k^{\prime}/20$ is
$\Omega(\frac{1}{N})$-far from $\Gamma_{\oplus 2}$ under $\mathcal{D}_{\oplus
2}$.

Next, we consider $(\Gamma_{\oplus 2})^{\oplus m}$ and $(\mathcal{D}_{\oplus
2})^{m}$ where $m=\Theta(N^{2})$:

  * $\circ$

If $\mathrm{opt}(\mathcal{S})\leq k$, then $(\Gamma_{\oplus 2})^{\oplus m}$ is
a $2km$-junta under $(\mathcal{D}_{\oplus 2})^{m}$. Such a junta can be
computed by a decision tree of depth $d\coloneqq 2km$.

  * $\circ$

If $\mathrm{opt}(\mathcal{S})>k^{\prime}$, then by Lemma 7.4, $(\Gamma_{\oplus
2})^{\oplus m}$ is $(\frac{1}{2}-2^{-N})$-far from decision trees of depth
$d^{\prime}\coloneqq\Omega(k^{\prime}m)$ under $(\mathcal{D}_{\oplus 2})^{m}$.

Note that the circuit representation for $(\Gamma_{\oplus 2})^{\oplus m}$ and
generator for $(\mathcal{D}_{\oplus 2})^{m}$ can be constructed in
$\mathrm{poly}(N)$ time from those for $\Gamma_{\oplus 2}$ and
$\mathcal{D}_{\oplus 2}$ by simply feeding $m$ copies of $f$ into an XOR gate
and by using $m$ copies of $\mathcal{D}$. See Figure 5 for an illustration of
this circuit. Since $(\Gamma_{\oplus 2})^{\oplus m}$ is a function over
$2nm\leq O(N^{3})$ variables and $d^{\prime}\geq\Omega(d\log
N)\geq\Omega(d\log d)$, Theorem 4 now follows by applying Theorem 9 with
$\beta\in(0,1)$ being any constant.

##  8 Proof of Theorem 5

The PAC learning lower bound from Section 6.3.2 applies to properly learning
decision trees. In this setting, the concept class is
$\mathcal{T}=\\{T:\\{0,1\\}^{n}\to\\{0,1\\}\mid T\text{ is a decision
tree}\\}$. So the learner is allowed to output a decision tree hypothesis that
may be much larger than the target. One could instead consider the problem of
properly learning the class of size-$s$ decision trees:
$\mathcal{T}_{s}=\\{T:\\{0,1\\}^{n}\to\\{0,1\\}\mid T\text{ is a size-}s\text{
decision tree}\\}$. This problem is strictly harder than learning decision
trees since the output must satisfy a size constraint. Indeed, against this
class, we are able to adapt the proof of Theorem 12 to obtain a stronger lower
bound.

######  Theorem 14.

Assuming randomized ETH, there is a constant $\lambda\in(0,1)$ such that DT-
Construction$(s,\frac{1}{n})$ cannot be solved in time $n^{\lambda\log s}$ if
the algorithm has to return a size-$s$ DNF hypothesis, even when the function
is promised to be a $\log s$-junta.

###### Proof.

This proof is a combination of the proofs of Theorems 15 and 12. The analysis
is similar so we only outline the important details here. In particular, let
$\mathcal{S}=(S,U,E)$ be an $N$-vertex $\left(k,\frac{1}{2}\left(\frac{\log
N}{\log\log N}\right)^{1/k}\right)$-Set-Cover instance where $k$ is taken to
be $k=\frac{1}{2}\cdot\frac{\log\log N}{\log\log\log N}$ for $N$ large enough
so that $32k<\frac{1}{2}\left(\frac{\log N}{\log\log N}\right)^{1/k}$. Using
Theorem 7, there is a constant $c\in(0,1)$ such that $\mathcal{S}$ cannot be
solved in time $N^{ck}$. We derive a contradiction for any algorithm for DT-
Construction$(s,\frac{1}{n})$ that returns a size-$s$ DNF and runs in time
$n^{\lambda\log s}$ for $\lambda\leq c/5$.

Use Lemma 6.13 with $\ell=4$ (as in Theorem 15) to obtain the target function
$\overline{\Gamma}_{\oplus 4}:\\{0,1\\}^{4N}\to\\{0,1\\}$ and the distribution
$\mathcal{D}_{\oplus 4}$. Run DT-Construction$(s,\frac{1}{4N})$ with
$s\coloneqq 2^{4k}$ on $\overline{\Gamma}_{\oplus 4}:\\{0,1\\}^{4N}$ and
$\mathcal{D}_{\oplus 4}$ for $N^{5\lambda k}$ time steps where $\lambda\leq
c/5$. Output yes if and only if the DNF formula returned by the algorithm as
size at most $2^{4k}$ and error less than $1/(4N)$. The correctness of the no
case follows from the fact that $32k<\frac{1}{2}\left(\frac{\log N}{\log\log
N}\right)^{1/k}$ and so the DNF lower bound from Lemma 6.13 ensures
$2^{\mathrm{opt}(\mathcal{S})\ell/16}>2^{4k}$. Since the algorithm returns a
size-$2^{4k}$ DNF formula if one exists, this separation between the DNF sizes
is sufficient to establish correctness. ∎

As in the case of Corollary 6.18, this theorem yields hardness of properly PAC
learning the class of size-s decision trees.

######  Corollary 8.1.

Assuming randomized ETH, there is a constant $\lambda\in(0,1)$ such that the
class $\mathcal{T}_{s}$ of size-s decision trees cannot be distribution-free,
properly PAC learned to accuracy $\varepsilon=1/n$ in time $n^{\lambda\log
s}$. The same result also holds for properly learning size-$s$ DNFs and CNFs.

##  9 Proof of Theorem 6

In this section, we outline a concrete path towards proving optimal lower
bounds for DT-Construction. In particular, we show that better lower bounds
for gapped set cover yields better lower bounds for DT-Construction.
Specifically, the main theorem assumes 1 and proves an $n^{\Omega(\log s)}$
lower bound for DT-Construction$(s,\frac{1}{n})$.

######  Theorem 15.

Assume 1, then there is a constant $\lambda\in(0,1)$ such that DT-
Construction$(s,\frac{1}{n})$ cannot be solved in time $n^{\lambda\log s}$,
even when the target is a $\log s$-junta and the algorithm is allowed to
return a DNF hypothesis.

###### Proof.

Let $\beta\in(0,1)$ be as in the statement of the 1. Assume there is an
algorithm for DT-Construction$(s,\frac{1}{n})$ running in time
$n^{\lambda\cdot\log s}$ for any $\lambda\leq(1-\beta)/(40\log e)$. Then,
following the proof strategy of Theorem 12, we derive a contradiction by
solving $(k,k\cdot(1-\beta)\ln N)$-Set-Cover over $N$ vertices in time
$N^{5\lambda k}$. Let $\mathcal{S}=(S,U,E)$ be an $N$-vertex
$(k,k\cdot(1-\beta)\ln N)$-Set-Cover instance for $k\in\mathds{N}$. Using
Lemma 6.17 with $\ell=4$, we obtain the target function
$\overline{\Gamma}_{\oplus 4}:\\{0,1\\}^{4N}\to\\{0,1\\}$ and the distribution
$\mathcal{D}_{\oplus 4}$. We run the algorithm for DT-
Construction$(s,\frac{1}{4N})$ on $\overline{\Gamma}_{\oplus 4}$ and
$\mathcal{D}_{\oplus 4}$ with $s\coloneqq 2^{4k}$ and terminate it after
$N^{5\lambda k}$ time steps. The output is some DNF formula $F$. We estimate
the error of $F$ over $\mathcal{D}_{\oplus 4}$ and output Yes if it’s less
than $1/(4N)$ and No otherwise.

##### Runtime.

By Lemma 6.17, we can construct the circuit for $\overline{\Gamma}_{\oplus
4}:\\{0,1\\}^{4N}\to\\{0,1\\}$ and generator for $\mathcal{D}_{\oplus 4}$ in
$\mathrm{poly}(N)$-time. Moreover, we can use random sampling to efficiently
estimate the error of $F$ over $\mathcal{D}_{\oplus 4}$. Therefore, the
runtime of the reduction is dominated by $N^{5\lambda k}$.

##### Correctness.

We handle the yes case and the no case separately.

###### Yes case: $\mathrm{opt}(\mathcal{S})\leq k$.

By Lemma 6.17, $\overline{\Gamma}_{\oplus 4}$ is a $4k$-junta over
$\mathcal{D}_{\oplus 4}$. Therefore, it is a decision tree of size $s=2^{4k}$
and DT-Construction$(s,\frac{1}{4N})$ runs in time

$(4N)^{\lambda\cdot\log s}=(2N)^{4\lambda k}\leq N^{5\lambda k}.$

The output is DNF formula with error at most $1/(4N)$. It follows that our
algorithm outputs Yes with high probability.

###### No case: $\mathrm{opt}(\mathcal{S})>k\cdot(1-\beta)\ln N$.

By Lemma 6.17, any DNF for $\overline{\Gamma}_{\oplus 4}$ with size at most
$2^{\mathrm{opt}(\mathcal{S})/8}$ has error at least $1/(4N)$. Using the
assumption on $\mathrm{opt}(\mathcal{S})$:

$\displaystyle 2^{\mathrm{opt}(\mathcal{S})/8}$
$\displaystyle>N^{k(1-\beta)/(8\log e)}$ $\displaystyle\geq N^{5\lambda k}$
($(1-\beta)/(40\log e)\geq\lambda$)

which shows that the DNF output by the algorithm must have error at least
$1/(4N)$. It follows that our algorithm outputs No with high probability. ∎

As discussed in Section 6.3.2, this lower bound for DT-Construction implies a
lower bound for PAC learning decision trees.

######  Corollary 9.1.

Assume 1, then there is a constant $\lambda\in(0,1)$ such that decision trees
cannot be distribution-free, properly PAC learned to accuracy
$\varepsilon=1/n$ in time $n^{\lambda\log s}$ where $s$ is the size of the
decision tree target. The same result also holds for properly learning DNFs
and CNFs.

The proof of this corollary is identical to that of Corollary 6.18.

## Acknowledgments

We thank the SODA reviewers for their useful comments and feedback.

Caleb, Carmen, and Li-Yang are supported by NSF awards 1942123, 2211237, and
2224246. Caleb is also supported by an NDSEG fellowship.

## References

  * [ABF+09] Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toniann Pitassi.  The complexity of properly learning simple concept classes.  Journal of Computer & System Sciences, 74(1):16–34, 2009.  Preliminary version in FOCS 2004.
  * [ABF+22] Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida.  Low degree testing over the reals.  arXiv preprint arXiv:2204.08404, 2022.
  * [AH12] Micah Adler and Brent Heeringa.  Approximating optimal binary decision trees.  Algorithmica, 62(3-4):1112–1121, 2012.
  * [BB19] Eric Blais and Joshua Brody.  Optimal Separation and Strong Direct Sum for Randomized Query Complexity.  In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [BBM12] Eric Blais, Joshua Brody, and Kevin Matulef.  Property testing lower bounds via communication complexity.  computational complexity, 21(2):311–358, 2012.
  * [Bel19] Aleksandrs Belovs.  Quantum algorithm for distribution-free junta testing.  In International Computer Science Symposium in Russia, pages 50–59. Springer, 2019.
  * [BFJ+94] Avirm Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich.  Weakly learning DNF and characterizing statistical query learning using Fourier analysis.  In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 253–262, 1994.
  * [BFPJH21] Eric Blais, Renato Ferreira Pinto Jr, and Nathaniel Harms.  VC dimension and distribution-free sample-based testing.  In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 504–517, 2021.
  * [BHZ22] Nader H Bshouty and Catherine A Haddad-Zaknoon.  On testing decision tree.  In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [Bis06] Christopher M. Bishop.  Pattern Recognition and Machine Learning (Information Science and Statistics).  Springer-Verlag, Berlin, Heidelberg, 2006.
  * [BKB17] Osbert Bastani, Carolyn Kim, and Hamsa Bastani.  Interpretability via model extraction.  In Proceedings of the 4th Workshop on Fairness, Accountability, and Transparency in Machine Learning (FAT/ML), 2017.
  * [BKLS20] Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu.  A strong XOR lemma for randomized query complexity.  arXiv preprint arXiv:2007.05580, 2020.
  * [BLQT21] Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan.  Properly learning decision trees in almost polynomial time.  In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021.
  * [BLT20] Guy Blanc, Jane Lange, and Li-Yang Tan.  Top-down induction of decision trees: rigorous guarantees and inherent limitations.  In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 1–44, 2020.
  * [BLT22] Guy Blanc, Jane Lange, and Li-Yang Tan.  Reconstructing Decision Trees.  In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), 2022.
  * [Blu92] Avrim Blum.  Rank-$r$ decision trees are a subclass of $r$-decision lists.  Inform. Process. Lett., 42(4):183–185, 1992.
  * [BM02] Nader H Bshouty and Yishay Mansour.  Simple learning algorithms for decision trees and multivariate polynomials.  SIAM Journal on Computing, 31(6):1909–1925, 2002.
  * [BS96] Leo Breiman and Nong Shang.  Born again trees.  Technical report, University of California, Berkeley, 1996.
  * [Bsh93] Nader Bshouty.  Exact learning via the monotone theory.  In Proceedings of 34th Annual Symposium on Foundations of Computer Science (FOCS), pages 302–311, 1993.
  * [Bsh19] Nader H Bshouty.  Almost optimal distribution-free junta testing.  In Proceedings of the 34th Computational Complexity Conference, pages 1–13, 2019.
  * [Bsh22] Nader H Bshouty.  An optimal tester for $k$-linear.  In International Conference and Workshops on Algorithms and Computation, pages 201–212. Springer, 2022.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [CHK20] Marek Cygan, Magnús M Halldórsson, and Guy Kortsarz.  Tight bounds on subexponential time approximation of set cover and related problems.  In International Workshop on Approximation and Online Algorithms, pages 159–173. Springer, 2020.
  * [CHKX06] Jianer Chen, Xiuzhen Huang, Iyad A Kanj, and Ge Xia.  Strong computational lower bounds via parameterized complexity.  Journal of Computer and System Sciences, 72(8):1346–1367, 2006\.
  * [CIKP08] Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi.  The complexity of unique k-SAT: An isolation lemma for k-CNFs.  Journal of Computer and System Sciences, 74(3):386–393, 2008.  Computational Complexity 2003.
  * [CL19] Yijia Chen and Bingkai Lin.  The constant inapproximability of the parameterized dominating set problem.  SIAM J. Comput., 48(2):513–533, 2019.
  * [CM19] Sitan Chen and Ankur Moitra.  Beyond the low-degree algorithm: mixtures of subcubes and their applications.  In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 869–880, 2019.
  * [CP22] Xi Chen and Shyamal Patel.  Distribution-free testing for halfspaces (almost) requires PAC learning.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1715–1743. SIAM, 2022.
  * [CPR+07] Venkatesan T Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania.  Decision trees for entity identification: Approximation algorithms and hardness results.  In Proceedings of the 26th ACM Symposium on Principles of Database Systems (PODS), pages 53–62, 2007.
  * [CS95] Mark Craven and Jude Shavlik.  Extracting tree-structured representations of trained networks.  Proceedings of the 8th Conference on Advances in Neural Information Processing Systems (NeurIPS), 8:24–30, 1995.
  * [CX16] Xi Chen and Jinyu Xie.  Tight bounds for the distribution-free testing of monotone conjunctions.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 54–71. SIAM, 2016.
  * [DF13] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Springer Publishing Company, Incorporated, 2013.
  * [DHM+14] Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén.  Exponential time complexity of the permanent and the tutte polynomial.  ACM Trans. Algorithms, 10(4), aug 2014.
  * [Dru12] Andrew Drucker.  Improved direct product theorems for randomized query complexity.  computational complexity, 21(2):197–244, 2012.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 624–633, New York, NY, USA, 2014. Association for Computing Machinery.
  * [EH89] Andrzej Ehrenfeucht and David Haussler.  Learning decision trees from random examples.  Information and Computation, 82(3):231–246, 1989.
  * [Fei98] Uriel Feige.  A threshold of $\ln n$ for approximating set cover.  J. ACM, 45(4):634–652, 1998.
  * [FH17] Nicholas Frosst and Geoffrey Hinton.  Distilling a neural network into a soft decision tree.  arXiv preprint arXiv:1711.09784, 2017.
  * [FY20] Noah Fleming and Yuichi Yoshida.  Distribution-free testing of linear functions on $\mathbb{R}^{n}$.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [GGR98] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM, 45:653–750, 1998.
  * [GJ79] M. R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [GKK08] Parikshit Gopalan, Adam Kalai, and Adam Klivans.  Agnostically learning decision trees.  In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pages 527–536, 2008.
  * [GKMP20] Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi.  Automating cutting planes is NP-hard.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 68–77, 2020.
  * [GLR99] David Guijarro, Vıctor Lavın, and Vijay Raghavan.  Exact learning when irrelevant variables abound.  Information Processing Letters, 70(5):233–239, 1999.
  * [Han93] Thomas Hancock.  Learning $k$$\mu$ decision trees on the uniform distribution.  In Proceedings of the 6th Annual Conference on Computational Learning Theory (COLT), pages 352–360, 1993.
  * [Har19] Nathaniel Harms.  Testing halfspaces over rotation-invariant distributions.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 694–713. SIAM, 2019.
  * [Hau88] David Haussler.  Quantifying inductive bias: Ai learning algorithms and valiant’s learning framework.  Artificial intelligence, 36(2):177–221, 1988.
  * [HJLT96] Thomas Hancock, Tao Jiang, Ming Li, and John Tromp.  Lower bounds on learning decision lists and trees.  Information and Computation, 126(2):114–122, 1996.
  * [HKY18] Elad Hazan, Adam Klivans, and Yang Yuan.  Hyperparameter optimization: A spectral approach.  Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
  * [HR76] Laurent Hyafil and Ronald L Rivest.  Constructing optimal binary decision trees is NP-complete.  Information processing letters, 5(1):15–17, 1976.
  * [HY22] Nathaniel Harms and Yuichi Yoshida.  Downsampling for Testing and Learning in Product Distributions.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 71:1–71:19, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of $k$-SAT.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.
  * [JS05] Jeffrey C Jackson and Rocco A Servedio.  Learning random log-depth decision trees under uniform distribution.  SIAM Journal on Computing, 34(5):1107–1128, 2005.
  * [KI21] CS Karthik and Livni-Navon Inbal.  On hardness of approximation of parameterized set cover and label cover: Threshold graphs from error correcting codes.  In Symposium on Simplicity in Algorithms (SOSA), pages 210–223. SIAM, 2021.
  * [KLM18] CS Karthik, Bundit Laekhanukit, and Pasin Manurangsi.  On the parameterized complexity of approximating dominating set.  In 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1283–1296. ACM, 2018.
  * [KM93] Eyal Kushilevitz and Yishay Mansour.  Learning decision trees using the Fourier spectrum.  SIAM Journal on Computing, 22(6):1331–1348, December 1993.
  * [KM96] Michael Kearns and Yishay Mansour.  On the boosting ability of top-down decision tree learning algorithms.  In Proceedings of the 28th Annual Symposium on the Theory of Computing (STOC), pages 459–468, 1996.
  * [KPB99] S Rao Kosaraju, Teresa M Przytycka, and Ryan Borgstrom.  On an optimal split tree problem.  In Workshop on Algorithms and Data Structures, pages 157–168. Springer, 1999.
  * [KS06] Adam Klivans and Rocco Servedio.  Toward attribute efficient learning of decision lists and parities.  Journal of Machine Learning Research, 7(Apr):587–602, 2006.
  * [KST09] Adam Kalai, Alex Samorodnitsky, and Shang-Hua Teng.  Learning and smoothed analysis.  In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 395–404, 2009.
  * [LCS+18] Zhengyang Liu, Xi Chen, Rocco A Servedio, Ying Sheng, and Jinyu Xie.  Distribution-free junta testing.  ACM Transactions on Algorithms (TALG), 15(1):1–23, 2018.