Research Interests

Circuit Complexity  e.g. Lower bounds for boolean circuits [RST]
Proof Complexity   e.g. Lower bounds for propositional proofs [PRST]
Property Testing  e.g. Lower bounds for testing function properties [CSTWX, CDST]
Pseudorandomness  e.g. PRGs and high-dimensional geometry [OST, OSTK]
Learning Theory  e.g. Algorithms and lower bounds for learning decision trees [BLQT, KST]

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.

Selected recent publications

Properly learning decision trees with queries is NP-hard
with Caleb Koch and Carmen Strassle.
FOCS 2023

A strong composition theorem for junta complexity and the boosting of property testers
with Guy Blanc, Caleb Koch, and Carmen Strassle.
FOCS 2023

Lifting uniform learners via distributional decomposition
with Guy Blanc, Jane Lange, and Ali Malik.
STOC 2023


Selected less recent publications

A generalization of the satisfiability coding lemma and its applications
with Milan Mossé and Harry Sha.
SAT 2022
Best paper award
Invited to SAT 2022 special issue

Properly learning decision trees in almost polynomial time
with Guy Blanc, Jane Lange, and Mingda Qiao.
FOCS 2021
Invited to FOCS 2021 special issue
Journal of the ACM, 2022

Fooling Gaussian PTFs via local hyperconcentration
with Ryan O’Donnell and Rocco Servedio, with an appendix by Daniel Kane.
STOC 2020
Journal of the ACM, accepted pending minor revisions

Fooling polytopes
with Ryan O'Donnell and Rocco Servedio.
STOC 2019
Invited to STOC 2019 special issue
Journal of the ACM, 2022

Settling the query complexity of non-adaptive junta testing
with Xi Chen, Rocco Servedio, Erik Waingarten, and Jinyu Xie.
CCC 2017
Best paper award
Invited to the Journal of the ACM

Poly-logarithmic Frege depth lower bounds via an expander switching lemma
with Toniann Pitassi, Benjamin Rossman, and Rocco Servedio.
STOC 2016
Invited to STOC 2016 special issue

An average-case depth hierarchy theorem for Boolean circuits
with Benjamin Rossman and Rocco Servedio.
FOCS 2015
Best paper award
Invited to the Journal of the ACM




Click here for the list of all publications.