Computational complexity theory and its connections to algorithms,
combinatorics and mathematical logic.
I'm particularly interested in unconditional lower bounds.
The power of negations in
cryptography (with S. Guo, T. Malkin, and A. Rosen). [Preprint]
is incompressible by AC^0[p] circuits (with R.
circuits with negations (with
E. Blais, C. Canonne, R. Servedio and L.-Y.
simple algorithmic explanation for the concentration of measure
phenomenon. [Preprint] Erdos-Ko-Rado
for random hypergraphs: asymptotics and stability (with
H. Han). [arXiv:1409.3634] Algorithms
versus circuit lower bounds. [ECCC
formulation of the graph reconstruction conjecture (with
hard functions from
learning algorithms (with A. Klivans and P. Kothari).
TR13-129] Computational complexity and the P vs. NP
problem (in Portuguese). [Master's