Properly learning decision trees with queries is NP-hard.

Caleb Koch, Carmen Strassle, Li-Yang Tan

Browse the full FOCS paper archive.