8 citations · 18 across the 23 of their papers we have counts for
6 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…
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…
Properly learning monotone functions via local reconstruction
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
We give a -time algorithm for properly learning monotone Boolean functions under the uniform distribution over . Our algorithm is robust to ad…
The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange +1
We study the problem of {\sl certification}: given queries to a function with certificate complexity and an input , output a size- c…