We prove that it is NP-hard to properly PAC learn decision trees with
qu...
We prove a strong composition theorem for junta complexity and show how ...
We show how any PAC learning algorithm that works under the uniform
dist...
In the certification problem, the algorithm is given a function f with
c...
We establish new hardness results for decision tree optimization problem...
We investigate the computational efficiency of multitask learning of Boo...
We design an algorithm for finding counterfactuals with strong theoretic...
The authors recently gave an n^O(loglog n) time membership query
algorit...
Using the framework of boosting, we prove that all impurity-based decisi...
We study parallel algorithms for correlation clustering. Each pair among...
We study the complexity of computing majority as a composition of local
...
We study the problem of certification: given queries to a function f :
{...
We study a fundamental question concerning adversarial noise models in
s...
We study the complexity of small-depth Frege proofs and give the first
t...
We consider the problem of explaining the predictions of an arbitrary
bl...
In 1992 Mansour proved that every size-s DNF formula is
Fourier-concentr...
We give an n^O(loglog n)-time membership query algorithm for properly
an...
Greedy decision tree learning heuristics are mainstays of machine learni...
We give a quasipolynomial-time algorithm for learning stochastic decisio...
We give a pseudorandom generator that fools degree-d polynomial threshol...
The Stabbing Planes proof system was introduced to model the reasoning
c...
We study sublinear and local computation algorithms for decision trees,
...
We show that top-down decision tree learning heuristics are amenable to
...
We consider the problem of designing query strategies for priced informa...
We propose a simple extension of top-down decision tree learning heurist...
We give strengthened provable guarantees on the performance of widely
em...
The randomized query complexity R(f) of a boolean function
f{0,1}^n→{0,1...
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a nov...
We give efficient deterministic algorithms for converting randomized que...
Consider the following heuristic for building a decision tree for a func...
We give a pseudorandom generator that fools m-facet polytopes over
{0,1}...
We study correlation bounds and pseudorandom generators for depth-two
ci...
We construct efficient, unconditional non-malleable codes that are secur...
We give the best known pseudorandom generators for two touchstone classe...
We consider the fundamental derandomization problem of deterministically...