Reconstructing decision trees
  We give the first {\sl reconstruction algorithm} for decision trees: given
queries to a function $f$ that is $\mathrm{opt}$-close to a size-$s$ decision
tree, our algorithm provides query access to a decision tree $T$ where:
  $\circ$ $T$ has size $S = s^{O((\log s)^2/\varepsilon^3)}$;
  $\circ$ $\mathrm{dist}(f,T)\le O(\mathrm{opt})+\varepsilon$;
  $\circ$ Every query to $T$ is answered with $\mathrm{poly}((\log
s)/\varepsilon)\cdot \log n$ queries to $f$ and in $\mathrm{poly}((\log
s)/\varepsilon)\cdot n\log n$ time.
  This yields a {\sl tolerant tester} that distinguishes functions that are
close to size-$s$ decision trees from those that are far from size-$S$ decision
trees. The polylogarithmic dependence on $s$ in the efficiency of our tester is
exponentially smaller than that of existing testers.
  Since decision tree complexity is well known to be related to numerous other
boolean function properties, our results also provide a new algorithms for
reconstructing and testing these properties.
