# Adaptive Exact Learning of Decision Trees from Membership Queries

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2019.

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

- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [On Learning and Testing Decision Tree](https://mlsanity.com/paper/2108.04587/) (2021)
- [Actively Learning Halfspaces without Synthetic Data](https://mlsanity.com/paper/2509.20848/) (2025)
- [Optimal Quantum-Classical Separations for Exact Learning](https://mlsanity.com/paper/2609.38073/) (2026)

## Abstract (arXiv)

In this paper we study the adaptive learnability of decision trees of depth at most d from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks tilde O(22d)log n queries and Kushilevitz-Mansour in a deterministic polynomial time algorithm that asks  218d+o(d)log n queries. We improve the query complexity of both algorithms. We give a randomized polynomial time algorithm that asks tilde O(22d) + 2dlog n queries and a deterministic polynomial time algorithm that asks 25.83d+22d+o(d)log n queries.