37 citations · 101 across the 43 of their papers we have counts for
4 papers · 2 filters
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…
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\}^…
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…
New lower bounds for Massively Parallel Computation from query complexity
Moses Charikar, Weiyun Ma, Li-Yang Tan
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a novel framework for proving lower bounds for Massively Parallel Computation using techniques from boolean funct…