  Decision Tree is a classic formulation of active learning: given $n$
hypotheses with nonnegative weights summing to 1 and a set of tests that each
partition the hypotheses, output a decision tree using the provided tests that
uniquely identifies each hypothesis and has minimum (weighted) average depth.
Previous works showed that the greedy algorithm achieves a $O(\log n)$
approximation ratio for this problem and it is NP-hard beat a $O(\log n)$
approximation, settling the complexity of the problem.
  However, for Uniform Decision Tree, i.e. Decision Tree with uniform weights,
the story is more subtle. The greedy algorithm's $O(\log n)$ approximation
ratio was the best known, but the largest approximation ratio known to be
NP-hard is $4-\varepsilon$. We prove that the greedy algorithm gives a
$O(\frac{\log n}{\log C_{OPT}})$ approximation for Uniform Decision Tree, where
$C_{OPT}$ is the cost of the optimal tree and show this is best possible for
the greedy algorithm. As a corollary, we resolve a conjecture of Kosaraju,
Przytycka, and Borgstrom. Leveraging this result, for all $\alpha\in(0,1)$, we
exhibit a $\frac{9.01}{\alpha}$ approximation algorithm to Uniform Decision
Tree running in subexponential time $2^{\tilde O(n^\alpha)}$. As a corollary,
achieving any super-constant approximation ratio on Uniform Decision Tree is
not NP-hard, assuming the Exponential Time Hypothesis. This work therefore adds
approximating Uniform Decision Tree to a small list of natural problems that
have subexponential time algorithms but no known polynomial time algorithms.
All our results hold for Decision Tree with weights not too far from uniform. A
key technical contribution of our work is showing a connection between greedy
algorithms for Uniform Decision Tree and for Min Sum Set Cover.
