research
∙
07/09/2023
Properly Learning Decision Trees with Queries Is NP-Hard
We prove that it is NP-hard to properly PAC learn decision trees with qu...
share
research
∙
07/08/2023
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
We prove a strong composition theorem for junta complexity and show how ...
research
∙
03/27/2023
Lifting uniform learners via distributional decomposition
We show how any PAC learning algorithm that works under the uniform dist...
research
∙
11/04/2022
Certification with an NP Oracle
In the certification problem, the algorithm is given a function f with c...
research
∙
10/12/2022
Superpolynomial Lower Bounds for Decision Tree Learning and Testing
We establish new hardness results for decision tree optimization problem...
research
∙
09/07/2022
Multitask Learning via Shared Features: Algorithms and Hardness
We investigate the computational efficiency of multitask learning of Boo...
research
∙
07/14/2022
A Query-Optimal Algorithm for Finding Counterfactuals
We design an algorithm for finding counterfactuals with strong theoretic...
research
∙
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...
research
∙
06/17/2022
Popular decision tree algorithms are provably noise tolerant
Using the framework of boosting, we prove that all impurity-based decisi...
research
∙
05/07/2022
Almost 3-Approximate Correlation Clustering in Constant Rounds
We study parallel algorithms for correlation clustering. Each pair among...
research
∙
05/05/2022
The composition complexity of majority
We study the complexity of computing majority as a composition of local ...
research
∙
01/19/2022
The Query Complexity of Certification
We study the problem of certification: given queries to a function f : {...
research
∙
11/19/2021
On the power of adaptivity in statistical adversaries
We study a fundamental question concerning adversarial noise models in s...
research
∙
11/15/2021
Tradeoffs for small-depth Frege proofs
We study the complexity of small-depth Frege proofs and give the first t...
research
∙
11/01/2021
Provably efficient, succinct, and precise explanations
We consider the problem of explaining the predictions of an arbitrary bl...
research
∙
09/09/2021
Sharper bounds on the Fourier concentration of DNFs
In 1992 Mansour proved that every size-s DNF formula is Fourier-concentr...
research
∙
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...
research
∙
07/02/2021
Decision tree heuristics can fail, even in the smoothed setting
Greedy decision tree learning heuristics are mainstays of machine learni...
research
∙
05/08/2021
Learning stochastic decision trees
We give a quasipolynomial-time algorithm for learning stochastic decisio...
research
∙
03/13/2021
Fooling Gaussian PTFs via Local Hyperconcentration
We give a pseudorandom generator that fools degree-d polynomial threshol...
research
∙
02/09/2021
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
research
∙
12/16/2020
Testing and reconstruction via decision trees
We study sublinear and local computation algorithms for decision trees, ...
research
∙
11/03/2020
Estimating decision tree learnability with polylogarithmic sample complexity
We show that top-down decision tree learning heuristics are amenable to ...
research
∙
10/22/2020
Query strategies for priced information, revisited
We consider the problem of designing query strategies for priced informa...
research
∙
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...
research
∙
06/01/2020
Provable guarantees for decision tree induction: the agnostic setting
We give strengthened provable guarantees on the performance of widely em...
research
∙
02/25/2020
The Power of Many Samples in Query Complexity
The randomized query complexity R(f) of a boolean function f{0,1}^n→{0,1...
research
∙
01/05/2020
New lower bounds for Massively Parallel Computation from query complexity
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a nov...
research
∙
12/06/2019
Constructive derandomization of query algorithms
We give efficient deterministic algorithms for converting randomized que...
research
∙
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...
research
∙
08/13/2018
Fooling Polytopes
We give a pseudorandom generator that fools m-facet polytopes over {0,1}...
research
∙
03/12/2018
Luby--Veličković--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
We study correlation bounds and pseudorandom generators for depth-two ci...
research
∙
02/21/2018
Non-Malleable Codes for Small-Depth Circuits
We construct efficient, unconditional non-malleable codes that are secur...
research
∙
01/10/2018
Improved pseudorandom generators from pseudorandom multi-switching lemmas
We give the best known pseudorandom generators for two touchstone classe...
research
∙
01/10/2018