Superconstant Inapproximability of Decision Tree Learning

Caleb Koch, Carmen Strassle, Li-Yang Tan

We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothes…