Jane Lange

most citedA Query-Optimal Algorithm for Finding Counterfactuals

1 citations · 1 across the 3 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2022★ 1 cited

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 $f : X^{d} \to {0, 1}$ and instance $x^{⋆}$ , our a…

cs.DS2022

Open Problem: Properly learning decision trees in polynomial time?

Guy Blanc, Jane Lange, Mingda Qiao +1

The authors recently gave an $n^{O (l o g l o g n)}$ time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previ…

cs.DS2022

The Query Complexity of Certification

Guy Blanc, Caleb Koch, Jane Lange +1

We study the problem of {\sl certification}: given queries to a function $f : {0, 1}^{n} \to {0, 1}$ with certificate complexity $\leq k$ and an input $x^{⋆}$ , output a size- $k$ c…