Computational complexity theory and its connections to algorithms,
combinatorics and mathematical logic.
I'm mainly interested in unconditional lower bounds.
Majority is incompressible by ACC[p] circuits (with R. Santhanam).
Erdos-Ko-Rado for random hypergraphs: asymptotics and stability (with
Learning circuits with few negations (with
E. Blais, C. Canonne, R. Servedio and L.-Y.
simple algorithmic explanation for the concentration of measure
versus circuit lower bounds. [ECCC
formulation of the graph reconstruction conjecture (with
hard functions from
learning algorithms (with A. Klivans and P. Kothari).