Andrew Wan
atw12@columbia.edu

• Approximate Resilience, Monotonicity, and the Complexity of Agnostic Learning
      with Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, and Karl Wimmer.
      ACM-SIAM 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 Li-Yang Tan.
      Manuscript.
  
  
• Decision Trees, Protocols, and the Fourier Entropy-Influence 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 Read-once 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. 368-380, 2010.
  
  
• A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
      with Ilias Diakonikolas, Rocco Servedio, and Li-Yang Tan.
      25th Conference on Computational Complexity (CCC), pp. 211-220, 2010.
  
  
• Hard Instances for Satisfiability and Quasi-one-way Functions
      with Andrej Bogdanov and Kunal Talwar.
      The First Symposium on Innovations in Theoretical Computer Science (ITCS), pp. 20-23, 2010.
  
  
• Optimal Cryptographic Hardness of Learning Monotone Functions.
      with Dana Dachman-Soled, Homin Lee, Tal Malkin, Rocco Servedio, and Hoeteck Wee.
      Theory of Computing, Vol. 5, pp. 257-282.
      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 283-497.
  
  
• 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 549-558.
  
  
• DNF are Teachable in the Average Case.
      with Homin Lee and Rocco Servedio.
      Machine Learning, 69(2-3):79-96, 2007.
      Preliminary version in Nineteenth Annual Conference on Computational Learning Theory (COLT), 2006, pp. 214--228.
      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):277-290, 2007.
      Preliminary version in Eighteenth Annual Conference on Computational Learning Theory (COLT), 2005, pp. 637-651.
  
  
• Computing Sparse Permanents Faster.
      with Rocco Servedio.
      Information Processing Letters 96(5), 2005, pp. 89-92.


• Learning, Cryptography and the Average Case
  Ph.D. Thesis, Columbia University, May 2010.