Title: Adaptive Exact Learning of Decision Trees from Membership Queries,
Abstract: 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(2^{2d})\log n$ queries and Kushilevitz-Mansour in a deterministic
polynomial time algorithm that asks $ 2^{18d+o(d)}\log n$ queries. We improve
the query complexity of both algorithms. We give a randomized polynomial time
algorithm that asks $\tilde O(2^{2d}) + 2^{d}\log n$ queries and a
deterministic polynomial time algorithm that asks $2^{5.83d}+2^{2d+o(d)}\log n$
queries.