On Learning and Testing Decision Tree

Nader H. Bshouty, Catherine A. Haddad-Zaknoon

In this paper, we study learning and testing decision tree of size and depth that are significantly smaller than the number of attributes $n$. Our main result addresses the problem…