Fetching the paper…
Reading the bibliography…
We prove that it is NP-hard to properly PAC learn decision trees with queries, resolving a longstanding open problem in learning theory (Bshouty 1993; Guijarro-Lavin-Raghavan 1999; Mehta-Raghavan 2002; Feldman 2016).
Universal sorting problem
Leonid A Levin · 1973
Earlier work this paper cites.
Constructing optimal binary decision trees is NP-complete
Laurent Hyafil and Ronald L Rivest · 1976
Earlier work this paper cites.
Computers and Intractability: A Guide to the Theory of NP-Completeness
M. R. Garey and David S. Johnson · 1979
Earlier work this paper cites.
A theory of the learnable
Leslie Valiant · 1984
Earlier work this paper cites.
Learning disjunction of conjunctions
Leslie G Valiant · 1985
Earlier work this paper cites.
Queries and concept learning
Dana Angluin · 1988
Earlier work this paper cites.
Quantifying inductive bias: AI learning algorithms and valiant’s learning framework
David Haussler · 1988
Earlier work this paper cites.
Computational limitations on learning from examples
Leonard Pitt and Leslie G Valiant · 1988
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth · 1989
Earlier work this paper cites.
Learning decision trees from random examples
Andrzej Ehrenfeucht and David Haussler · 1989
Earlier work this paper cites.
Optimization, approximation, and complexity classes
Christos H. Papadimitriou and Mihalis Yannakakis · 1991
Earlier work this paper cites.
Exact learning via the monotone theory
Nader Bshouty · 1993
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
Eyal Kushilevitz and Yishay Mansour · 1993
Earlier work this paper cites.
Learning sparse multivariate polynomials over a field with queries and counterexamples
Robert Schapire and Linda Sellie · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Avirm Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Extracting tree-structured representations of trained networks
Mark Craven and Jude Shavlik · 1995
Earlier work this paper cites.
Born again trees
Leo Breiman and Nong Shang · 1996
Earlier work this paper cites.
Lower bounds on learning decision lists and trees
Thomas Hancock, Tao Jiang, Ming Li, and John Tromp · 1996
Cited alongside, same era.
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998
Cited alongside, same era.
Probabilistic checking of proofs: A new characterization of NP
Sanjeev Arora and Shmuel Safra · 1998
Cited alongside, same era.
Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron · 1998
Cited alongside, same era.
Exact learning when irrelevant variables abound
David Guijarro, Vıctor Lavın, and Vijay Raghavan · 1999
Cited alongside, same era.
On an optimal split tree problem
S Rao Kosaraju, Teresa M Przytycka, and Ryan Borgstrom · 1999
Cited alongside, same era.
Short PCPs with polylog query complexity
Eli Ben-Sasson and Madhu Sudan · 2008
Later among the works it cites.
Minimization of decision trees is hard to approximate
Detlef Sieling · 2008
Later among the works it cites.
Approximating optimal binary decision trees
Micah Adler and Brent Heeringa · 2012
Later among the works it cites.
Truth table minimization of computational models
Netanel Raviv · 2013
Later among the works it cites.
Inapproximability of Combinatorial Optimization Problems
Luca Trevisan · 2014
Later among the works it cites.
Hardness of proper learning
Vitaly Feldman · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Finding small equivalent decision trees is hard
Hans Zantema and Hans Bodlaender · 2000
Cited alongside, same era.
Statistical modeling: The two cultures (with comments and a rejoinder by the author)
Leo Breiman · 2001
Cited alongside, same era.
Decision tree approximations of boolean functions
Dinesh Mehta and Vijay Raghavan · 2002
Cited alongside, same era.
On the proper learning of axis-parallel concepts
Nader H Bshouty and Lynn Burroughs · 2003
Cited alongside, same era.
The complexity of properly learning simple concept classes
Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, and Toniann Pitassi · 2004
Cited alongside, same era.
On the hardness of the minimum height decision tree problem
Eduardo S Laber and Loana Tito Nogueira · 2004
Cited alongside, same era.
Yichen Zhou and Giles Hooker · 2016
Later among the works it cites.
Interpretability via model extraction
Osbert Bastani, Carolyn Kim, and Hamsa Bastani · 2017
Later among the works it cites.
Distilling a neural network into a soft decision tree
Nicholas Frosst and Geoffrey Hinton · 2017
Later among the works it cites.
A genetic algorithm for interpretable model extraction from decision tree ensembles
Gilles Vandewiele, Kiani Lannoye, Olivier Janssens, Femke Ongenae, Filip De Turck, and Sofie Van Hoecke · 2017
Later among the works it cites.
Born-again tree ensembles
Thibaut Vidal and Maximilian Schiffer · 2020
Later among the works it cites.
Decision tree heuristics can fail, even in the smoothed setting
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan · 2021
Later among the works it cites.
Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan · 2022
Later among the works it cites.
Interpretable machine learning: Fundamental principles and 10 grand challenges
Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong · 2022
Later among the works it cites.
Superpolynomial lower bounds for learning monotone classes
Nader H. Bshouty · 2023
Closest in time.
Superpolynomial lower bounds for decision tree learning and testing
Caleb Koch, Carmen Strassle, and Li-Yang Tan · 2023
Closest in time.