1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément L. Canonne, Erik Waingarten
In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the unifo…
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…
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…