Selected Publications

My group studies the limits of efficient computation. We approach this question from several perspectives, including circuit complexity, proof complexity, pseudorandomness, query complexity, and learning theory.

Quantum speedups require structure or depth

Computational-statistical tradeoffs from NP-hardness

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

Fast decision tree learning solves hard coding-theoretic problems

Properly learning decision trees in almost polynomial time

---

---

All publications