Research Interests

A central theme in my work is the development of techniques to understand boolean function complexity, and the application of these techniques to a range of areas in theoretical computer science.

My work has been recognized with best paper awards at FOCS, CCC, and SAT, an Alfred P. Sloan Fellowship, an NSF CAREER Award, and a Google Research Scholar Award.

Selected recent publications

The sample complexity of smooth boosting and the tightness of the hardcore theorem

Fast decision tree learning solves hard coding-theoretic problems

A strong direct sum theorem for distributional query complexity

Properly learning decision trees with queries is NP-hard

A strong composition theorem for junta complexity and the boosting of property testers

Lifting uniform learners via distributional decomposition

Selected less recent publications

A generalization of the satisfiability coding lemma and its applications

Properly learning decision trees in almost polynomial time

Fooling Gaussian PTFs via local hyperconcentration

Fooling polytopes

Settling the query complexity of non-adaptive junta testing

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

An average-case depth hierarchy theorem for Boolean circuits