Computational
complexity theory and its connections to algorithms, combinatorics, and
mathematical logic. I'm particularly interested in unconditional
computational lower bounds and their applications.

Publication
and Preprints.

An averagecase lower bound against ACC (with Ruiwen Chen and
Rahul Santhanam). [ ECCC ]
Submitted.

On monotone circuits with local oracles and clique lower bounds (with
Jan Krajicek). [ arXiv ]
Submitted.
 Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness (with Rahul Santhanam). [ arXiv ] [ slides ] Computational Complexity Conference (CCC), 2017.
 Pseudodeterministic constructions in subexponential time (with Rahul Santhanam). [ ECCC ] [ slides ] Symposium on Theory of Computing (STOC), 2017.  Addition is exponentially harder than counting for shallow monotone circuits (with Xi Chen and Rocco Servedio). [ arXiv ] [ slides ] Symposium on Theory of Computing (STOC), 2017.  Unprovability of circuit upper bounds in Cook's theory PV (with Jan Krajicek). [ arXiv ] [ slides ] Logical Methods in Computer Science, Volume 13, Issue 1, 2017.  ErdosKoRado for random hypergraphs: asymptotics and stability (with Marcelo Gauy and Hiep Han). [ arXiv ] Combinatorics, Probability and Computing, 26(3), 406422, 2017.  Nearoptimal smalldepth lower bounds for small distance connecticity (with Xi Chen, Rocco Servedio, and LiYang Tan). [ arXiv ] Symposium on Theory of Computing (STOC), 2016.  An algebraic formulation of the graph reconstruction conjecture (with Bhalchandra Thatte). [ arXiv ] J. Graph Theory, 81: 351363, 2016.  On the monotone complexity of the satisfiability problem. [ Chapter 3  Phd Thesis ] Manuscript, 2015.  Learning circuits with few negations. (with Eric Blais, Clement Canonne, Rocco Servedio, and LiYang Tan). [ ECCC ] International Workshop on Randomization and Computation (RANDOM), 2015.  Majority is incompressible by AC[p] circuits (with Rahul Santhanam). [ ECCC ] [ slides ] Conference on Computational Complexity (CCC), 2015.  The power of negations in cryptography (with Siyao Guo, Tal Malkin, and Alon Rosen). [ ePrint ] [ slides ] Theory of Cryptography Conference (TCC), 2015.  A simple algorithmic explanation for the concentration of measure phenomenon. [ note ] Manuscript (not intended for publication), 2014.  Algorithms versus Circuit lower bounds. [ ECCC ] [ slides ] (Survey) Electronic Colloquium on Computational Complexity, 2013.  Constructing hard functions from learning algorithms (with Adam Klivans and Pravesh Kothari). [ ECCC ] [ slides ] Conference on Computational Complexity (CCC), 2013.
[PhD Thesis] Unconditional lower bounds in complexity theory. [ External Link ] Columbia University, 2015. [Master's Thesis] Computational complexity and the P vs. NP problem (In Portuguese). [ External Link ] University of Campinas, 2010.