Publications
-
Deterministic search for CNF satisfying assignments in almost polynomial time
with Rocco Servedio.
FOCS 2017 -
Fooling intersections of low-weight halfspaces
with Rocco Servedio.
FOCS 2017 -
Settling the query complexity of non-adaptive junta testing
with Xi Chen, Rocco Servedio, Erik Waingarten, and Jinyu Xie.
CCC 2017Best Paper Award at CCC 2017
Invited to the Journal of the ACM -
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
with Xi Chen, Rocco Servedio, and Erik Waingarten.
RANDOM 2017 -
What circuit classes can be learned with non-trivial savings?
with Rocco Servedio.
ITCS 2017 -
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
with Toniann Pitassi, Benjamin Rossman, and Rocco Servedio.
STOC 2016
Invited to STOC 2016 special issueSee also Ryan O'Donnell's lecture on our switching lemma. -
Near-optimal small-depth 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 126(9), pp. 2719-2733, (2016) -
Algorithmic signaling of features in auction design
with Shaddin Dughmi, Nicole Immorlica, and Ryan O'Donnell.
SAGT 2015 -
An average-case 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 ACMSee Computational Complexity, Shtetl-Optimized, 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 2015See also [Chen-Servedio-T-Waingarten-Xie '17] for an improved lower bound. -
Boolean monotonicity testing requires (almost) n1/2 non-adaptive queries
with Xi Chen, Anindya De, and Rocco Servedio.
STOC 2015See also [Khot-Minzer-Safra '15] for the matching upper bound, and [Belovs-Blais '16, Chen-Waingarten-Xie '17] for adaptive lower bounds. -
Approximate resilience, monotonicity, and the complexity of agnostic learning
with Dana Dachman-Soled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.
SODA 2015 -
New algorithms and lower bounds for monotonicity testing
with Xi Chen and Rocco Servedio.
FOCS 2014Videos of talks at IAS and FOCS, and scribe notes on the lower bound. See also [Chen-De-Servedio-T '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 Frankl-Rödl graph
with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
SODA 2014
Discrete Analysis 2016:4 -
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 k-CNF formulas
with Dominik Scheder.
RANDOM 2013 -
A composition theorem for the Fourier Entropy-Influence conjecture
with Ryan O'Donnell.
ICALP 2013
See also [Wan-Wright-Wu '14] for a new proof of our composition theorem. -
Approximating Boolean functions with depth-2 circuits
with Eric Blais.
CCC 2013
SIAM Journal on Computing 44(6), pp. 1583-1600, (2015)See also Gödel's Lost Letter and P=NP for a discussion of this paper, and [Blais-Håstad-Servedio-T '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. 889-896, (2013)
Special issue on Analysis of Boolean Functions. -
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
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, Article 4, pp. 1-13, (2015) - Bounding the average
sensitivity and noise sensitivity of PTFs
with Ilias Diakonikolas, Prasad Raghavendra, and Rocco Servedio.
STOC 2010
Conference version 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.
CCC 2010
Theory of Computing 10(2), pp. 27-53, (2014)
Other writings
-
The Polynomial Hierarchy, Random Oracles, and Boolean Circuits
with Benjamin Rossman and Rocco Servedio.
Invited article in ACM SIGACT News 46(4), December 2015 issue
Overview of [Rossman-Servedio-T '15], with an emphasis on the connections to structural complexity theory. -
Research Vignette: Hard Problems All the Way Up
with Benjamin Rossman.
UC Berkeley Simons Institute newsletter, Summer 2015 issue
-
Analytic Methods in Concrete Complexity
Ph.D. Thesis.
Columbia University, 2014. -
2014 Simons Symposium on Discrete Analysis
-
Analysis of Boolean Functions
10-lecture minicourse by Ryan O'Donnell.
2012 Barbados workshop on Computational Complexity.
Manuscripts
-
Discrete isoperimetry via the entropy method
with Eric Blais and Andrew Wan.