Jane Lange | DeepAI

DeepAI AI Chat

Featured Co-authors

Clark Barrett
54 publications
Li-Yang Tan
35 publications
Guy Blanc
24 publications
Ronitt Rubinfeld
23 publications
Mingda Qiao
14 publications
Neha Gupta
12 publications
Yoni Zohar
12 publications
Ying Sheng
10 publications
Ali Malik
8 publications
Sofya Raskhodnikova
8 publications
Arsen Vasilyan
8 publications

∙ 08/28/2023

Local Lipschitz Filters for Bounded-Range Functions

We study local filters for the Lipschitz property of real-valued functio...

0 Jane Lange, et al. ∙

∙ 04/05/2023

Agnostic proper learning of monotone functions: beyond the black-box correction barrier

We give the first agnostic, efficient, proper learning algorithm for mon...

0 Jane Lange, et al. ∙

∙ 03/27/2023

Lifting uniform learners via distributional decomposition

We show how any PAC learning algorithm that works under the uniform dist...

0 Guy Blanc, et al. ∙

∙ 11/04/2022

Certification with an NP Oracle

In the certification problem, the algorithm is given a function f with c...

0 Guy Blanc, et al. ∙

∙ 07/14/2022

A Query-Optimal Algorithm for Finding Counterfactuals

We design an algorithm for finding counterfactuals with strong theoretic...

0 Guy Blanc, et al. ∙

∙ 06/29/2022

Open Problem: Properly learning decision trees in polynomial time?

The authors recently gave an n^O(loglog n) time membership query algorit...

0 Guy Blanc, et al. ∙

∙ 06/17/2022

Popular decision tree algorithms are provably noise tolerant

Using the framework of boosting, we prove that all impurity-based decisi...

0 Guy Blanc, et al. ∙

∙ 04/25/2022

Properly learning monotone functions via local reconstruction

We give a 2^Õ(√(n)/ε)-time algorithm for properly learning monotone Bool...

0 Jane Lange, et al. ∙

∙ 01/19/2022

The Query Complexity of Certification

We study the problem of certification: given queries to a function f : {...

0 Guy Blanc, et al. ∙

∙ 11/19/2021

On the power of adaptivity in statistical adversaries

We study a fundamental question concerning adversarial noise models in s...

0 Guy Blanc, et al. ∙

∙ 11/01/2021

Provably efficient, succinct, and precise explanations

We consider the problem of explaining the predictions of an arbitrary bl...

0 Guy Blanc, et al. ∙

∙ 09/01/2021

Properly learning decision trees in almost polynomial time

We give an n^O(loglog n)-time membership query algorithm for properly an...

0 Guy Blanc, et al. ∙

∙ 07/02/2021

Decision tree heuristics can fail, even in the smoothed setting

Greedy decision tree learning heuristics are mainstays of machine learni...

0 Guy Blanc, et al. ∙

∙ 05/08/2021

Learning stochastic decision trees

We give a quasipolynomial-time algorithm for learning stochastic decisio...

0 Guy Blanc, et al. ∙

∙ 12/16/2020

Testing and reconstruction via decision trees

We study sublinear and local computation algorithms for decision trees, ...

0 Guy Blanc, et al. ∙

∙ 11/03/2020

Estimating decision tree learnability with polylogarithmic sample complexity

We show that top-down decision tree learning heuristics are amenable to ...

0 Guy Blanc, et al. ∙

∙ 10/22/2020

Query strategies for priced information, revisited

We consider the problem of designing query strategies for priced informa...

0 Guy Blanc, et al. ∙

∙ 10/16/2020

Universal guarantees for decision tree induction via a higher-order splitting criterion

We propose a simple extension of top-down decision tree learning heurist...

0 Guy Blanc, et al. ∙

∙ 06/01/2020

Provable guarantees for decision tree induction: the agnostic setting

We give strengthened provable guarantees on the performance of widely em...

0 Guy Blanc, et al. ∙

∙ 04/09/2020

Politeness for the Theory of Algebraic Datatypes

Algebraic datatypes, and among them lists and trees, have attracted a lo...

0 Ying Sheng, et al. ∙

∙ 12/06/2019

Constructive derandomization of query algorithms

We give efficient deterministic algorithms for converting randomized que...

0 Guy Blanc, et al. ∙

∙ 11/18/2019

Top-down induction of decision trees: rigorous guarantees and inherent limitations

Consider the following heuristic for building a decision tree for a func...

0 Guy Blanc, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world