Adaptive Exact Learning of Decision Trees from Membership Queries

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.