Papers

Approximate Resilience, Monotonicity, and the Complexity of Agnostic Learning
with Dana DachmanSoled, Vitaly Feldman, LiYang Tan, and Karl Wimmer.
ACMSIAM Symoposium on Discrete Algorithms (SODA 2015), to appear.

Satisfiability and Evolution
with Adi Livnat, Christos Papadimitriou, Aviad Rubinstein, and Gregory Valiant.
55th Annual Symposium on Foundations of Computer Science (FOCS 2014), to appear.

Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
with Thomas Steinke and Salil Vadhan.
18th International Workshop on Randomization and Computation (RANDOM) , 2014, to appear.

Discrete Isoperimetry via the Entropy Method
with Eric Blais and LiYang Tan.
Manuscript.

Decision Trees, Protocols, and the Fourier EntropyInfluence Conjecture
with John Wright and Chenggang Wu.
5th Innovations in Theoretical Computer Science (ITCS), 2014, to appear.

Faster Private Release of Marginals on Small Databases
with Karthekayan Chandrasekaran, Justin Thaler, and Jonathan Ullman.
5th Innovations in Theoretical Computer Science (ITCS), 2014, to appear.

Pseudorandmoness for Linear Length Branching Programs and Stack Machines
with Andrej Bogdanov and Periklis Papakonstantinou.
16th International Workshop on Randomization and Computation (RANDOM), 2012.

Pseudorandomness for Readonce Formulas
with Andrej Bogdanov and Periklis Papakonstantinou.
Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.

Mansour's Conjecture is True for Random DNF
with Adam Klivans, Homin Lee, and A. Wan
23rd International Conference on Learning Theory (COLT), pp. 368380, 2010.

A Regularity Lemma, and LowWeight Approximators, for LowDegree Polynomial Threshold Functions
with Ilias Diakonikolas, Rocco Servedio, and LiYang Tan.
25th Conference on Computational Complexity (CCC), pp. 211220, 2010.

Hard Instances for Satisfiability and Quasioneway Functions
with Andrej Bogdanov and Kunal Talwar.
The First Symposium on Innovations in Theoretical Computer Science (ITCS), pp. 2023, 2010.

Optimal Cryptographic Hardness of Learning Monotone Functions.
with Dana DachmanSoled, Homin Lee, Tal Malkin, Rocco Servedio, and Hoeteck Wee.
Theory of Computing, Vol. 5, pp. 257282.
35th International Conference on Automata,
Languages and Programming (ICALP), 2008.

Efficiently Testing Sparse GF(2) Polynomials.
with Ilias Diakonikolas, Homin Lee, Kevin Matulef, and Rocco Servedio.
35th International Conference on Automata,
Languages and Programming (ICALP), 2008.

Learning Random Monotone DNF
with Jeffrey Jackson, Homin Lee, and Rocco Servedio.
Discrete Applied Mathematics, to appear.
RANDOM 2008, pp 283497.

Testing for Concise Representations
with Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, and Rocco Servedio.
48th Annual Symposium on Foundations of Computer Science
(FOCS), 2007, pp 549558.

DNF are Teachable in the Average Case.
with Homin Lee and Rocco Servedio.
Machine Learning, 69(23):7996, 2007.
Preliminary version in Nineteenth Annual Conference on Computational Learning Theory (COLT), 2006, pp. 214228.
Mark Fulk Best Student Paper award, COLT 2006.

Separating Models of Learning from Correlated and Uncorrelated Data.
with Ariel Elbaz, Homin Lee, and Rocco Servedio.
Journal of Machine Learning Research, 8(Feb):277290, 2007.
Preliminary version in
Eighteenth Annual Conference on Computational Learning Theory (COLT),
2005, pp. 637651.

Computing Sparse Permanents Faster.
with Rocco Servedio.
Information Processing Letters 96(5), 2005, pp. 8992.
 Learning, Cryptography and the Average Case
Ph.D. Thesis, Columbia University, May 2010.
