Publications

Polylogarithmic Frege depth lower bounds via an expander switching lemma.
with Toniann Pitassi, Benjamin Rossman, and Rocco Servedio.
STOC 2016. 
Nearoptimal smalldepth lower bounds for small distance connectivity.
with Xi Chen, Igor Oliveira, and Rocco Servedio.
STOC 2016. 
Convergence, unanimity, and disagreement in majority dynamics on unimodular graphs and random graphs.
with Itai Benjamini, Siu On Chan, Ryan O'Donnell, and Omer Tamuz.
Stochastic Processes and their Applications, to appear. 
Algorithmic signaling of features in auction design.
with Shaddin Dughmi, Nicole Immorlica, and Ryan O'Donnell.
SAGT 2015. 
An averagecase depth hierarchy theorem for Boolean circuits.
with Benjamin Rossman and Rocco Servedio.
FOCS 2015.
Best Paper Award at FOCS 2015.
Invited to the Journal of the ACM.See Computational Complexity, ShtetlOptimized, Gödel's Lost Letter and P=NP, Combinatorics and more for discussions of our results. See also Boaz Barak's lecture notes, a Simons Institute research vignette, our invited article in SIGACT News, and a TCS+ talk.

Learning circuits with few negations.
with Eric Blais, Clément Canonne, Igor Oliveira, and Rocco Servedio.
RANDOM 2015. 
Adaptivity helps for testing juntas.
with Rocco Servedio and John Wright.
CCC 2015. 
Boolean monotonicity testing requires (almost) n^{1/2} nonadaptive queries.
with Xi Chen, Anindya De, and Rocco Servedio.
STOC 2015.See also [KhotMinzerSafra '15] for the matching upper bound, and Clément Canonne's open problem regarding adaptivity. 
Approximate resilience, monotonicity, and the complexity of agnostic learning.
with Dana DachmanSoled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.
SODA 2015. 
New algorithms and lower bounds for monotonicity testing.
with Xi Chen and Rocco Servedio.
FOCS 2014.Videos of talks at IAS and FOCS, and scribe notes on the lower bound. See also [ChenDeServedioT '15] for a subsequent improvement of the lower bound. 
On DNF approximators for monotone Boolean functions.
with Eric Blais, Johan Håstad, and Rocco Servedio.
ICALP 2014. 
A composition theorem for parity kill number.
with Ryan O'Donnell, Xiaorui Sun, John Wright, and Yu Zhao.
CCC 2014. 
Hypercontractive inequalities via SOS, and the FranklRödl graph.
with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
SODA 2014.
Discrete Analysis, to appear. 
Learning sums of independent integer random variables.
with Costis Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, and Rocco Servedio.
FOCS 2013.
Invited to Algorithmica Special Issue on Machine Learning. 
On the average sensitivity and density of kCNF formulas.
with Dominik Scheder.
RANDOM 2013. 
A composition theorem for the Fourier EntropyInfluence conjecture.
with Ryan O'Donnell.
ICALP 2013.
See also [WanWrightWu '14] for a new proof of our composition theorem. 
Approximating Boolean functions with depth2 circuits.
with Eric Blais.
CCC 2013.
SIAM Journal on Computing 44(6), pp. 15831600, (2015).See also Gödel's Lost Letter and P=NP for a discussion of this paper, and [BlaisHåstadServedioT '14] for related results. A video of my talk at the Simons Institute. 
Hypercontractivity via the entropy method.
with Eric Blais.
Theory of Computing 9(29), pp. 889896, (2013).
Special issue on Analysis of Boolean Functions. 
New NPhardness results for 3Coloring and 2to1 Label Cover.
with Per Austrin, Ryan O'Donnell, and John Wright.
ACM Transactions on Computation Theory 6(1), Article 2, (2014). 
Attributeefficient learning and weightdegree tradeoffs for
PTFs.
with Rocco Servedio and Justin Thaler.
COLT 2012. 
Noise stable halfspaces are close to very small juntas.
with Ilias Diakonikolas, Ragesh Jaiswal, Rocco Servedio, and Andrew Wan.
Chicago Journal of Theoretical Computer Science, (2015).  Bounding the average
sensitivity and noise sensitivity of PTFs.
with Ilias Diakonikolas, Prasad Raghavendra, and Rocco Servedio.
STOC 2010.
Conference version merged with [HarshaKlivansMeka].
SIAM Journal on Computing 43(1), pp. 231253, (2014). 
A regularity lemma and lowweight approximators for lowdegree PTFs.
with Ilias Diakonikolas, Rocco Servedio, and Andrew Wan.
CCC 2010.
Theory of Computing 10(2), pp. 2753, (2014).  The algebra of equality proofs.
with Aaron Stump.
RTA 2005.
Other writings

The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.
with Benjamin Rossman and Rocco Servedio.
Invited article in SIGACT News 46(4), December 2015 issue.
Overview of [RossmanServedioT '15], with an emphasis on the connections to structural complexity theory. 
Analytic Methods in Concrete Complexity.
Ph.D. Thesis.
Columbia University, 2014. 
2014 Simons Symposium on Discrete Analysis.

Analysis of Boolean Functions.
10lecture minicourse by Ryan O'Donnell.
2012 Barbados workshop on Computational Complexity.
Manuscripts

Discrete isoperimetry via the entropy method.
with Eric Blais and Andrew Wan.