37 citations · 101 across the 43 of their papers we have counts for
9 papers · 1 filter
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange +2
In the certification problem, the algorithm is given a function with certificate complexity and an input , and the goal is to find a certificate of size $\le \text…
Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, Li-Yang Tan
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 randomized ETH, su…
Multitask Learning via Shared Features: Algorithms and Hardness
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan +2
We investigate the computational efficiency of multitask learning of Boolean functions over the -dimensional hypercube, that are related by means of a feature representation of…
A Query-Optimal Algorithm for Finding Counterfactuals
Guy Blanc, Caleb Koch, Jane Lange +1
We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model and instance , our a…
Open Problem: Properly learning decision trees in polynomial time?
Guy Blanc, Jane Lange, Mingda Qiao +1
The authors recently gave an time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previ…
Popular decision tree algorithms are provably noise tolerant
Guy Blanc, Jane Lange, Ali Malik +1
Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guara…