Research Interests

I am broadly interested in complexity theory and its adjacent areas.

Circuit Complexity  e.g. Lower bounds for boolean circuits  [HRST JACM '17]
Proof Complexity   e.g. Lower bounds for propositional proofs  [PRST STOC '16, PRT FOCS '21]
Property Testing  e.g. Testing monotonicity and juntas  [CST FOCS '14, CDST STOC '15, CSTWX JACM '18]
Pseudorandomness  e.g. PRGs and high-dimensional geometry  [OSTK STOC '20, OST JACM '22]
Learning Theory  e.g. Decision tree learning  [BLQT JACM '22, KST FOCS '23, KST FOCS '24]
Hardness Amplification  e.g. Relationships with boosting  [BKST FOCS '23, BHKT FOCS '24]

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
with Guy Blanc, Alexandre Hayderi, and Caleb Koch.
FOCS 2024
Invited to FOCS 2024 special issue

Fast decision tree learning solves hard coding-theoretic problems
with Caleb Koch and Carmen Strassle.
FOCS 2024

A strong direct sum theorem for distributional query complexity
with Guy Blanc, Caleb Koch, and Carmen Strassle.
CCC 2024
Invited to CCC 2024 special issue

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

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

On the power and limitations of branch and cut
with Noah Fleming, Mika Göös, Russell Impagliazzo, Toni Pitassi, Robert Robere, and Avi Wigderson.
CCC 2021
Invited to CCC 2021 special issue

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.