# Reconstructing decision trees

arXiv: https://arxiv.org/abs/2012.08735 · HTML: https://mlsanity.com/paper/2012.08735/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2020.

## Built on by (most cited first, 1 of 1)

- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)

## Abstract (arXiv)

We give the first sl reconstruction algorithm for decision trees: given queries to a function f that is opt-close to a size-s decision tree, our algorithm provides query access to a decision tree T where: circ T has size S = sO((log s)2/varepsilon3); circ dist(f,T)≤ O(opt)+varepsilon; circ Every query to T is answered with poly((log s)/varepsilon)· log n queries to f and in poly((log s)/varepsilon)· nlog 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.