A polynomial lower bound for monotonicity testing of Boolean
functions over hypercube and hypergrid domains.
with Rocco Servedio.
On DNF approximators for monotone Boolean functions.
with Eric Blais, Johan Håstad, and Rocco Servedio.
Monotonicity, resilience, and the hardness of agnostic learning.
with Dana Dachman-Soled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.
Learning circuits with few negations.
with Eric Blais, Clément Canonne, Igor Carboni Oliveira, and Rocco Servedio.
A composition theorem for parity kill number.
with Ryan O'Donnell, Xiaorui Sun, John Wright, and Yu Zhao.
Discrete isoperimetry via the entropy method.
with Eric Blais and Andrew Wan.
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph.
with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
Learning sums of independent integer random variables.
with Costis Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, and Rocco Servedio.
FOCS 2013. [slides
Blog post about our work: MIT Theory student blog
On the average sensitivity and density of k-CNF formulas.
with Dominik Scheder.
A composition theorem for the Fourier Entropy-Influence conjecture.
with Ryan O'Donnell.
Hypercontractivity via the entropy method.
Approximating Boolean functions with depth-2 circuits.
New NP-hardness results for 3-coloring and 2-to-1 label cover.
with Per Austrin, Ryan O'Donnell, and John Wright.
ACM Transactions on Computation Theory.
Analysis of Boolean functions.
Attribute-efficient learning and weight-degree tradeoffs for
with Rocco Servedio and Justin Thaler.
On the distribution of the Fourier spectrum of LTFs.
with Ilias Diakonikolas, Ragesh Jaiswal, Rocco Servedio, and
- Bounding the average
sensitivity and noise sensitivity of PTFs.
with Ilias Diakonikolas, Prasad Raghavendra, and Rocco
STOC 2010, merged with [Harsha-Klivans-Meka
SIAM Journal on Computuing.
A regularity lemma, and low-weight approximators, for low-degree PTFs.
with Ilias Diakonikolas, Rocco Servedio, and Andrew
Theory of Computing.
- The meta-theory of Q0 in the calculus of inductive
M.Sc. Thesis, 2006.
- The algebra of equality proofs.
with Aaron Stump.