8 citations · 17 across the 7 of their papers we have counts for
5 papers · 1 filter
Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao +1
We give an -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over . Even in the…
Multiway Online Correlated Selection
Guy Blanc, Moses Charikar
We give a -competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was due to Fahrbach, Huang, Tao, and Za…
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…
Top-down induction of decision trees: rigorous guarantees and inherent limitations
Guy Blanc, Jane Lange, Li-Yang Tan
Consider the following heuristic for building a decision tree for a function . Place the most influential variable of at the root, and recurs…