J. Jackson and R. Servedio.

Preliminary version appeared in

We consider three natural models of random log-depth decision trees. We give an efficient algorithm that for each of these models learns---as a decision tree---all but an inverse polynomial fraction of such trees using only uniformly distributed random examples.

Postscript or pdf of journal version