8 citations · 18 across the 23 of their papers we have counts for
6 papers · 1 filter
Reconstructing decision trees
Guy Blanc, Jane Lange, Li-Yang Tan
We give the first {\sl reconstruction algorithm} for decision trees: given queries to a function that is -close to a size- decision tree, our algorithm provide…
Estimating decision tree learnability with polylogarithmic sample complexity
Guy Blanc, Neha Gupta, Jane Lange +1
We show that top-down decision tree learning heuristics are amenable to highly efficient learnability estimation: for monotone target functions, the error of the decision tree hypo…
Query strategies for priced information, revisited
Guy Blanc, Jane Lange, Li-Yang Tan
We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function $f : \{0,1\}^…
Universal guarantees for decision tree induction via a higher-order splitting criterion
Guy Blanc, Neha Gupta, Jane Lange +1
We propose a simple extension of top-down decision tree learning heuristics such as ID3, C4.5, and CART. Our algorithm achieves provable guarantees for all target functions $f: \{-…
Provable guarantees for decision tree induction: the agnostic setting
Guy Blanc, Jane Lange, Li-Yang Tan
We give strengthened provable guarantees on the performance of widely employed and empirically successful {\sl top-down decision tree learning heuristics}. While prior works have f…
Politeness for the Theory of Algebraic Datatypes
Ying Sheng, Yoni Zohar, Christophe Ringeissen +3
Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable versi…