Approximate resilience, monotonicity, and the complexity of agnostic learning.
with Dana Dachman-Soled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.
New algorithms and lower bounds for monotonicity testing.
On DNF approximators for monotone Boolean functions.
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 Frankl-Rödl graph.
with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
Learning sums of independent integer random variables.
On the average sensitivity and density of k-CNF formulas.
with Dominik Scheder.
A composition theorem for the Fourier Entropy-Influence conjecture.
Hypercontractivity via the entropy method.
with Eric Blais.
Theory of Computing 9(29), pp. 889-896, (2013).
Special issue on Analysis of Boolean Functions.
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 6(1), Article 2, (2014).
Attribute-efficient learning and weight-degree tradeoffs for
with Rocco Servedio and Justin Thaler.
Blog post about our work: My Biased Coin.
- Bounding the average
sensitivity and noise sensitivity of PTFs.
with Ilias Diakonikolas, Prasad Raghavendra, and Rocco Servedio.
STOC 2010, merged with [Harsha-Klivans-Meka].
SIAM Journal on Computing 43(1), pp. 231-253, (2014).
A regularity lemma and low-weight approximators for low-degree PTFs.
with Ilias Diakonikolas, Rocco Servedio, and Andrew Wan.
Theory of Computing 10(2), pp. 27-53, (2014).
- The algebra of equality proofs.
with Aaron Stump.
Analytic Methods in Concrete Complexity.
Columbia University, 2014.
Analysis of Boolean Functions.
10-lecture minicourse by Ryan O'Donnell.
2012 Barbados workshop on Computational Complexity.Manuscripts
Adaptivity helps for testing juntas.
with Rocco Servedio and John Wright.
Boolean monotonicity testing requires (almost) n1/2 non-adaptive queries.
with Xi Chen, Anindya De, and Rocco Servedio.
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.
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.
- Adaptivity helps for testing juntas.