
Sharper bounds on the Fourier concentration of DNFs
In 1992 Mansour proved that every sizes DNF formula is Fourierconcentr...
read it

Properly learning decision trees in almost polynomial time
We give an n^O(loglog n)time membership query algorithm for properly an...
read it

Decision tree heuristics can fail, even in the smoothed setting
Greedy decision tree learning heuristics are mainstays of machine learni...
read it

Learning stochastic decision trees
We give a quasipolynomialtime algorithm for learning stochastic decisio...
read it

Fooling Gaussian PTFs via Local Hyperconcentration
We give a pseudorandom generator that fools degreed polynomial threshol...
read it

On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
read it

Testing and reconstruction via decision trees
We study sublinear and local computation algorithms for decision trees, ...
read it

Estimating decision tree learnability with polylogarithmic sample complexity
We show that topdown decision tree learning heuristics are amenable to ...
read it

Query strategies for priced information, revisited
We consider the problem of designing query strategies for priced informa...
read it

Universal guarantees for decision tree induction via a higherorder splitting criterion
We propose a simple extension of topdown decision tree learning heurist...
read it

Provable guarantees for decision tree induction: the agnostic setting
We give strengthened provable guarantees on the performance of widely em...
read it

The Power of Many Samples in Query Complexity
The randomized query complexity R(f) of a boolean function f{0,1}^n→{0,1...
read it

New lower bounds for Massively Parallel Computation from query complexity
Roughgarden, Vassilvitskii, and Wang (JACM 18) recently introduced a nov...
read it

Constructive derandomization of query algorithms
We give efficient deterministic algorithms for converting randomized que...
read it

Topdown induction of decision trees: rigorous guarantees and inherent limitations
Consider the following heuristic for building a decision tree for a func...
read it

Fooling Polytopes
We give a pseudorandom generator that fools mfacet polytopes over {0,1}...
read it

LubyVeličkovićWigderson revisited: Improved correlation bounds and pseudorandom generators for depthtwo circuits
We study correlation bounds and pseudorandom generators for depthtwo ci...
read it

NonMalleable Codes for SmallDepth Circuits
We construct efficient, unconditional nonmalleable codes that are secur...
read it

Improved pseudorandom generators from pseudorandom multiswitching lemmas
We give the best known pseudorandom generators for two touchstone classe...
read it

Deterministic search for CNF satisfying assignments in almost polynomial time
We consider the fundamental derandomization problem of deterministically...
read it
LiYang Tan
is this you? claim profile