Review for NeurIPS paper: Universal guarantees for decision tree induction via a higher-order splitting criterion

Summary and Contributions: This paper considers the problem of learning decision trees. You are given samples from a function f on the Boolean cube that is known to be computed by a size s decision tree. The goal is to produce a hypothesis h that is also a small decision tree and is close to f. It was known that simply looking at correlations is not a good idea, simple functions like parity of a few variables would defeat this algorithm. Indeed, I don't think there was any known algorithm that was guaranteed to return a "decision tree" of small size. This paper presents an algorithm of this type.