# Superconstant inapproximability of decision tree learning

Caleb Koch
Stanford Carmen Strassle
Stanford Li-Yang Tan
Stanford

###### Abstract

We consider the task of properly PAC learning decision trees with queries.
Recent work of Koch, Strassle, and Tan showed that the strictest version of
this task, where the hypothesis tree $T$ is required to be optimally small, is
NP-hard. Their work leaves open the question of whether the task remains
intractable if $T$ is only required to be close to optimal, say within a
factor of $2$, rather than exactly optimal.

We answer this affirmatively and show that the task indeed remains NP-hard
even if $T$ is allowed to be within any constant factor of optimal. More
generally, our result allows for a smooth tradeoff between the hardness
assumption and inapproximability factor. As Koch et al.’s techniques do not
appear to be amenable to such a strengthening, we first recover their result
with a new and simpler proof, which we couple with a new XOR lemma for
decision trees. While there is a large body of work on XOR lemmas for decision
trees, our setting necessitates parameters that are extremely sharp and are
not known to be attainable by existing such lemmas. Our work also carries new
implications for the related problem of Decision Tree Minimization.

##  1 Introduction

Decision trees are a basic and popular way to represent data. Their simple
logical structure makes them the prime example of an interpretable model. They
are also the base model at the heart of powerful ensemble methods, such as
XGBoost and random forests, that achieve state-of-the-art performance in
numerous settings. Owing in part to their practical importance, the task of
efficiently constructing decision tree representations of data has been
intensively studied in the theory community for decades, in a variety of
models and from both algorithmic and hardness perspectives. Indeed, on the
heels of Cook and Karp’s papers on the theory of NP-hardness, [HR76] proved
that a certain formulation of decision tree learning is NP-hard. Quoting their
introduction, “While the proof to be given is relatively simple, 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.” This effort has only compounded over the
years, with a recent surge of interest coming from the interpretable machine
learning community; the 2022 survey [RCC+22] lists decision tree learning as
the very first of the field’s “10 grand challenges”.

We consider the problem within the model of PAC learning with queries [Val84,
Ang88]. In this model, the learner is given query access to a function $f$ and
i.i.d. draws from a distribution $\mathcal{D}$, along with the promise that
$f$ is computable by a size-$s$ decision tree. Its task is to output a
size-$s^{\prime}$ decision tree that achieves high accuracy with respect to
$f$ under $\mathcal{D}$, where $s^{\prime}$ is as close to $s$ as possible.
Motivation for studying query learners for this problem is twofold. First, it
models the task of converting an existing trained model $f$, for which one has
query access to, into its decision tree representation—a common post-
processing step for interpretability reasons. The second, more intrinsic,
motivation comes from the fact that computational lower bounds against query
learners, for any learning task, have generally been elusive. We are aware of
only one such result outside of decision tree learning, on the NP-hardness of
learning DNF formulas with queries [Fel06]—this resolved a longstanding open
problem of [Val84, Val85].

####  [KST23a].

For decision tree learning, recent work of Koch, Strassle, and Tan showed that
the strictest version of the problem, where $s^{\prime}=s$, is NP-hard. This
resolved an open problem that had been raised repeatedly over the years
[Bsh93, GLR99, MR02, Fel16], but still left open the possibility of efficient
algorithms achieving $s^{\prime}$ that is slightly larger than $s$. [KST23a]
listed this as an natural avenue for further research, while also pointing to
challenges in extending their techniques to even rule out $s^{\prime}=2s$.

###  1.1 This work

We show that the problem remains NP-hard even for $s^{\prime}=Cs$ where $C$ is
an arbitrarily large constant:

######  Theorem 1.

For every constant $C>1$, there is a constant $\varepsilon>0$ such that the
following holds. If there is an algorithm running in time $t(n)$ that, given
queries to an $n$-variable function $f$ computable by a decision tree of size
$s=O(n)$ and random examples $(\bm{x},f(\bm{x}))$ drawn according to a
distribution $\mathcal{D}$, outputs w.h.p. a decision tree of size $Cs$ that
is $\varepsilon$-close to $f$ under $\mathcal{D}$, then SAT can be solved in
randomized time $O(n^{2})\cdot t(\mathrm{poly}(n))$.

Consequently, assuming $\mathrm{NP}\neq\mathrm{RP}$, any algorithm for the
problem has to either be inefficient with respect to time (i.e. take
superpolynomial time), or inefficient with respect to representation size
(i.e. output a hypothesis of size much larger than actually necessary).

Theorem 1 is a special case of a more general result that allows for a smooth
tradeoff between the strength of the hardness assumption on one hand and the
inapproximability factor on the other hand:

######  Theorem 2.

Suppose for some $r\geq 1$ there is a time $t(s,1/\varepsilon)$ algorithm
which given queries to an $n$-variable function $f$ computable by a decision
tree of size $s$ and random examples $(\bm{x},f(\bm{x}))$ drawn according to a
distribution $\mathcal{D}$, outputs w.h.p. a decision tree of size
$2^{O(r)}\cdot s$ that is $\varepsilon$-close to $f$ under $\mathcal{D}$. Then
$\mathrm{SAT}$ can be solved in randomized time $\tilde{O}(rn^{2})\cdot
t(n^{O(r)},2^{O(r)})$.

By taking $r$ to be superconstant in Theorem 2, we obtain superconstant
inapproximability ratios at the price of stronger yet still widely-accepted
hardness assumptions. For example, assuming SAT cannot be solved in randomized
quasipolynomial time, we get a near-polynomial inapproximability ratio of
$2^{(\log s)^{\gamma}}$ for any constant $\gamma<1$.

Our work also carries new implications for the related problem of Decision
Tree Minimization: Given a decision tree $T$, construct an equivalent decision
tree $T^{\prime}$ of minimal size. This problem was first shown to be NP-hard
by [ZB00], and subsequently [Sie08] showed that it is NP-hard even to
approximate. We recover [Sie08]’s inapproximability result, and in fact
strengthen it to hold even if $T^{\prime}$ is only required to mostly agree
with $T$ on a given subset of inputs (rather than fully agree with $T$ on all
inputs as in [Sie08]). See Section 11 for details.

##  2 Background and Context

###  2.1 Algorithms for properly learning decision trees

In the language of learning theory, we are interested in the task of properly
PAC learning decision trees. We distinguish between strictly-proper learning,
where the size $s^{\prime}$ of the hypothesis decision tree has to exactly
match the optimal size $s$ of the target decision tree, and weakly-proper
learning, where $s^{\prime}$ can be larger than $s$. [KST23a] therefore
establishes the hardness of strictly-proper learning whereas our work
establishes the hardness even of weakly-proper learning even when $s^{\prime}$
is larger than $s$ by any constant. We now overview the fastest known
algorithms for both settings.

#### Strictly-proper learning via dynamic programming.

There is a simple $2^{O(n)}$ time algorithm for strictly-properly learning
decision trees: draw a dataset of size $O(s\log n)$, dictated by the VC
dimension of size-$s$ decision trees, and run a $2^{O(n)}$-time dynamic
program to find a size-$s$ decision tree that fits the dataset perfectly. (See
[GLR99, MR02] for a description of this dynamic program.) There are no known
improvements to this naive algorithm if one insists on strictly-proper
learning, and indeed, [KST23a]’s result strongly suggests that there are
probably none.

#### Weakly-proper learning via Ehrenfeucht–Haussler.

The setting of weakly-proper learning allows for a markedly faster algorithm:
a classic algorithm of [EH89] runs in $n^{O(\log s)}$ time and outputs a
decision tree hypothesis of size $s^{\prime}=n^{O(\log s)}$. [EH89] listed as
an open problem that of designing algorithms that output smaller hypotheses,
i.e. ones where $s^{\prime}$ is closer to $s$. There has been no algorithmic
progress on this problem since 1989, and prior to our work, there were also no
hardness results ruling out efficient algorithms achieving say
$s^{\prime}=2s$.

###  2.2 Lower bounds for random example learners

Inapproximability factor Lower bounds against random-example learners Lower
bounds against query learners Exact (i.e. strictly-proper learning)
Superconstant Polynomial Superpolynomial Quasipolynomial (matching [EH89]’s
guarantee) [PV88] (under $\mathrm{NP}\neq\mathrm{RP}$) [HJLT96] (under
$\mathrm{NP}\neq\mathrm{RP}$) [ABF+09] (under ETH) [KST23b] (under ETH)
[KST23b] (under inapproximability of parameterized Set Cover) [KST23a] (under
$\mathrm{NP}\neq\mathrm{RP}$) This work (under $\mathrm{NP}\neq\mathrm{RP}$)
Figure 1: Summary of lower bounds for decision tree learning.

The problem is also well-studied in the model of PAC learning from random
examples, where the algorithm is only given labeled examples
$(\bm{x},f(\bm{x}))$ where $\bm{x}\sim\mathcal{D}$. Lower bounds against
random example learners are substantially easier to establish, and a sequence
of works has given strong evidence of the optimality [EH89]’s weakly-proper
algorithm under standard complexity-theoretic assumptions.

[PV88], in an early paper on the hardness of PAC learning, showed that
strictly-proper learning of decision trees from random examples is NP-hard;
they attributed this result to an unpublished manuscript of [Ang]. [HJLT96]
then established a superconstant inapproximability factor (assuming
$\mathrm{NP}\neq\mathrm{RP}$), which was subsequently improved to polynomial
by [ABF+09] (assuming the Exponential Time Hypothesis (ETH)). Recent work of
[KST23b] further improves the inapproximability factor to superpolynomial
(assuming ETH) and quasipolynomial (assuming the inapproximability of
parameterized Set Cover), the latter of which exactly matches [EH89]’s
performance guarantee.

It is reasonable to conjecture that [EH89]’s algorithm is optimal even for
query learners. If so, our work is a step forward for proving lower bounds in
the more challenging setting of query learners so that these bounds might
“catch up” with those in the random example setting; historically, the race
has not been close—query-learner lower bounds have lagged far behind. Just as
[KST23a] can be viewed as establishing the query-learner analogue of [PV88]’s
result (i.e. the hardness of strictly-proper learning), our work can be viewed
as establishing the query-learner analogue of [HJLT96]’s result (i.e.
superconstant inapproximability of weakly-proper learning). Figure 1
summarizes the current landscape of decision tree lower bounds and shows how
our work fits into it.

We refer the reader to Section 2.1 of [KST23a] for a discussion of the
technical challenges involved in proving lower bounds against query learners,
and why the techniques developed in [PV88, HJLT96, ABF+09, KST23b] for random-
example learners do not carry over.

###  2.3 Other related work: improper learning of decision trees

There is also vast literature on improper learning of decision trees, where
the target function is assumed to be a small decision tree but the hypothesis
does not have to be one (see e.g. [Riv87, Blu92, KM93, Han93, Bsh93, BFJ+94,
HJLT96, JS06, OS07, KS06, GKK08, KST09, HKY18, CM19]). Examples of hypotheses
that are constructed by existing algorithms include the sign of low-degree
polynomials and small-depth boolean circuits.

##  3 Technical Overview

At a high level, our proof proceeds in two steps:

  * $\circ$

Step 1: Slight inapproximaibility. We first give a new proof of [KST23a]’s
result. In fact, we prove a statement that is (very) slightly stronger than
the hardness of strictly-proper learning: we show that it is NP-hard for query
learners to construct a decision tree of size $s^{\prime}=(1+\delta)\cdot s$
for small constant $\delta<1$. While such a slight strengthening is not of
much independent interest, it is important for technical reasons because it
establishes some inapproximability factor, albeit a small one, which we then
amplify in the next step.

  * $\circ$

Step 2: Gap amplification. We give a reduction that for any integer $r$ runs
in time $n^{O(r)}$ and amplifies the inapproximability factor of
$s^{\prime}/s=1+\delta$ from the step above into $(1+\delta)^{r}$. In
particular, for any arbitrarily large constant $C$ this is a reduction that
runs in polynomial time and amplifies the inapproximability factor to $C$.

At the heart of this reduction is a new XOR lemma for decision trees: roughly
speaking, this lemma says that if decision trees of size $s^{\prime}$ incur
large error when computing $f$, then decision trees of size $(s^{\prime})^{r}$
incur large error when computing the $r$-fold XOR $f^{\oplus
r}(x^{(1)},\ldots,x^{(r)})\coloneqq f(x^{(1)})\oplus\cdots\oplus f(x^{(r)})$.

There is a large body of work on XOR lemmas for decision tree complexity
[IRW94, NRS94, Sav02, Sha04, KŠdW07, JKS10, Dru12, BDK18, BB19, BKLS20], but
our setting necessitates extremely sharp parameters that are not known to be
achievable by any existing ones. Most relevant to our setting is one by
[Dru12], but it only reasons about the error of decision trees of size
$(s^{\prime})^{cr}$ for some $c<1$ instead of $(s^{\prime})^{r}$. This
constant factor loss is inherent to [Dru12]’s proof technique, and we explain
in Remark 10.3 why we cannot afford even a tiny constant factor loss in the
exponent.

###  3.1 Step 1: Slight inapproximability

Like [KST23a], we reduce from the NP-complete problem Vertex Cover. For every
graph $G$ there is an associated edge indicator function $\mathrm{\sc IsEdge}$
defined as follows:

######  Definition 3.1 ($\mathrm{\mathrm{\sc IsEdge}}_{G}$).

Let $G$ be a graph with vertex set $V=\\{v_{1},\ldots,v_{n}\\}$. We write
$\mathrm{Ind}[e]\in\\{0,1\\}^{n}$ for the encoding of an edge $e\in E$ in
$\\{0,1\\}^{n}$. That is, $\mathrm{Ind}[e]_{i}=1$ if and only if the vertex
$v_{i}$ is in $e$. The edge indicator function of $G$ is the function
$\mathrm{\mathrm{\sc IsEdge}}_{G}:\\{0,1\\}^{n}\to\\{0,1\\}$,

$\mathrm{\mathrm{\sc IsEdge}}_{G}(x)=\begin{cases}1&x=\mathrm{Ind}[e]\text{
for some $e\in E$}\\\ 0&\text{otherwise.}\end{cases}$

For technical reasons, we work with a generalization of $\mathrm{\sc IsEdge}$
called $\ell$-$\mathrm{\sc IsEdge}$ where $\ell\in\mathds{N}$ is a tuneable
“padding parameter” (we defer the definition of $\ell$-$\mathrm{\sc IsEdge}$
to the main body; see Definition 7.1). We prove that the decision tree
complexity of $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}$ scales with the
vertex cover complexity of $G$ with fairly tight quantitative parameters:

######  Claim 3.2.

Let $G$ be a graph on $n$ vertices and $m$ edges. For all $\ell\geq 1$ and
$\varepsilon>0$, the following two cases hold.

  * $\circ$

Yes case: if $G$ has a vertex cover of size $k$, then there is a decision tree
$T$ computing $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}$ whose size
satisfies

$|T|\leq(\ell+1)(k+m)+mn.$

  * $\circ$

No case: there is a distribution $\mathcal{D}$ such that if every vertex cover
of $G$ has size at least $k^{\prime}$, then any decision tree $T$ that is
$\varepsilon$-close to $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}$ over
$\mathcal{D}$ has size at least

$|T|\geq(\ell+1)\left(k^{\prime}+(1-4\varepsilon)m\right).$

It is known that there is a constant $\delta>0$ such that deciding whether a
graph has a vertex cover of size $\leq k$ or requires vertex cover size
$\geq(1+\delta)k$ is NP-hard [PY91, Hås01, DS05]. With an appropriate choice
of parameters, 3.2 translates this into a gap of $\leq s$ versus
$\geq(1+\delta^{\prime})s$ for some other constant $\delta^{\prime}>0$ in the
decision tree complexity of $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}$. The
NP-query hardness of learning size-$s$ decision trees with hypotheses of size
$(1+\delta^{\prime})s$ follows as a corollary.

#### Key ingredients in the proof of 3.2: Patch up and hard distribution
lemmas.

As is often the case in reductions such as 3.2, the upper bound in the Yes
case is straightforward to establish and most of the work goes into proving
the lower bound in the No case. [KST23a]’s analysis of their No case is rather
specific to the $\ell\text{-}\mathrm{\sc IsEdge}$ function, whereas we develop
a new technique for proving such lower bounds on decision tree complexity. In
addition to being more general and potentially useful in other settings, our
technique lends itself to an “XOR-ed generalization” which we will need for
gap amplification. ([KST23a]’s technique does not appear to be amenable to
such a generalization, despite our best efforts at obtaining it.111On a more
technical level, [KST23a]’s technique requires them to reason about the
complexity of Partial Vertex Cover, a generalization of Vertex Cover, whereas
our simpler approach bypasses the need for this.)

There are two components to our technique, both of which are generic
statements concerning a decision tree $T$ that imperfectly computes a function
$f$. The first is a patch up lemma that shows how $T$ can be patched up so
that it computes $f$ perfectly. The cost of this patch up operation, i.e. how
much larger $T$ becomes, is upper bounded by the certificate complexity of
$f$, a basic and well-studied complexity measure of functions. (We defer the
formal definitions of the technical terms and notation used in these lemmas to
Section 4.)

######  Lemma 3.3 (Patch up lemma).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a function and let $T$ be a decision
tree. Then

$\mathrm{DT}(f)\leq|T|+\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f_{\pi(x)},x)$

where $\pi(x)$ denote the path followed by $x$ in $T$ and $f_{\pi(x)}$ is the
restriction of $f$ by $\pi(x)$.

The second component is a hard distribution lemma that shows how a hard
distribution $\mathcal{D}$ can be designed so that the error of $T$ with
respect to $f$ under $\mathcal{D}$ is large. Roughly speaking, the more weight
that $\mathcal{D}$ places on “highly sensitive” points, the larger the error
is:

######  Lemma 3.4 (Hard distribution lemma).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a nonconstant function. Then for all
nonempty $C\subseteq f^{-1}(1)$, there is a distribution over $C$ and all of
its sensitive neighbors such that for any decision tree $T$, we have

$\mathrm{error}_{\mathcal{D}}(T,f)\geq\frac{1}{2|C|\mathrm{Sens}(f)}\sum_{x\in
S}|\mathrm{Sens}(f_{\pi(x)},x)|$

where $\pi(x)$ is the path followed by $x$ in $T$ and $f_{\pi(x)}$ is the
restriction of $f$ by $\pi(x)$.

The No case of 3.2 follows by applying Lemmas 3.3 and 3.4 to the
$\ell$-$\mathrm{\sc IsEdge}$ function and reasoning about its certificate
complexity and sensitivity.

###  3.2 Step 2: Gap amplification

As alluded to above, a key advantage of our approach is that the patch up and
hard distribution lemmas lend themselves to “XOR-ed generalizations”:

######  Lemma 3.5 (XOR-ed version of Patch Up Lemma, see Lemma 8.1 for the
exact version).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a function and let $T$ be a decision
tree. Then for all $r\geq 1$,

$\mathrm{DT}(f^{\oplus r})\leq|T|+2^{r}\sum_{x\in
f^{-1}(1)^{r}}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(f_{\pi(x)},x^{(i)})\\}$

where $\pi(x)$ is the path followed by $x$ in $T$ and $f_{\pi(x)}$ is the
restriction of $f$ by $\pi(x)$.

######  Lemma 3.6 (XOR-ed version of Hard Distribution Lemma, see Lemma 9.1
for the exact version).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a nonconstant function, $C\subseteq
f^{-1}(1)$ be nonempty, and $T$ be a decision tree. There is a distribution
$\mathcal{D}$ over the inputs in $C$ and their sensitive neighbors such that
for all $r\geq 1$,

$\mathrm{error}_{\mathcal{D}^{\otimes r}}(T,f^{\oplus
r})\geq\left(\frac{1}{2|C|\mathrm{Sens}(f)}\right)^{r}\sum_{x\in
C^{r}}\prod_{i=1}^{r}\max\\{1,|\mathrm{Sens}(f_{\pi(x)},x^{(i)})|\\}$

where $\pi(x)$ is the path followed by $x$ in $T$ and $f_{\pi(x)}$ is the
restriction of $f$ by $\pi(x)$.

Just as how Lemmas 3.3 and 3.4 combine to yield 3.2, combining their XOR-ed
generalizations Lemmas 3.3 and 9.1 yields the following amplified version of
of 3.2:

######  Claim 3.7.

Let $G$ be a graph on $n$ vertices and $m$ edges. For all $\ell,r\geq 1$ and
$\varepsilon>0$, the following two cases hold.

  * •

Yes case: if $G$ has a vertex cover of size $k$, then there is a decision tree
$T$ computing $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}^{\oplus r}$ whose
size satisfies

$|T|\leq\big{[}(\ell+1)(k+m)+mn\big{]}^{r}.$

  * •

No case: there is a distribution $\mathcal{D}$ such that if every vertex cover
of $G$ has size at least $k^{\prime}$, then any decision tree $T$ that is
$\varepsilon$-close to $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}^{\oplus
r}$ over $\mathcal{D}$ has size at least

$|T|\geq\big{[}(\ell+1)(k^{\prime}+m)\big{]}^{r}-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}.$

With an appropriate choice of parameters, 3.7 translates a gap of $\leq k$
versus $\geq(1+\delta)k$ in the vertex cover complexity of $G$ into a gap of
$\leq s^{r}$ versus $\geq(1+\delta^{\prime})^{r}s^{r}$ in the decision tree
complexity of $\ell$-$\mathrm{\sc IsEdge}_{G}^{\oplus r}$, where
$\delta^{\prime}$ is a constant that depends only on $\delta$. Theorem 2
follows as a corollary. See Figure 2 for an illustration of this amplification
and how it fits into our overall reduction from Vertex Cover.

$0$$n$$0$$2^{n}$$0$$2^{n}$$\mathrm{VC}(G)\leq
k$$\mathrm{VC}(G)>(1+\delta)k$size-$(1+\delta^{\prime})s$ DTsize-$s$
DTsize-$(1+\delta^{\prime})^{r}s^{r}$ DTsize-$s^{r}$ DTStep 2: gap
amplification Step 1: Slight inapproximability Vertex cover size of $G$ DT
size of $\ell\text{-}\mathrm{\sc IsEdge}_{G}$ under $\mathcal{D}$ DT size of
$\ell\text{-}\mathrm{\sc IsEdge}_{G}^{\oplus r}$ under $\mathcal{D}^{\otimes
r}$ Figure 2: An illustration of main reduction from Vertex Cover in two
steps. The first step, which establishes slight inapproximability of decision
tree learning, is proved in 3.2. The second step amplifies this slight
inapproximability gap using 3.7.

##  4 Preliminaries

#### Notation and naming conventions.

We write $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. We use lower case
letters to denote bitstrings e.g. $x,y\in\\{0,1\\}^{n}$ and subscripts to
denote bit indices: $x_{i}$ for $i\in[n]$ is the $i$th index of $x$. The
string $x^{\oplus i}$ is $x$ with its $i$th bit flipped. We use superscripts
to denote multiple bitstrings of the same dimension, e.g.
$x^{(1)},x^{(2)},...,x^{(j)}\in\\{0,1\\}^{n}$. For a set $S$ and an integer
$r\geq 1$, we write $S^{r}$ to denote the $r$-ary Cartesian product of the
set.

#### Distributions.

We use boldface letters e.g. $\bm{x},\bm{y}$ to denote random variables. For a
distribution $\mathcal{D}$, we write
$\mathrm{error}_{\mathcal{D}}(f,g)=\operatorname{{Pr}}_{\bm{x}\sim\mathcal{D}}[f(\bm{x})\neq
g(\bm{x})]$. The support of the distribution is the set of elements with
nonzero mass and is denoted $\mathrm{supp}(\mathcal{D})$. For $r\geq 1$, we
write $\mathcal{D}^{\otimes r}$ to denote the $r$-wise product distribution
$\underbrace{\mathcal{D}\times\cdots\times\mathcal{D}}_{r\text{ times }}$.

#### Decision trees.

The size of a decision tree $T$ is its number of leaves and is denoted $|T|$.
In an abuse of notation, we also write $T$ for the function computed by the
decision tree $T$. We say $T$ computes a function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ if $T(x)=f(x)$ for all $x\in\\{0,1\\}^{n}$. The
decision tree complexity of a function $f$ is the size of the smallest
decision tree computing $f$ and is denoted $\mathrm{DT}(f)$.

#### Restrictions and decision tree paths.

A restriction $\rho$ is a set
$\rho\subseteq\\{x_{1},\overline{x}_{1},\ldots,x_{n},\overline{x}_{n}\\}$ of
literals, and $f_{\rho}$ is the subfunction obtained by restricting $f$
according to $\rho$: $f_{\rho}(x^{\star})=f(x^{\star}|_{\rho})$ where
$x^{\star}|_{\rho}$ is the string obtained from $x^{\star}$ by setting its
$i$th coordinate to $1$ if $x_{i}\in\rho$, $0$ if $\overline{x}_{i}\in\rho$,
and otherwise setting it to $x^{\star}_{i}$. We say an input $x^{\star}$ is
consistent with $\rho$ if $x_{i}\in\rho$ implies $x^{\star}_{i}=1$ and
$\overline{x}_{i}\in\rho$ implies $x^{\star}_{i}=0$.

Paths in decision trees naturally correspond to restrictions. A depth-$d$ path
can be identified with a set of $d$ literals:
$\pi=\\{\ell_{1},\ell_{2},\ldots,\ell_{d}\\}$ where each $\ell_{i}$
corresponds to a query of an input variable and is unnegated if $\pi$ follows
the right branch and negated if $\pi$ follows the left branch.

#### Boolean Functions.

We use $f$ to denote an arbitrary $n$-bit Boolean function,
$f:\\{0,1\\}^{n}\to\\{0,1\\}$. For a set $D\subseteq\\{0,1\\}^{n}$, we write
$f:D\to\\{0,1\\}$ for the partial Boolean function defined on $D$. We use both
partial and total functions and specify the setting by writing either
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ or $f:D\to\\{0,1\\}$. For $f:D\to\\{0,1\\}$, the
sensitivity of $f$ on $x\in D$ and the certificate complexity of $f$’s value
on $x$ are defined as

$\displaystyle\mathrm{Sens}(f,x)$ $\displaystyle=\\{x^{\oplus i}\in D:f(x)\neq
f(x^{\oplus i})\text{ for }i\in[n]\\}$ $\displaystyle\mathrm{Cert}(f,x)$
$\displaystyle=|\pi|\text{ s.t. }\pi\text{ is the shortest restriction
consistent with }x\text{ and }$ $\displaystyle\quad\quad f_{\pi}\text{ is a
constant function}.$

Note that both of these definitions are with respect to $D$. Also, we refer to
the sensitivity of $f$ which is $\mathrm{Sens}(f)\coloneqq\max_{x\in
D}|\mathrm{Sens}(f,x)|$.

#### Graphs.

An undirected graph $G=(V,E)$ has $n$ vertices $V\subseteq[n]$ and $m=|E|$
edges $E\subseteq V\times V$. The degree of a vertex $v\in V$ is the number of
edges containing it: $|\\{e\in E:v\in e\\}|$. The graph $G$ is degree-$d$ if
every vertex $v\in V$ has degree at most $d$. We often use letters $v,u,w$ to
denote vertices of a graph $G$.

#### Learning.

In the PAC learning model, there is an unknown distribution $\mathcal{D}$ and
some unknown target function $f\in\mathcal{C}$ from a fixed concept class
$\mathcal{C}$ of functions over a fixed domain. An algorithm for learning
$\mathcal{C}$ over $\mathcal{D}$ takes as input an error parameter
$\varepsilon\in(0,1)$ and has oracle access to an example oracle
$\textnormal{EX}(f,\mathcal{D})$. The algorithm can query the example oracle
to receive a pair $(\bm{x},f(\bm{x}))$ where $\bm{x}\sim\mathcal{D}$ is drawn
independently at random. The goal is to output a hypothesis $h$ such that
$\mathrm{dist}_{\mathcal{D}}(f,h)\leq\varepsilon$. Since the example oracle is
inherently randomized, any learning algorithm is necessarily randomized. So we
require the learner to succeed with some fixed probability e.g. $2/3$. A
learning algorithm is proper if it always outputs a hypothesis
$h\in\mathcal{C}$. A learning algorithm with queries is given oracle access to
the target function $f$ along with the example oracle
$\textnormal{EX}(f,\mathcal{D})$.

###  4.1 Vertex Cover

#### Vertex cover.

A vertex cover for an undirected graph $G=(V,E)$ is a subset of the vertices
$C\subseteq V$ such that every edge has at least one endpoint in $C$. We write
$\mathrm{VC}(G)$ to denote the size of the smallest vertex cover of $G$. The
Vertex Cover problem is to decide whether a graph contains a vertex cover of
size $\leq k$. For $a>1$, an $a$-approximation of Vertex Cover corresponds to
the problem of deciding whether a graph contains a vertex cover of size $\leq
k$ or every vertex cover has size at least $a\cdot k$. There is a polynomial-
time greedy algorithm for vertex cover which achieves a $2$-approximation.

#### Hardness of approximation.

Constant factor hardness of Vertex Cover is known, even for bounded degree
graphs (graphs whose degree is bounded by some universal constant). This is
the main hardness result we reduce from in this work.

######  Theorem 3 (Hardness of approximating Vertex Cover).

There are constants $\delta>0$ and $d\in\mathds{N}$ such that if Vertex Cover
can be $(1+\delta)$-approximated on $n$-vertex degree-$d$ graphs in time
$t(n)$, then SAT can be solved in time $t(n\mathrm{polylog}n)$.

Theorem 3 follows from the works of [PY91, AS98, ALM+98]. The fact that
Theorem 3 holds for constant degree graphs will be essential for our lower
bound because it allows us to assume that $k$ is large:
$\mathrm{VC}(G)=\Theta(m)$.

######  Fact 4.1 (Constant degree graphs require large vertex covers).

If $G$ is an $m$-edge degree-$d$ graph, then $\mathrm{VC}(G)\geq m/d$.

This fact follows from the observation that in a degree-$d$ graph each vertex
can cover at most $d$ edges.

##  5 Patching up a decision tree: Proof of Lemma 3.3

We start with the following claim about building a decision tree from scratch
using certificates.

######  Claim 5.1 (Building a decision tree out of certificates).

Let $f:D\to\\{0,1\\}$ be a function with $D\subseteq\\{0,1\\}^{n}$, then

$\mathrm{DT}(f)\leq 1+\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f,x).$

###### Proof.

Let $T$ be the decision tree built iteratively by the following procedure. In
the first iteration, pick an arbitrary $x\in f^{-1}(1)$ and fully query the
indices in $\mathrm{Cert}(f,x)$. Let $T_{i}$ be the tree formed after the
$i$th iteration. Then $T_{i+1}$ is formed by choosing $x\in f^{-1}(1)$ which
has not been picked in a previous iteration. Then, at the leaf reached by $x$
in $T_{i}$, fully query the indices in $\mathrm{Cert}(f,x)$ (ignoring those
indices which have already been queried along the path followed by $x$ in
$T_{i}$). Repeating this for $|f^{-1}(1)|$ steps, yields a decision tree with
at most $\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f,x)$ internal nodes. Therefore,
the number of leaves is at most $1+\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f,x)$.

It remains to show that this tree exactly computes $f$. Specifically, we’ll
argue that $f_{\pi}$ is the constant function for every path $\pi$ in the
decision tree. If not, then there is an $x\in f^{-1}(1)$ so that $x$ follows
the path $\pi$ and $f_{\pi}$ is nonconstant. But this is a contradiction since
$\pi$ consists of a certificate of $x$ by construction. ∎

The next lemma shows that we can patch up a decision tree by querying
certificates. This recovers Lemma 3.3 in the setting where $D=\\{0,1\\}^{n}$.

######  Lemma 5.2 (Patch-up with respect to $1$-inputs).

Let $f:D\to\\{0,1\\}$ be a function with $D\subseteq\\{0,1\\}^{n}$ and let $T$
be a decision tree, then

$\mathrm{DT}(f)\leq|T|+\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f_{\pi(x)},x)$

###### Proof.

Let $\Pi$ denote the set of paths in $T$. Then,

$\displaystyle\mathrm{DT}(f)$
$\displaystyle\leq\sum_{\pi\in\Pi}\mathrm{DT}(f_{\pi})$
$\displaystyle\leq\sum_{\pi\in\Pi}\left(1+\sum_{x\in
f_{\pi}^{-1}(1)}\mathrm{Cert}(f_{\pi},x)\right)$ (5.1)
$\displaystyle=|T|+\sum_{\pi\in\Pi}\sum_{x\in
f_{\pi}^{-1}(1)}\mathrm{Cert}(f_{\pi},x)$ ($|\Pi|=|T|$)
$\displaystyle=|T|+\sum_{x\in f^{-1}(1)}\mathrm{Cert}(f_{\pi(x)},x).$

The last equality follows from the fact that the set of paths $\pi\in\Pi$
partition $f^{-1}(1)$. ∎

##  6 Hard distribution lemma: Proof of Lemma 3.4

Lemma 3.4 is proved for the canonical hard distribution for a partial function
$f:D\to\\{0,1\\}$.

######  Definition 6.1 (Canonical hard distribution).

For a function $f:D\to\\{0,1\\}$ with $D\subseteq\\{0,1\\}^{n}$, the canonical
hard distribution, $\mathcal{D}_{f}$, is defined via the following experiment

  * •

sample $\bm{x}\sim f^{-1}(1)$ u.a.r.

  * •

with probability $1/2$, return $\bm{y}\sim\mathrm{Sens}(f,\bm{x})$ u.a.r.

  * •

with probability $1/2$, return $\bm{x}$.

When $f$ is clear from context, we simply write $\mathcal{D}$. We use the
canonical hard distribution to prove the following result which recovers Lemma
3.4 in the setting where $D=\\{0,1\\}^{n}$.

######  Lemma 6.2 (Hard distribution lemma).

Let $f:D\to\\{0,1\\}$ be a nonconstant function for $D\subseteq\\{0,1\\}^{n}$.
Then for all $C\subseteq f^{-1}(1)$, there exists a distribution $\mathcal{D}$
over $C$ and and all of its sensitive neighbors such that for any decision
tree $T$, we have

$\mathrm{error}_{\mathcal{D}}(T,f)\geq\frac{1}{2|C|\mathrm{Sens}(f)}\sum_{x\in
C}|\mathrm{Sens}(f_{\pi(x)},x)|.$

First we prove a claim which counts the error under $\mathcal{D}$ conditioned
on the $1$-input obtained in the first sampling step.

######  Claim 6.3 (Error with respect to the canonical hard distribution
conditioned on a $1$-input).

Let $T$ be a decision tree, $f:D\to\\{0,1\\}$ be a function, and let
$\mathcal{D}$ be the canonical hard distribution. For all $x\in f^{-1}(1)$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}_{f}}[T(\bm{z})\neq
f(\bm{z})\mid\text{ first sampling }x\text{ from
}f^{-1}(1)]\geq\frac{1}{2}\cdot\frac{|\mathrm{Sens}(f_{\pi(x)},x)|}{\max\\{1,|\mathrm{Sens}(f,x)|\\}}.$

###### Proof.

If $|\mathrm{Sens}(f,x)|=0$ then $|\mathrm{Sens}(f_{\pi(x)},x)|=0$. And if the
RHS is $0$ then the bound is vacuously true. Assume that
$\mathrm{Sens}(f_{\pi(x)},x)\neq\varnothing$. Both $x$ and all
$y\in\mathrm{Sens}(f_{\pi(x)},x)$ follow the same path in $T$ and have the
same leaf label. Since $f(x)=1$ and $f(y)=0$, we can write

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}_{f}}\big{[}T(\bm{z})\neq
f(\bm{z})\mid\textnormal{first sampling }x$ $\displaystyle\textnormal{ from
}f^{-1}(1)\big{]}$ $\displaystyle\geq\min\bigg{\\{}$
$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}_{f}}\big{[}\bm{z}=x\mid\textnormal{first
sampling }x\textnormal{ from }f^{-1}(1)\big{]},$
$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}_{f}}\big{[}\bm{z}\in\mathrm{Sens}(f_{\pi(x)},x)\mid\textnormal{first
sampling }x\textnormal{ from }f^{-1}(1)\big{]}\bigg{\\}}$
$\displaystyle=\min\bigg{\\{}$
$\displaystyle\frac{1}{2},\frac{1}{2}\cdot\frac{|\mathrm{Sens}(f_{\pi(x)},x)|}{|\mathrm{Sens}(f,x)|}\bigg{\\}}\geq\frac{1}{2}\cdot\frac{|\mathrm{Sens}(f_{\pi(x)},x)|}{|\mathrm{Sens}(f,x)|}$

where the inequality follows from the fact that the probability of an error is
lower bounded by the probability that $\bm{z}=x$ when the label for the path
in $T$ is $0$ and is lower bounded by the probability that
$\bm{z}\in\mathrm{Sens}(f_{\pi(x)},x)$ when the label for the path is $1$.
Note that if $\mathrm{Sens}(f_{\pi(x)},x)\neq\varnothing$ then necessarily
$|\mathrm{Sens}(f,x)|\geq 1$ and
$\max\\{1,|\mathrm{Sens}(f,x)|\\}=|\mathrm{Sens}(f,x)|$. Therefore, the proof
is complete. ∎

###### Proof of Lemma 6.2.

We prove the statement for $C=f^{-1}(1)$. If $C\neq f^{-1}(1)$, we can
consider the function $f:C\cup C^{\prime}\to\\{0,1\\}$ where $C^{\prime}$
denotes the set of sensitive neighbors of strings in $C$, and the same proof
holds. Let $\mathcal{D}$ denote the distribution from Definition 6.1 and
notice that the support of this distribution is $C$ and all of its sensitive
neighbors. We have

$\displaystyle\mathrm{error}_{\mathcal{D}}(T,f)$
$\displaystyle=\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}}[T(\bm{z})\neq
f(\bm{z})]$ $\displaystyle=\sum_{x\in
C}\frac{1}{|C|}\cdot\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}}[T(\bm{z})\neq
f(\bm{z})\mid\text{ first sampling }x\text{ from }f^{-1}(1)]$
$\displaystyle\geq\frac{1}{2|C|}\sum_{x\in
C}\frac{|\mathrm{Sens}(f_{\pi(x)},x)|}{\max\\{1,|\mathrm{Sens}(f,x)|\\}}$
(6.3) $\displaystyle\geq\frac{1}{2|C|\cdot\mathrm{Sens}(f)}\sum_{x\in
C}|\mathrm{Sens}(f_{\pi(x)},x)|$
($\max\\{1,|\mathrm{Sens}(f,x)|\\}\leq\mathrm{Sens}(f)$ for all $x$)

where the last step uses the fact that $\mathrm{Sens}(f)\geq 1$ since $f$ is
nonconstant. In particular, we have that
$\max\\{1,|\mathrm{Sens}(f,x)|\\}\leq\mathrm{Sens}(f)$ for all $x$. ∎

##  7 Hardness of learning via $\ell$-$\mathrm{\sc IsEdge}$

We are interested in the following learning task.

DT-Learn$(s,s^{\prime},\varepsilon)$: Given queries to an unknown function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, random samples from a distribution
$\mathcal{D}$ over $\\{0,1\\}^{n}$, parameters $s,s^{\prime}\in\mathds{N}$ and
$\varepsilon\in(0,1)$, and the promise that $f$ is a size-$s$ decision tree,
construct a size-$s^{\prime}$ decision tree $T$ that is $\varepsilon$-close to
$f$ under $\mathcal{D}$.

The main theorem of this section is the following reduction from approximating
Vertex Cover to DT-Learn. This theorem recovers, via a simpler proof, the main
reduction in [KST23a], while also achieving a better dependence on the Vertex
Cover approximation factor. Later, we build on this reduction to prove our
main result Theorem 1.

######  Theorem 4 (Reduction from Vertex Cover to DT-Learn).

If there is a time-$t(n,1/\varepsilon)$ algorithm solving DT-
Learn$(s,(1+\delta)s,\varepsilon)$ over $n$-variable functions for any
$\varepsilon>0$, $s=O(n)$, and $\delta>0$, then Vertex Cover can be
$(1+\delta^{\prime})$-approximated on degree-$d$, $n$-vertex graphs in
randomized time $O(n^{2}\cdot t(n^{2},1/\varepsilon))$ for any
$\delta^{\prime}>(\delta+4\varepsilon)d+\delta$.

At a high level, Theorem 4 works by taking a graph $G$, and defining an
“amplified” version of the edge indicator function for $G$ (recall Definition
3.1). This function is called $\ell$-$\mathrm{\sc IsEdge}$ and is formally
defined as follows (see also [KST23a]).

######  Definition 7.1 (The $\ell$-amplified $\mathrm{\sc IsEdge}$ function).

Let $G=(V,E)$ be an $n$-vertex graph and $\ell\in\mathds{N}$. The
$\ell$-amplified edge indicator function of $G$ is the function

$\ell\text{-}\mathrm{\mathrm{\sc
IsEdge}}_{G}:\\{0,1\\}^{n}\times(\\{0,1\\}^{n})^{\ell}\to\\{0,1\\}$

defined as follows: $\ell\text{-}\mathrm{\mathrm{\sc
IsEdge}}_{G}(v^{(0)},v^{(1)},\ldots,v^{(\ell)})=1$ if and only if

  1. 1.

$\mathrm{\mathrm{\sc IsEdge}}_{G}(v^{(0)})=1$ (i.e. $v^{(0)}=\mathrm{Ind}[e]$
for some $e\in E$), and

  2. 2.

$v_{i}^{(1)}=\cdots=v_{i}^{(\ell)}=1$ for all $i\in[n]$ such that
$v_{i}^{(0)}=1$.

We write $\ell\text{-}\mathrm{Ind}[e]\in(\\{0,1\\}^{n})^{\ell+1}$ for the
generalized edge indicator $(\mathrm{Ind}[e],\ldots,\mathrm{Ind}[e])$. Note
that $\ell\text{-}\mathrm{\mathrm{\sc
IsEdge}}(\ell\text{-}\mathrm{Ind}[e])=1$.

###  7.1 Decision tree size upper bound for $\ell\text{-}\mathrm{\mathrm{\sc
IsEdge}}_{G}$: First part of 3.2

The upper bound in 3.2 follows from [KST23a, Theorem 2]:

######  Theorem 5 (Upper bound on decision tree size of $\ell$-$\mathrm{\sc
IsEdge}$ [KST23a, Theorem 2]).

Let $G$ be an $n$-vertex, $m$-edge graph with a vertex cover of size $k$.
Then, there is a decision tree $T$ computing $\ell\text{-}\mathrm{\sc
IsEdge}_{G}:\\{0,1\\}^{n\ell+n}\to\\{0,1\\}$ whose size satisfies

$|T|\leq(\ell+1)(k+m)+mn$

and $T$ can be computed in polynomial-time given $G$ and a size-$k$ vertex
cover of $G$.

The last part of Theorem 5, the constructivity of $T$, is implicit in the
proof of [KST23a, Theorem 2], but is made explicit in their paper when proving
Lemma 5.2 (see Section 5.3 of [KST23a]).

###  7.2 Decision tree size lower bound for $\ell\text{-}\mathrm{\mathrm{\sc
IsEdge}}_{G}$: Second part of 3.2

The lower bound in 3.2 is proved with respect to the canonical hard
distribution for $\ell\text{-}\mathrm{\mathrm{\sc IsEdge}}_{G}$:

######  Definition 7.2 (Canonical hard distribution for
$\ell\text{-}\mathrm{\sc IsEdge}$).

For a graph $G$, we write $\ell\text{-}\mathcal{D}_{G}$ to denote the
canonical hard distribution of $\ell\text{-}\mathrm{\sc IsEdge}$ and
$\ell\text{-}{D}_{G}=\mathrm{supp}(\ell\text{-}\mathcal{D}_{G})$ to denote the
support of the canonical hard distribution. As per Definition 6.1, this
distribution is defined via the experiment

  * •

sample $\ell\text{-}\mathrm{Ind}[e]$ u.a.r. among all generalized edge
indicators;

  * •

with probability $1/2$, return $\bm{y}$ sampled u.a.r. from the set of
sensitive neighbors:
$\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge},\ell\text{-}\mathrm{Ind}[e])$
$=\\{\ell\text{-}\mathrm{Ind}[e]^{\oplus i}\mid i\text{ is a
}1\text{-coordinate of }\ell\text{-}\mathrm{Ind}[e]\\}$; and

  * •

with probability $1/2$, return $\ell\text{-}\mathrm{Ind}[e]$.

######  Lemma 7.3 (Decision tree size lower bound for computing
$\ell\text{-}\mathrm{\sc IsEdge}$).

Let $T$ be a decision tree for $\ell\text{-}\mathrm{\sc IsEdge}_{G}$
satisfying
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}}(T,\ell\text{-}\mathrm{\sc
IsEdge})\leq\varepsilon$, then

$|T|\geq(\ell+1)\cdot(k^{\prime}+(1-4\varepsilon)m)$

where $m$ is the number of edges of $G$ and $k^{\prime}$ is the vertex cover
size of $G$.

We obtain Lemma 7.3 using an application of the general size lower bound from
Lemmas 5.2 and 6.2.

First, we give a basic zero-error lower bound on $\ell\text{-}\mathrm{\sc
IsEdge}$ and observe some properties about the sensitivity and certificate
complexity of $\ell\text{-}\mathrm{\sc IsEdge}$ in Lemmas 7.4, 7.5 and 7.6,
respectively.

######  Lemma 7.4 (Zero-error lower bound for $\ell\text{-}\mathrm{\sc
IsEdge}_{G}$; see [KST23a, Claim 6.6]).

Let $G$ be an $n$-vertex, $m$-edge graph where every vertex cover has size at
least $k^{\prime}$. Then, any decision tree $T$ computing
$\ell\text{-}\mathrm{\sc IsEdge}_{G}:\ell\text{-}{D}_{G}\to\\{0,1\\}$ over
$\ell\text{-}{D}_{G}$, the support of the canonical hard distribution, must
have size

$|T|\geq(\ell+1)(k^{\prime}+m).$

###### Proof.

The same lower bound is proved in Claim 6.6 of [KST23a] under a slightly
different subset of inputs. Specifically, they prove
$\mathrm{DT}(\ell\text{-}\mathrm{\sc IsEdge}_{G})\geq(\ell+1)(k^{\prime}+m)$
where $\ell\text{-}\mathrm{\sc IsEdge}_{G}:D^{\prime}\to\\{0,1\\}$ for the set
$D^{\prime}=\ell\text{-}{D}_{G}\cup\\{0^{n+\ell n}\\}$ which adds the all 0s
input. This small difference doesn’t change the lower bound since any decision
tree $T$ computing $\ell\text{-}\mathrm{\sc IsEdge}_{G}$ over the set
$\ell\text{-}{D}_{G}$ also computes it over $D^{\prime}$. Indeed, every
$1$-input to $\ell\text{-}\mathrm{\sc IsEdge}_{G}$ is sensitive on every
$1$-coordinate and so if $T$ satisfies $T(x)=\ell\text{-}\mathrm{\sc
IsEdge}_{G}(x)$ for every $x\in\ell\text{-}{D}_{G}$, then it must query every
$1$-coordinate of each $1$-input. Therefore, we can assume without loss of
generality that $T(0^{n+\ell n})=0$. ∎

######  Proposition 7.5 (Sensitivity of $\ell\text{-}\mathrm{\sc
IsEdge}_{G}$).

For a graph $G$, $\ell\geq 1$, and $\ell\text{-}\mathrm{\sc
IsEdge}_{G}:\ell\text{-}{D}_{G}\to\\{0,1\\}$, we have

$\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{G})=2(\ell+1).$

###### Proof.

Let $\ell\text{-}\mathrm{Ind}[e]$ be an edge indicator for an edge $e\in E$.
Let $i\in[n\ell+n]$ denote the index of a $1$-coordinate of
$\ell\text{-}\mathrm{Ind}[e]$. By definition, there are $2(\ell+1)$ many such
$i$ and each $i$ is sensitive: $\ell\text{-}\mathrm{\sc
IsEdge}_{G}(\ell\text{-}\mathrm{Ind}[e]^{\oplus i})=0$. Therefore,
$|\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge}_{G},\ell\text{-}\mathrm{Ind}[e])|=2(\ell+1)$. Conversely, for every
sensitive neighbor $\ell\text{-}\mathrm{Ind}[e]^{\oplus i}$, we have
$\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge}_{G},\ell\text{-}\mathrm{Ind}[e]^{\oplus
i})=\\{\ell\text{-}\mathrm{Ind}[e]\\}$ and so
$|\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge}_{G},\ell\text{-}\mathrm{Ind}[e]^{\oplus i})|=1$. Thus the overall
sensitivity is $\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{G})=2(\ell+1).$
∎

######  Proposition 7.6 (Sensitivity equals certificate complexity of
$1$-inputs).

Let $G$ be a graph and $\ell\text{-}\mathrm{\sc
IsEdge}:\ell\text{-}{D}_{G}\to\\{0,1\\}$, the corresponding edge function. For
all edge indicators $x=\ell\text{-}\mathrm{Ind}[e]$ and for all restrictions
$\pi$, we have

$\mathrm{Cert}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi},x)=|\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi},x)|.$

###### Proof.

By definition $|\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi},x)|$ is
the number of $1$-coordinates in $x$ which are not restricted by $\pi$. The
set of $1$-coordinates of $x$ not restricted by $\pi$ forms a certificate of
$\ell\text{-}\mathrm{\sc IsEdge}_{\pi}$ since fixing these coordinates forces
$\ell\text{-}\mathrm{\sc IsEdge}$ to be the constant $1$-function. It follows
that $\mathrm{Cert}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi},x)=|\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi},x)|$. ∎

###### Proof of Lemma 7.3.

For a graph consisting of $m$ edges, the number of $1$-inputs to
$\ell\text{-}\mathrm{\sc IsEdge}:\ell\text{-}{D}_{G}\to\\{0,1\\}$ is $m$.
Therefore,

$\displaystyle\varepsilon$
$\displaystyle\geq\frac{1}{2m\cdot\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge})}\sum_{x\in\ell\text{-}\mathrm{\sc
IsEdge}^{-1}(1)}|\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi(x)},x)|$
(Lemma 6.2)
$\displaystyle=\frac{1}{2m\cdot\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge})}\sum_{x\in\ell\text{-}\mathrm{\sc
IsEdge}^{-1}(1)}\mathrm{Cert}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi(x)},x)$
(Proposition 7.6)
$\displaystyle\geq\frac{1}{2m\cdot\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge})}\left(\mathrm{DT}(\ell\text{-}\mathrm{\sc
IsEdge},\ell\text{-}{D}_{G})-|T|\right).$ (Lemma 5.2)

Rearranging the above, we obtain

$\displaystyle|T|$ $\displaystyle\geq\mathrm{DT}(\ell\text{-}\mathrm{\sc
IsEdge},\ell\text{-}{D}_{G})-2\varepsilon
m\cdot\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge})$
$\displaystyle\geq(\ell+1)(k^{\prime}+m)-2\varepsilon
m\cdot\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge})$ (Lemma 7.4)
$\displaystyle=(\ell+1)(k^{\prime}+m)-4\varepsilon m(\ell+1)$ (Proposition
7.5)

which completes the proof. ∎

###  7.3 Putting things together to prove Theorem 4

The following key lemma is used in the analysis of correctness for the
reduction in Theorem 4. It follows from 3.2 and a careful choice of
parameters.

######  Lemma 7.7 (Main technical lemma).

For all $\delta,\delta^{\prime},\varepsilon>0$ and $d,k\geq 1$, the following
holds. Given a constant degree-$d$ graph $G$ with $m$ edges and parameter $k$,
there is a choice of $\ell=\Theta(|G|)$ and a polynomial-time computable
quantity $s\in\mathds{N}$ such that so long as
$\delta^{\prime}>(\delta+4\varepsilon)d+\delta$ and $dk\geq m$ we have:

  * •

Yes case: if $G$ has a vertex cover of size at most $k$, then there is a
decision tree of size at most $s$ which computes $\ell\text{-}\mathrm{\sc
IsEdge}:\\{0,1\\}^{n\ell+n}\to\\{0,1\\}$; and

  * •

No case: if every vertex cover of $G$ has size at least
$(1+\delta^{\prime})k$, then $(1+\delta)s<|T|$ for any decision tree $T$ with
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}}(T,\ell\text{-}\mathrm{\sc
IsEdge})\leq\varepsilon$.

This lemma is a consequence of the following proposition along with the upper
and lower bounds we have obtained for $\ell\text{-}\mathrm{\sc IsEdge}$. The
proposition is a calculation involving the parameters that come into play in
Lemma 7.7. We state it on its own, since we will reuse the calculation later
when proving Theorem 2.

######  Proposition 7.8.

For all $\delta,\delta^{\prime},\alpha>0$ and $\ell,m,n,k,d\geq 1$ satisfying
$m\leq dk$ and
$\delta^{\prime}>(\delta+\alpha)d+\delta+\frac{(1+\delta)mn}{k(\ell+1)}$, we
have

$(1+\delta)\left[(\ell+1)(k+m)+mn\right]<(\ell+1)\left[(1+\delta^{\prime})k+(1-\alpha)m\right].$

###### Proof.

The proof is a calculation. We can write

$\displaystyle(1+\delta^{\prime})k-(1+\delta)k$
$\displaystyle=(\delta^{\prime}-\delta)k$
$\displaystyle>\left(\delta+(\delta+\alpha)d+\frac{(1+\delta)mn}{k(\ell+1)}-\delta\right)k$
(Assumption on $\delta^{\prime}$)
$\displaystyle=(\delta+\alpha)dk+\frac{(1+\delta)mn}{\ell+1}$
$\displaystyle\geq(\delta+\alpha)m+\frac{(1+\delta)mn}{\ell+1}$ ($m\leq dk$)
$\displaystyle=(1+\delta)m-(1-\alpha)m+\frac{(1+\delta)mn}{\ell+1}.$

Therefore, rearranging we obtain

$(1+\delta)\left[(\ell+1)(k+m)+mn\right]<(\ell+1)\left[(1+\delta^{\prime})k+(1-\alpha)m\right]$

which completes the proof. ∎

###### Proof of Lemma 7.7.

Given a degree-$d$, $m$-edge, $n$-vertex graph $G$ and parameter $k$, we
choose $\ell=\Theta(n)$ so that
$\delta^{\prime}>(\delta+4\varepsilon)d+\delta+\frac{(1+\delta)mn}{k(\ell+1)}$
and set $s=(\ell+1)(k+m)+mn$. Note that such an $\ell$ exists since
$k=\Theta(n)$ for constant-degree graphs. We now prove the two points
separately.

#### Yes case.

In this case, we have by Theorem 5 that there is a decision tree $T$ computing
$\ell\text{-}\mathrm{\sc IsEdge}:\\{0,1\\}^{n\ell+n}\to\\{0,1\\}$ whose size
satisfies

$|T|\leq(\ell+1)(k+m)+mn=s.$

#### No case.

Let $T$ be a decision tree satisfying
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}}(T,\ell\text{-}\mathrm{\sc
IsEdge})\leq\varepsilon$. Then, using our assumptions on the parameters:

$\displaystyle(1+\delta)s$
$\displaystyle=(1+\delta)\left[(\ell+1)(k+m)+mn\right]$ (Definition of $s$)
$\displaystyle<(\ell+1)\left[(1+\delta^{\prime})k+(1-4\varepsilon)m\right]$
(Proposition 7.8 with $\alpha=4\varepsilon$) $\displaystyle\leq|T|.$ (Lemma
7.3 with $k^{\prime}=(1+\delta^{\prime})k$)

We’ve shown the desired bounds in both the Yes and No cases so the proof is
complete. ∎

Theorem 4 follows in a straightforward way from Lemma 7.7.

###### Proof of Theorem 4.

Let $G$ be a constant degree-$d$, $n$-vertex graph and $k\in\mathds{N}$, a
parameter. Let $\mathcal{A}$ be the algorithm for DT-Learn from the theorem
statement. We’ll use $\mathcal{A}$ to approximate Vertex Cover on $G$.

#### The reduction.

First, we check whether $dk\geq m$. If $dk<m$, our algorithm outputs “No” as
$G$ cannot have a vertex cover of size at most $k$. Otherwise, we proceed
under the assumption that $dk\geq m$. Let $s\in\mathds{N}$ be the quantity
from Lemma 7.7. We will run $\mathcal{A}$ over the distribution
$\ell\text{-}\mathcal{D}_{G}$ and on the function $\ell\text{-}\mathrm{\sc
IsEdge}_{G}:\\{0,1\\}^{N}\to\\{0,1\\}$ where $\ell$ is as in Lemma 7.7. Note
that $N=n\ell+n=O(n^{2})$ and $s=O(n^{2})=O(N)$. See Figure 3 for the exact
procedure we run.

$\textsc{Vertex Cover}(k,(1+\delta^{\prime})\cdot k)$: Given: $G$, an $m$-edge
degree-$d$ graph over $n$ vertices and $k\in\mathds{N}$ Run: DT-
Learn$(s,(1+\delta)\cdot s,\varepsilon)$ for $t(N,1/\varepsilon)$ time steps
providing the learner with – queries: return $\ell\text{-}{\mathrm{\mathrm{\sc
IsEdge}}}(v^{(0)},\ldots,v^{(\ell)})$ for a query
$(v^{(0)},\ldots,v^{(\ell)})\in\\{0,1\\}^{N}$; and – random samples: return
$(\bm{v}^{(0)},\ldots,\bm{v}^{(\ell)})\sim\ell\text{-}\mathcal{D}_{G}$ for a
random sample. $T_{\text{hyp}}\leftarrow$ decision tree output of the learner
$\varepsilon_{\text{hyp}}\leftarrow\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}}(T_{\text{hyp}},\ell\text{-}{\mathrm{\mathrm{\sc
IsEdge}}})$ Output: Yes if and only if $|T_{\text{hyp}}|\leq(1+\delta)\cdot s$
and $\varepsilon_{\text{hyp}}\leq\varepsilon$ Figure 3: Using an algorithm for
DT-Learn to solve Vertex Cover.

#### Runtime.

Any query to $\ell\text{-}{\mathrm{\mathrm{\sc IsEdge}}}$ can be answered in
$O(N)$ time. Similarly, a random sample can be obtained in $O(N)$ time. The
algorithm uses $O(N\cdot t(N,1/\varepsilon))$ time to run DT-Learn. Finally,
computing
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}}(T_{\text{hyp}},\ell\text{-}{\mathrm{\mathrm{\sc
IsEdge}}})$ takes $O(N^{2})$. Since $t(N,1/\varepsilon)\geq N$, the overall
runtime is $O(N\cdot t(N,1/\varepsilon))=O(n^{2}t(n^{2},1/\varepsilon))$.

#### Correctness.

Correctness follows from Lemma 7.7. Specifically, in the Yes case, if $G$ has
a vertex cover of size at most $k$, then there is a decision tree of size at
most $s$ computing $\ell\text{-}{\mathrm{\mathrm{\sc IsEdge}}}$. Therefore, by
the guarantees of DT-Learn, we have $|T_{\text{hyp}}|\leq(1+\delta)\cdot s$
and $\varepsilon_{\text{hyp}}\leq\varepsilon$ and our algorithm correctly
outputs “Yes”.

In the No case, every vertex cover of $G$ has size at least
$(1+\delta^{\prime})k$. If $\varepsilon_{\text{hyp}}>\varepsilon$ then our
algorithm for Vertex Cover correctly outputs “No”. Otherwise, assume that
$\varepsilon_{\text{hyp}}\leq\varepsilon$. Then, Lemma 7.7 ensures that
$(1+\delta)s<|T_{\text{hyp}}|$ and so our algorithm correctly outputs “No” in
this case as well. This completes the proof. ∎

##  8 Patching up a decision tree for $f^{\oplus r}$: Proof of Lemma 3.5

The following lemma recovers Lemma 3.5 by setting $D=\\{0,1\\}^{n}$.

######  Lemma 8.1 (XOR-ed version of patchup lemma, formal statement of Lemma
3.5).

Let $T$ be a decision tree and $f:D\to\\{0,1\\}$ be a nonconstant function for
$D\subseteq\\{0,1\\}^{n}$, then

$\mathrm{DT}(f^{\oplus r})\leq|T|+2^{r}\sum_{\begin{subarray}{c}x\in
f^{-1}(1)^{r}\\\ f_{\pi(x)}^{\oplus r}\textnormal{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(f_{\pi(x)},x^{(i)})\\}.$

For the lemma, we require the following generalization of a result from
[Sav02]. Savický proved that for functions $f_{1}:\\{0,1\\}^{n}\to\\{0,1\\}$
and $f_{2}:\\{0,1\\}^{n}\to\\{0,1\\}$, it holds that $\mathrm{DT}(f_{1}\oplus
f_{2})\geq\mathrm{DT}(f_{1})\cdot\mathrm{DT}(f_{2})$ [Sav02, Lemma 2.1]. We
will use the following analogous statement for partial functions.

######  Theorem 6 (Generalization of Savický [Sav02]).

Let $f^{(1)},\ldots,f^{(r)}$ be functions, $f^{(i)}:D^{(i)}\to\\{0,1\\}$ with
$D^{(i)}\subseteq\\{0,1\\}^{n^{(i)}}$ for each $i=1,\ldots,r$. Then,

$\mathrm{DT}(f^{(1)}\oplus\cdots\oplus
f^{(r)})=\prod_{i=1}^{r}\mathrm{DT}(f^{(i)}).$

$\cdots$$\cdots$$\cdots$$\cdots$$T^{(1)}$$T^{(2)}$$T^{(2)}$$T^{(r)}$$T^{(r)}$$T^{(r)}$size
$\mathrm{DT}(f^{(1)})$

Figure 4: Illustration of a stacked decision tree for a function
$f^{(1)}\oplus\cdots\oplus f^{(r)}$. For an input
$x=(x^{(1)},\ldots,x^{(r)})$, the decision tree sequentially computes
$f^{(i)}(x^{(i)})$ for each $i=1,\ldots,r$ using a decision tree $T^{(i)}$ of
size $\mathrm{DT}(f^{(i)})$ for $f^{(i)}$. Then at the leaf it outputs
$f^{(1)}(x^{(1)})\oplus\cdots\oplus f^{(r)}(x^{(r)})$. The overall size of the
decision tree is $\prod_{i=1}^{r}\mathrm{DT}(f^{(i)})$.

###### Proof.

First, the upper bound $\mathrm{DT}(f^{(1)}\oplus\cdots\oplus
f^{(r)})\leq\prod_{i=1}^{r}\mathrm{DT}(f^{(i)})$ follows by considering the
decision tree for $f^{(1)}\oplus\cdots\oplus f^{(r)}$ which sequentially
computes $f^{(i)}(x)$ for each $i=1,\ldots,r$ using a decision tree of size
$\mathrm{DT}(f^{(i)})$. See Figure 4 for an illustration of this decision
tree.

The lower bound is by induction on $\sum_{i\in[r]}n^{(i)}$, the total number
of input variables. In the base case, $n=0$ and the bound is trivially true:
the constant function requires a decision tree of size $1$. For the inductive
step, let $T$ be a decision tree for $f^{(1)}\oplus\cdots\oplus f^{(r)}$ of
size $\mathrm{DT}(f^{(1)}\oplus\cdots\oplus f^{(r)})$, and let $x_{j}$ be the
variable queried at the root. Assume without loss of generality that $x_{j}$
belongs to $f^{(1)}$. The subfunctions computed at the left and right branches
of the root of $T$ are $f^{(1)}_{x_{j}\leftarrow 0}\oplus\cdots\oplus f^{(r)}$
and $f^{(1)}_{x_{j}\leftarrow 1}\oplus\cdots\oplus f^{(r)}$, respectively.
Each is a function on $\left(\sum_{i\in[r]}n^{(i)}\right)-1$ many variables
and so we can apply the inductive hypothesis. Therefore:

$\displaystyle\mathrm{DT}(f^{(1)}\oplus\cdots\oplus f^{(r)})$
$\displaystyle=|T|$ $\displaystyle\geq\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
0}\oplus\cdots\oplus f^{(r)})+\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
1}\oplus\cdots\oplus f^{(r)})$ (Root of $T$ is $x_{j}^{(1)}$)
$\displaystyle\geq\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
0})\prod_{i=2}^{r}\mathrm{DT}(f^{(i)})+\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
1})\prod_{i=2}^{r}\mathrm{DT}(f^{(i)})$ (Inductive hypothesis)
$\displaystyle=\left(\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
0})+\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
1})\right)\prod_{i=2}^{r}\mathrm{DT}(f^{(i)})$
$\displaystyle\geq\prod_{i=1}^{r}\mathrm{DT}(f^{(i)})$

where the last step follows from the fact that
$\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow 0})+\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
1})\geq\mathrm{DT}(f^{(1)})$. Indeed, one can construct a decision tree for
$f^{(1)}$ of size $\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow
0})+\mathrm{DT}(f^{(1)}_{x_{j}\leftarrow 1})$ by querying $x_{j}$ at the root
and on the left branch placing a tree for $f^{(1)}_{x_{j}\leftarrow 0}$ and on
the right branch placing a tree for $f^{(1)}_{x_{j}\leftarrow 1}$. ∎

###### Proof of Lemma 8.1.

Let $\Pi$ denote the set of paths. For each path $\pi\in\Pi$, we write
$\pi^{(i)}$ for $i\in[r]$ to denote the part of $\pi$ corresponding to the
$i$th block of input variables. This way, the restricted function
$f_{\pi}^{\oplus r}$ corresponds to the function
$f_{\pi^{(1)}}\oplus\cdots\oplus f_{\pi^{(r)}}$ Then we have

$\displaystyle\mathrm{DT}(f_{\pi}^{\oplus r})$
$\displaystyle\leq\sum_{\pi\in\Pi}\mathrm{DT}(f_{\pi}^{\oplus r})$
$\displaystyle=\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus r}\text{
is constant}\end{subarray}}\mathrm{DT}(f_{\pi}^{\oplus
r})+\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus r}\text{ is
nonconstant}\end{subarray}}\mathrm{DT}(f_{\pi}^{\oplus r})$
$\displaystyle=|T|+\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus
r}\text{ is nonconstant}\end{subarray}}\mathrm{DT}(f_{\pi}^{\oplus r})$
($\mathrm{DT}(f_{\pi}^{\oplus r})=1$ when $f_{\pi}^{\oplus r}$ is constant)
$\displaystyle=|T|+\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus
r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\mathrm{DT}(f_{\pi^{(i)}})$ (Theorem
6) $\displaystyle\leq|T|+\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus
r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\left(1+\sum_{x:f_{\pi^{(i)}}(x)=1}\mathrm{Cert}(f_{\pi^{(i)}},x)\right)$
(5.1)

We use the fact that $1+a\leq 2\max\\{1,a\\}$ for all $a\in\mathds{R}$ to
rewrite the above in a simpler form, while suffering a factor of $2^{r}$:

$\displaystyle|T|+$ $\displaystyle\sum_{\begin{subarray}{c}\pi\in\Pi\\\
f_{\pi}^{\oplus r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\left(1+\sum_{x:f_{\pi^{(i)}}(x)=1}\mathrm{Cert}(f_{\pi^{(i)}},x)\right)$
$\displaystyle\leq|T|+\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus
r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\left(2\max\\{1,\sum_{x:f_{\pi^{(i)}}(x)=1}\mathrm{Cert}(f_{\pi^{(i)}},x)\\}\right)$
$\displaystyle\leq|T|+2^{r}\sum_{\begin{subarray}{c}\pi\in\Pi\\\
f_{\pi}^{\oplus r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\left(\sum_{x:f_{\pi^{(i)}}(x)=1}\max\\{1,\mathrm{Cert}(f_{\pi^{(i)}},x)\\}\right)$
$\displaystyle=|T|+2^{r}\sum_{\begin{subarray}{c}\pi\in\Pi\\\ f_{\pi}^{\oplus
r}\text{ is
nonconstant}\end{subarray}}\sum_{x^{(1)}:f_{\pi^{(1)}}(x^{(1)})=1}\cdots\sum_{x^{(r)}:f_{\pi^{(r)}}(x^{(r)})=1}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(f_{\pi^{(i)}},x^{(i)})\\}$
$\displaystyle=|T|+2^{r}\sum_{\begin{subarray}{c}x\in f^{-1}(1)^{r}\\\
f_{\pi(x)}^{\oplus r}\textnormal{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(f_{\pi^{(i)}},x^{(i)})\\}$

where the last equality follows from the fact that $\Pi$ partitions the input
space and so for every $x\in f^{-1}(1)^{r}$ there is exactly one path
$\pi\in\Pi$ such that $f_{\pi^{(i)}}(x^{(i)})=1$ for all $i\in[r]$. ∎

##  9 Hard distribution lemma for $f^{\oplus r}$: Proof of Lemma 3.6

The following lemma recovers Lemma 3.6 by setting $D=\\{0,1\\}^{n}$.

######  Lemma 9.1 (Hard distribution lemma for $f^{\oplus r}$).

Let $T$ be a decision tree, $f:D\to\\{0,1\\}$ be a nonconstant function and
let $C\subseteq f^{-1}(1)$. There is a distribution $\mathcal{D}$ over the
inputs in $C$ and their sensitive neighbors such that for all $r\geq 1$,

$\mathrm{error}_{\mathcal{D}^{\otimes r}}(T,f^{\oplus
r})\geq\left(\frac{1}{2|C|\mathrm{Sens}(f)}\right)^{r}\sum_{\begin{subarray}{c}x\in
C^{r}\\\ \mathrm{Sens}(f_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Sens}(f_{\pi(x)}^{(i)},x^{(i)})\\}.$

First, we prove the following claim.

######  Claim 9.2 (Error of $f^{\oplus r}$ conditioned on an input).

Let $T$ be a decision tree, $r\geq 1$, $f:D\to\\{0,1\\}$ be a nonconstant
function, $x\in f^{-1}(1)^{r}$, $\mathcal{D}$ be the canonical hard
distribution, and $\pi$ be the path followed by $x$ in $T$ and assume that
$\mathrm{Sens}(f_{\pi(x)}^{\oplus r},x)\neq\varnothing$, then

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}[f^{\oplus r}(\bm{z})\neq T(\bm{z})\mid\text{ first sampling }x]\geq
2^{-r}\prod_{i=1}^{r}\frac{\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}}{\max\\{1,|\mathrm{Sens}(f^{(i)},x^{(i)})|\\}}.$

###### Proof.

Let $y\in\mathrm{Sens}(f_{\pi}^{\oplus r},x)$ and let $j\in[r]$ be such that
$y^{(j)}\in\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})$. Since $f^{\oplus r}(y)\neq
f^{\oplus r}(x)$, we have

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}$ $\displaystyle[f^{\oplus r}(\bm{z})\neq T(\bm{z})\mid\text{ first
sampling }x]$
$\displaystyle\geq\min\big{\\{}\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}[\bm{z}=x\mid\text{ first sampling }x],$
$\displaystyle\qquad\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}[\bm{z}=(x^{(1)},...,y,...,x^{(r)})\text{ for
}y\in\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})\mid\text{ first sampling
}x]\big{\\}}$ (Either $x$ or $(x^{(1)},...,y,...,x^{(r)})$ makes an error)
$\displaystyle=\min\left\\{2^{-r},2^{-(r-1)}\frac{|\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})|}{|\mathrm{Sens}(f^{(j)},x^{(j)})|}\right\\}$
(Definition of $\mathcal{D}^{\otimes r}$) $\displaystyle\geq
2^{-r}\frac{|\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})|}{|\mathrm{Sens}(f^{(j)},x^{(j)})|}$
$\displaystyle\geq
2^{-r}\frac{|\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})|}{|\mathrm{Sens}(f^{(j)},x^{(j)})|}\cdot\prod_{i\in[r]\setminus\\{j\\}}\frac{\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}}{\max\\{|\mathrm{Sens}(f^{(i)},x^{(i)})|\\}}$
(${\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}}\leq\max\\{1,|\mathrm{Sens}(f^{(i)},x^{(i)})|\\}$
for all $i$)
$\displaystyle=2^{-r}\prod_{i=1}^{r}\frac{\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}}{\max\\{1,|\mathrm{Sens}(f^{(i)},x^{(i)})|\\}}.$
($|\mathrm{Sens}(f_{\pi}^{(j)},x^{(j)})|\neq 0$ by assumption)

∎

We can now prove the main result of this section.

###### Proof of Lemma 9.1.

As in the case of Lemma 6.2, we assume without loss of generality that
$C=f^{-1}(1)$. We lower bound the error as follows

$\displaystyle\varepsilon$
$\displaystyle\geq\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}[T(\bm{z})\neq f^{\oplus r}(\bm{z})]$
$\displaystyle=\sum_{\begin{subarray}{c}x\in C^{r}\\\
\mathrm{Sens}(f_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\frac{1}{|C|^{r}}\cdot\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathcal{D}^{\otimes
r}}[T(\bm{z})\neq f^{\oplus r}(\bm{z})\mid\text{ first sampling }x\text{ from
}C^{r}]$ $\displaystyle\geq(2|C|)^{-r}\sum_{\begin{subarray}{c}x\in C^{r}\\\
\mathrm{Sens}(f_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\prod_{i=1}^{r}\frac{\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}}{\max\\{1,|\mathrm{Sens}(f^{(i)},x^{(i)})|\\}}$
(9.2)
$\displaystyle\geq(2|C|\cdot\mathrm{Sens}(f))^{-r}\sum_{\begin{subarray}{c}x\in
C^{r}\\\ \mathrm{Sens}(f_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\prod_{i=1}^{r}\max\\{1,|\mathrm{Sens}(f_{\pi}^{(i)},x^{(i)})|\\}$
($|\mathrm{Sens}(f^{(i)},x^{(i)})|\leq\mathrm{Sens}(f)$)

which completes the proof. ∎

##  10 Hardness of learning via $\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}$

The main theorem of this section is the following reduction from approximating
Vertex Cover to DT-Learn. This reduction enables us to prove Theorems 1 and 2.

######  Theorem 7 (Main reduction from vertex cover to DT-Learn).

For all $r\geq 1$, $\varepsilon<2^{-3r}$, and $A>1$ the following holds. If
there is a time $t(s,1/\varepsilon)$ algorithm for solving DT-Learn$(s,A\cdot
s,\varepsilon)$ on $n$-variable functions with $s=O(n^{r})$, then Vertex Cover
can be $(1+\delta^{\prime})$-approximated on degree-$d$, $n$-vertex graphs in
randomized time $O(rn^{2}\cdot t(n^{2r},1/\varepsilon))$ for any
$\delta^{\prime}>(A^{1/r}-1+\varepsilon^{1/r}\cdot 8)d+A^{1/r}-1$.

The proof largely follows the steps in proving Theorem 4 where the lower bound
is obtained using a combination of Lemmas 9.1 and 8.1.

Before proving this theorem, we establish a few properties of
$\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}$ which will be helpful for our
analysis.

######  Theorem 8 (Decision tree size lower bound for computing
$\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}$).

Let $T$ be a decision tree for $\ell\text{-}\mathrm{\sc IsEdge}_{G}^{\oplus
r}$ with $\ell,r\geq 1$. Let $k$ be the minimum vertex cover size of $G$ and
let $m$ denote the number of edges of $G$. Then, if
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}^{\otimes
r}}(T,\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r})\leq\varepsilon$ for the
canonical hard distribution $\ell\text{-}\mathcal{D}_{G}$, we have

$|T|\geq\big{[}(\ell+1)(k+m)\big{]}^{r}-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}$

###### Proof.

Since $\ell\text{-}\mathrm{\sc IsEdge}$ has $m$ many $1$-inputs over the
dataset $\ell\text{-}D_{G}$ and $\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge})=2(\ell+1)$, we have

$\displaystyle\varepsilon$
$\displaystyle\geq\left(\frac{1}{4m(\ell+1)}\right)^{r}\sum_{\begin{subarray}{c}x\in\ell\text{-}D_{G}^{r}\\\
\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi(x)}^{(i)},x^{(i)})\\}$ (Lemma 9.1)
$\displaystyle=\left(\frac{1}{4m(\ell+1)}\right)^{r}\sum_{\begin{subarray}{c}x\in\ell\text{-}D_{G}^{r}\\\
\mathrm{Sens}(\ell\text{-}\mathrm{\sc IsEdge}_{\pi(x)}^{\oplus
r},x)\neq\varnothing\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi(x)}^{(i)},x^{(i)})\\}$ (Proposition 7.6)
$\displaystyle\geq\left(\frac{1}{4m(\ell+1)}\right)^{r}\sum_{\begin{subarray}{c}x\in\ell\text{-}D_{G}^{r}\\\
\ell\text{-}\mathrm{\sc IsEdge}_{\pi(x)}^{\oplus r}\text{ is
nonconstant}\end{subarray}}\prod_{i=1}^{r}\max\\{1,\mathrm{Cert}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi(x)}^{(i)},x^{(i)})\\}$
$\displaystyle\geq\left(\frac{1}{8m(\ell+1)}\right)^{r}(\mathrm{DT}(\ell\text{-}\mathrm{\sc
IsEdge}^{\oplus r})-|T|).$ (Lemma 8.1)

In this derivation, we used the fact that if an input
$x\in\ell\text{-}D_{G}^{r}$ is such that $\ell\text{-}\mathrm{\sc
IsEdge}_{\pi(x)}^{\oplus r}$ is nonconstant, then it must be the case that
there is some block $i\in[r]$ where the path $\pi$ does not fully restrict the
sensitive coordinates in the edge indicator for block $i$, and therefore it
must also be the case that $\mathrm{Sens}(\ell\text{-}\mathrm{\sc
IsEdge}_{\pi(x)}^{\oplus r},x)\neq\varnothing$. Now, we can rearrange this
lower bound on $\varepsilon$ to obtain:

$\displaystyle|T|$ $\displaystyle\geq\mathrm{DT}(\ell\text{-}\mathrm{\sc
IsEdge}^{\oplus r})-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}$
$\displaystyle=\mathrm{DT}(\ell\text{-}\mathrm{\sc
IsEdge})^{r}-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}$ (Theorem 6)
$\displaystyle\geq\big{[}(\ell+1)(k+m)\big{]}^{r}-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}$
(Lemma 7.4)

which completes the proof. ∎

The following proposition allows us to translate the above lower bound into a
slightly simpler form.

######  Proposition 10.1.

For all $a,b,r>0$ such that $a\geq b$, we have $a^{r}-b^{r}\geq(a-b)^{r}$.

###### Proof.

Since $a\geq b$, we have

$1\geq\left(1-\frac{b}{a}\right)^{r}+\left(\frac{b}{a}\right)^{r}.$

Multiplying both sides of the inequality by $a^{r}$ and rearranging gives the
desired bound. ∎

With Theorems 8 and 10.1, we are able to prove the main technical lemma used
for our reduction.

######  Lemma 10.2 (Main technical lemma for Theorem 7).

For all $\delta,\delta^{\prime},\varepsilon>0$ and $d,k,r\geq 1$, the
following holds. Given a constant degree-$d$ graph $G$ with $m$ edges, $n$
vertices, and parameter $k$, there is a choice of $\ell=\Theta(n)$ and a
polynomial-time computable quantity $s\in\mathds{N}$ such that so long as
$\delta^{\prime}>(\delta+8\varepsilon^{1/r})d+\delta$, $dk\geq m$, and
$\varepsilon<2^{-3r}$ we have:

  * •

Yes case: if $G$ has a vertex cover of size at most $k$, then there is a
decision tree of size at most $s$ which computes $\ell\text{-}\mathrm{\sc
IsEdge}^{\oplus r}:\\{0,1\\}^{r(n\ell+n)}\to\\{0,1\\}$; and

  * •

No case: if every vertex cover of $G$ has size at least
$(1+\delta^{\prime})k$, then $(1+\delta)^{r}s<|T|$ for any decision tree $T$
with $\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}^{\otimes
r}}(T,\ell\text{-}\mathrm{\sc IsEdge})\leq\varepsilon$.

###### Proof.

Given a degree-$d$, $m$-edge, $n$-vertex graph $G$ and parameter $k$, we
choose $\ell=\Theta(n)$ so that
$\delta^{\prime}>(\delta+8\varepsilon^{1/r})d+\delta+\frac{(1+\delta)mn}{k(\ell+1)}$
and set $s=\left[(\ell+1)(k+m)+mn\right]^{r}$. Note that such an $\ell$ exists
since $k=\Theta(n)$ for constant-degree graphs. We now prove the two points
separately.

#### Yes case.

In this case, we have

$\displaystyle\mathrm{DT}(\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r})$
$\displaystyle=\mathrm{DT}(\ell\text{-}\mathrm{\sc IsEdge})^{r}$ (Theorem 6)
$\displaystyle\leq\left[(\ell+1)(k+m)+mn\right]^{r}=s.$ (Theorem 5)

#### No case.

In this case, let $T$ be a decision tree with
$\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}^{\otimes
r}}(T,\ell\text{-}\mathrm{\sc IsEdge})\leq\varepsilon$. Then we have

$\displaystyle(1+\delta)^{r}s$
$\displaystyle=\bigg{[}(1+\delta)[(\ell+1)(k+m)+mn]\bigg{]}^{r}$
$\displaystyle<\left[(\ell+1)(1+\delta^{\prime})k+(\ell+1)(1-8\varepsilon^{1/r})m\right]^{r}$
(Proposition 7.8 with $\alpha=8\varepsilon^{1/r}$)
$\displaystyle\leq\big{[}(\ell+1)(k+m)\big{]}^{r}-\varepsilon\big{[}8m(\ell+1)\big{]}^{r}$
(Proposition 10.1) $\displaystyle\leq|T|.$ (Theorem 8)

We’ve shown the desired bounds in both the Yes and No cases so the proof is
complete. ∎

###### Proof of Theorem 7.

Let $\mathcal{A}$ be the algorithm for DT-Learn from the theorem statement.
Given an $n$-vertex, $m$-edge graph $G$ of constant degree $d$, we’ll use
$\mathcal{A}$ to approximate Vertex Cover on $G$.

#### The reduction.

First, we check whether $dk\geq m$. If $dk<m$, our algorithm outputs “No” as
$G$ cannot have a vertex cover of size at most $k$ (see 4.1). Otherwise, we
proceed under the assumption that $dk\geq m$. Let $s\in\mathds{N}$ be the
quantity from Lemma 10.2. We run $\mathcal{A}$ over the distribution
$\ell\text{-}\mathcal{D}_{G}^{\otimes r}$ and on the function
$\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}:\\{0,1\\}^{N}\to\\{0,1\\}$ where
$\ell$ is as in Lemma 10.2. Note that $N=r\cdot(n\ell+n)=O(rn^{2})$ and
$s=O(n^{2r})$. See Figure 5 for the exact procedure we run.

$\textsc{Vertex Cover}(k,(1+\delta^{\prime})\cdot k)$: Given: $G$, an $m$-edge
degree-$d$ graph over $n$ vertices and $k\in\mathds{N}$ Run: DT-
Learn$(s,A\cdot s,\varepsilon)$ for $t(s,1/\varepsilon)$ time steps providing
the learner with – queries: return $\ell\text{-}{\mathrm{\mathrm{\sc
IsEdge}}}^{\oplus r}(x)$ for a query $x\in\\{0,1\\}^{N}$; and – random
samples: return $\bm{x}\sim\ell\text{-}\mathcal{D}_{G}^{\otimes r}$ for a
random sample. $T_{\text{hyp}}\leftarrow$ decision tree output of the learner
$\varepsilon_{\text{hyp}}\leftarrow\mathrm{error}_{\ell\text{-}\mathcal{D}_{G}^{\otimes
r}}(T_{\text{hyp}},\ell\text{-}{\mathrm{\mathrm{\sc IsEdge}}}^{\oplus r})$
Output: Yes if and only if $|T_{\text{hyp}}|\leq A\cdot s$ and
$\varepsilon_{\text{hyp}}\leq\varepsilon$ Figure 5: Using an algorithm for DT-
Learn on $\ell\text{-}{\mathrm{\mathrm{\sc IsEdge}}}^{\oplus r}$ to solve
Vertex Cover.

#### Runtime.

Any query to $\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}_{G}$ can be answered
in $O(N)$ time. Similarly, a random sample can be obtained in $O(N)$ time. The
algorithm requires time $O(N\cdot t(N^{r},1/\varepsilon))$ to run the learner
and then $O(N^{2})$ time to compute $\mathrm{dist}_{\mathcal{D}^{\otimes
r}}(T,\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}_{G})$. This implies an
overall runtime of $O(N\cdot t(N^{r},1/\varepsilon))=O(rn^{2}\cdot
t(n^{2r},1/\varepsilon))$.

#### Correctness.

If we let $\delta\coloneqq A^{1/r}-1$, then the assumption of the theorem
statement is that $\delta^{\prime}>(\delta+8\varepsilon^{1/r})d+\delta$.
Therefore, we are able to apply Lemma 10.2 from which we deduce correctness.

In the Yes case, if $G$ has a vertex cover of size at most $k$, then there is
a decision tree of size at most $s$ computing $\ell\text{-}\mathrm{\sc
IsEdge}^{\oplus r}_{G}$. So by the guarantees of DT-Learn, our algorithm
correctly outputs “Yes”.

In the No case, every vertex cover of $G$ has size at least
$(1+\delta^{\prime})k$. If $\varepsilon_{\text{hyp}}>\varepsilon$ then our
algorithm for Vertex Cover correctly outputs “No”. Otherwise, assume that
$\varepsilon_{\text{hyp}}\leq\varepsilon$. Then, Lemma 10.2 ensures that
$(1+\delta)^{r}s<|T_{\text{hyp}}|$ and so our algorithm correctly outputs “No”
in this case as well.

∎

######  Remark 10.3 (Why we require such sharp lower bounds in the proof of
Theorem 7).

A key step in the analysis of the correctness of our reduction is Lemma 10.2.
Since our upper bound for $\ell$-$\mathrm{\sc IsEdge}$ is of the form $s^{r}$,
we require an equally strong lower bound of the form $(s^{\prime})^{r}$. A
weaker lower bound $(s^{\prime})^{cr}$ for some $c<1$ would be insufficient,
since the parameter $s$ would no longer separate the Yes and No cases in Lemma
10.2.

###  10.1 Proof of Theorem 2

By Theorem 3, there is a constant $\delta$ such that if Vertex Cover can be
approximated to within a factor of $1+\delta$ in time $t(n)$, then SAT can be
solved in time $t(n\mathrm{polylog}n)$. Given an $n$-vertex graph with
constant degree $d$, the reduction in Theorem 7 produces an instance of DT-
Learn in time $n^{O(r)}$. We choose $A=2^{\Theta(r)}$ in Theorem 7 so that
$\frac{\delta}{2}>(A^{1/r}-1)d+A^{1/r}-1$ and $\varepsilon=2^{-\Theta(r)}$
small enough so that $\frac{\delta}{2}>\varepsilon^{1/r}\cdot 8d$. This
ensures that our reduction from Vertex Cover produces an instance of DT-
Learn$(s,2^{\Theta(r)}\cdot s,2^{-\Theta(r)})$ for $s=n^{O(r)}$. The algorithm
guaranteed by the theorem statement solves DT-Learn$(s,2^{\Theta(r)}\cdot
s,2^{-\Theta(r)})$ in time $t(n^{O(r)},2^{O(r)})$. Therefore, by Theorem 7,
Vertex Cover can be approximated to within a factor of $1+\delta$ in time
$O(rn^{2})\cdot t(n^{O(r)},2^{O(r)})$. The proof is completed by using the
reduction from SAT to approximating Vertex Cover. $\blacksquare$

###  10.2 Proof of Theorem 1

Let $C>1$ be the constant from the theorem statement. Let $r\geq 1$ be a large
enough constant so that the $2^{O(r)}$ term in Theorem 2 is greater than $C$.
In this case, the error parameter $\varepsilon=2^{-\Theta(r)}$ is also a small
constant that depends on $C$. It follows that any polynomial-time algorithm
solving the problem in the theorem statement can solve SAT in time
$\tilde{O}(rn^{2})\cdot\mathrm{poly}(n^{O(r)},2^{O(r)})$ which is polynomial
when $r$ is constant. Therefore, the task is NP-hard. $\blacksquare$

##  11 Decision tree minimization given a subset of inputs

In this section, we show how our results yield new lower bounds for minimizing
decision trees. First, we recall the problem of decision tree minimization
[ZB00, Sie08].

######  Definition 11.1 (Decision tree minimization).

DT-Min$(s,s^{\prime})$ is the following. Given a decision tree $T$ over $n$
variables and parameters $s,s^{\prime}\in\mathds{N}$, distinguish between

  * •

Yes case: there is a size-$s$ decision tree $T^{\prime}$ such that
$T^{\prime}(x)=T(x)$ for all $x\in\\{0,1\\}^{n}$; and

  * •

No case: all decision trees $T^{\prime}$ such that $T^{\prime}(x)=T(x)$ for
all $x\in\\{0,1\\}^{n}$ have size at least $s^{\prime}$.

[Sie08] proves the following hardness results for DT-Min:

######  Theorem 9 (Hardness of approximating DT-Min [Sie08]).

The following hardness results hold for DT-Min:

  * •

for all constants $C>1$, DT-Min$(s,Cs)$ is NP-hard; and

  * •

for all constants $\gamma<1$, there is no quasipolynomial time algorithm for
DT-Min$(s,2^{(\log s)^{\gamma}}\cdot s)$ unless
$\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\mathrm{polylog}(n)})$

We observe that our proof of Theorem 2 recovers Theorem 9 and also strengthens
the hardness results to hold even when the no case in Definition 11.1 is
strengthened to: there is an explicit set of inputs $D$ and an explicit
distribution $\mathcal{D}$ over $D$ such that any decision tree $T^{\prime}$
which agrees with $T$ with probability $1-\varepsilon$ for
$\bm{x}\sim\mathcal{D}$ has size at least $s^{\prime}$. This is a strict
strengthening since any decision tree $T^{\prime}$ such that
$T^{\prime}(x)=T(x)$ for all $x\in\\{0,1\\}^{n}$ also agrees with $T$ over the
distribution $\mathcal{D}$.

######  Theorem 10 (Hardness of approximating DT-Dataset-Min).

Let DT-Dataset-Min$(s,s^{\prime})$ be the variant of DT-Min$(s,s^{\prime})$
where the input includes a subset of inputs $D\subseteq\\{0,1\\}^{n}$, the pmf
of a distribution $\mathcal{D}$ over $D$, and a parameter $\varepsilon$, and
the No case is changed to “all decision trees $T^{\prime}$ such that
$T^{\prime}(\bm{x})=T(\bm{x})$ with probability $1-\varepsilon$ for
$\bm{x}\sim\mathcal{D}$ have size at least $s^{\prime}$.” Then the following
hardness results hold

  * •

for all constants $C>1$ there is a constant $\varepsilon>0$ such that DT-
Dataset-Min$(s,Cs)$ with error parameter $\varepsilon$ is NP-hard; and

  * •

for all constants $\gamma<1$, there is a parameter $\varepsilon=2^{-(\log
s)^{\gamma}}$ such that there is no quasipolynomial time algorithm for DT-
Min$(s,2^{(\log s)^{\gamma}}\cdot s)$ with error parameter $\varepsilon$
unless $\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\mathrm{polylog}(n)})$

###### Proof.

These hardness results follow from the reduction in Theorem 7. Specifically,
we construct a decision tree $T^{\star}$ computing $\ell\text{-}\mathrm{\sc
IsEdge}^{\oplus r}$ over $\\{0,1\\}^{r(n\ell+n)}$. The set of all $n$ vertices
of $G$ trivially forms a vertex cover of $G$. Therefore, we can apply Theorem
5 to obtain a decision tree for $\ell\text{-}\mathrm{\sc IsEdge}$ of size
$(\ell+1)(n+m)+mn$. We can stack $r$ independent copies of this decision tree
as in the proof of Theorem 6 (see Figure 4) to get a decision tree for
$\ell\text{-}\mathrm{\sc IsEdge}^{\oplus r}$ whose size is
$\left[(\ell+1)(n+m)+mn\right]^{r}$. We then choose
$\ell\text{-}D_{G}^{r}=\mathrm{supp}(\ell\text{-}\mathcal{D}_{G}^{\otimes r})$
to be the subset of inputs for the minimization instance. Moreover, it is
straightforward to compute the pmf of the distribution
$\ell\text{-}\mathcal{D}_{G}^{\otimes r}$ and provide this to the algorithm
for DT-Dataset-Min.

Therefore, as in the proof of Theorem 1, $(1+\delta^{\prime})$-approximating
Vertex Cover reduces in polynomial-time to DT-Dataset-Min$(s,Cs)$. This
completes the proof of the first point in the theorem statement.

For the second point, let $\gamma<1$ be given. We choose $r$ large enough so
that $(1+\delta)^{r}>2^{(\log s)^{\gamma}}$ where $s$ and $\delta$ are
parameters from Lemma 10.2. Since $s=O(n^{2r})$, any $r=\mathrm{polylog}n$
satisfying $r^{1-\gamma}\geq\Omega((\log n)^{\gamma})$ is sufficient. For this
choice of $r$, our reduction runs in quasipolynomial-time and reduces
$(1+\delta^{\prime})$-approximating Vertex Cover to DT-Dataset-Min$(s,2^{(\log
s)^{\gamma}}\cdot s)$. Therefore, the proof is complete. ∎

## Acknowledgments

We thank the COLT reviewers for their helpful feedback and suggestions.

The authors are supported by NSF awards 1942123, 2211237, 2224246, a Sloan
Research Fellowship, and a Google Research Scholar Award. Caleb is also
supported by an NDSEG Fellowship, and Carmen by a Stanford Computer Science
Distinguished Fellowship and an NSF Graduate Research 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.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  J. ACM, 45(3):501–555, may 1998.
  * [Ang] Dana Angluin.  Remarks on the difficulty of finding a minimal disjunctive normal form for boolean functions.  Unpublished Manuscript.
  * [Ang88] Dana Angluin.  Queries and concept learning.  Machine learning, 2:319–342, 1988.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  J. ACM, 45(1):70–122, jan 1998.
  * [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.
  * [BDK18] Shalev Ben-David and Robin Kothari.  Randomized query complexity of sabotaged and composed functions.  Theory of Computing, 14(5):1–27, 2018.
  * [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.
  * [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.
  * [Blu92] Avrim Blum.  Rank-$r$ decision trees are a subclass of $r$-decision lists.  Inform. Process. Lett., 42(4):183–185, 1992.
  * [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.
  * [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.
  * [Dru12] Andrew Drucker.  Improved direct product theorems for randomized query complexity.  computational complexity, 21(2):197–244, 2012.
  * [DS05] Irit Dinur and Samuel Safra.  On the hardness of approximating minimum vertex cover.  Annals of mathematics, pages 439–485, 2005.
  * [EH89] Andrzej Ehrenfeucht and David Haussler.  Learning decision trees from random examples.  Information and Computation, 82(3):231–246, 1989.
  * [Fel06] Vitaly Feldman.  Hardness of approximate two-level logic minimization and pac learning with membership queries.  In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 363–372, 2006.
  * [Fel16] Vitaly Feldman.  Hardness of proper learning.  In Encyclopedia of Algorithms, pages 897–900. Springer New York, NY, 2016.
  * [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.
  * [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.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  J. ACM, 48(4):798–859, jul 2001.
  * [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.
  * [IRW94] Russell Impagliazzo, Ran Raz, and Avi Wigderson.  A direct product theorem.  In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, pages 88–96, 1994.
  * [JKS10] Rahul Jain, Hartmut Klauck, and Miklos Santha.  Optimal direct sum results for deterministic and randomized decision tree complexity.  Information Processing Letters, 110(20):893–897, 2010.
  * [JS06] Jeffrey C. Jackson and Rocco A. Servedio.  On learning random dnf formulas under the uniform distribution.  Theory of Computing, 2(8):147–172, 2006.
  * [KM93] Eyal Kushilevitz and Yishay Mansour.  Learning decision trees using the Fourier spectrum.  SIAM Journal on Computing, 22(6):1331–1348, December 1993.
  * [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.
  * [KŠdW07] Hartmut Klauck, Robert Špalek, and Ronald de Wolf.  Quantum and classical strong direct product theorems and optimal time-space tradeoffs.  SIAM Journal on Computing, 36(5):1472–1493, 2007.  Preliminary version in FOCS 2004.
  * [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.
  * [KST23a] Caleb Koch, Carmen Strassle, and Li-Yang Tan.  Properly learning decision trees with queries is NP-hard.  In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2383–2407, 2023.
  * [KST23b] Caleb Koch, Carmen Strassle, and Li-Yang Tan.  Superpolynomial lower bounds for decision tree learning and testing.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1962–1994, 2023.
  * [MR02] Dinesh Mehta and Vijay Raghavan.  Decision tree approximations of boolean functions.  Theoretical Computer Science, 270(1-2):609–623, 2002.
  * [NRS94] Noam Nisan, Steven Rudich, and Michael Saks.  Products and help bits in decision trees.  In Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 318–329, 1994.
  * [OS07] Ryan O’Donnell and Rocco Servedio.  Learning monotone decision trees in polynomial time.  SIAM Journal on Computing, 37(3):827–844, 2007.
  * [PV88] Leonard Pitt and Leslie G Valiant.  Computational limitations on learning from examples.  Journal of the ACM (JACM), 35(4):965–984, 1988.
  * [PY91] Christos H. Papadimitriou and Mihalis Yannakakis.  Optimization, approximation, and complexity classes.  Journal of Computer and System Sciences, 43(3):425–440, 1991.
  * [RCC+22] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong.  Interpretable machine learning: Fundamental principles and 10 grand challenges.  Statistics Surveys, 16:1 – 85, 2022.
  * [Riv87] Ronald Rivest.  Learning decision lists.  Machine learning, 2(3):229–246, 1987.
  * [Sav02] Petr Savickỳ.  On determinism versus unambiquous nondeterminism for decision trees.  In Electronic Colloquium on Computational Complexity (ECCC), volume 9, 2002.
  * [Sha04] Ronen Shaltiel.  Towards proving strong direct product theorems.  Computational Complexity, 12(1/2):1–22, 2004.
  * [Sie08] Detlef Sieling.  Minimization of decision trees is hard to approximate.  Journal of Computer and System Sciences, 74(3):394–403, 2008.
  * [Val84] Leslie Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [Val85] Leslie G Valiant.  Learning disjunction of conjunctions.  In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI), pages 560–566, 1985.
  * [ZB00] Hans Zantema and Hans Bodlaender.  Finding small equivalent decision trees is hard.  International Journal of Foundations of Computer Science, 11(2):343–354, 2000.