Superpolynomial lower bounds for decision tree learning and testing
Caleb Koch, Carmen Strassle, Li-Yang Tan · Society for Industrial and Applied Mathematics eBooks · 2023
We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under the randomized exponential time hypothesis, superpolynomial runtime lower bounds for two basic problems: given an explicit representation of a function f and a generator for a distribution D