Reconstructing decision trees
This work provides a new method for reconstructing and testing properties of boolean functions, which is significant for researchers working on decision tree complexity and related boolean function properties.
This paper presents the first reconstruction algorithm for decision trees, which, given a function f that is opt-close to a size-s decision tree, provides query access to a decision tree T of size S = s^O((log s)^2/ε^3) such that dist(f,T) ≤ O(opt)+ε. This algorithm also yields a tolerant tester with polylogarithmic dependence on s, which is exponentially smaller than existing testers.
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.