Publications

New algorithms and lower bounds for monotonicity testing.

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. [Yu's slides] 
Hypercontractive inequalities via SOS, and the FranklRödl graph.
with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
SODA 2014. 
Learning sums of independent integer random variables.
with Costis Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, and Rocco Servedio.
FOCS 2013. [video, slides]
Blog post about our work: MIT Theory student blog. 
On the average sensitivity and density of kCNF formulas.
with Dominik Scheder.
RANDOM 2013. 
A composition theorem for the Fourier EntropyInfluence conjecture.

Hypercontractivity via the entropy method.
with Eric Blais.
Theory of Computing 9(29), pp. 889896, (2013).
Special issue on Analysis of Boolean Functions. 
Approximating Boolean functions with depth2 circuits.

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.  Bounding the average
sensitivity and noise sensitivity of PTFs.
with Ilias Diakonikolas, Prasad Raghavendra, and Rocco Servedio.
STOC 2010, 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

Analytic Methods in Concrete Complexity.
Ph.D. Thesis.
Columbia University, 2014. 
Analysis of Boolean Functions.
10lecture minicourse by Ryan O'Donnell.
2012 Barbados workshop on Computational Complexity.
Manuscripts

Algorithmic signaling of features in auction design.
with Shaddin Dughmi, Nicole Immorlica, and Ryan O'Donnell. 
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. 
Approximate resilience, monotonicity, and the complexity of agnostic learning.
with Dana DachmanSoled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.

Learning large circuits with few negations.
with Eric Blais, Clément Canonne, Igor Oliveira, and Rocco Servedio. 
Discrete isoperimetry via the entropy method.
with Eric Blais and Andrew Wan. 
On the distribution of the Fourier spectrum of LTFs.
with Ilias Diakonikolas, Ragesh Jaiswal, Rocco Servedio, and Andrew Wan.