Andrew Wan

My new webpage is here.

This is the homepage of Andrew Wan. I am a phd student at Columbia University. I also attended Columbia College and the School of Continuing Education. my advisors are Rocco Servedio and Tal Malkin. I study theoretical computer science. My research interests include computational complexity theory, learning theory, and cryptography.
Contact Information 516 Computer Science Building (212)-939-7096 atw12 at columbia dot edu

Teaching: Spring 2008: COMSW 6261: Black Box Complexity of Cryptographic Primitives Spring 2007: COMSW 4261: Introduction to Cryptography Spring 2006: COMSW 4252: Introduction to Computational Learning Theory(CVN) Fall 2005: COMSW 4262: Introduction to Cryptography Spring 2005: COMSW 6998: Advanced Topics in Computational Learning Theory

Papers A. Bogdanov, P. Papakonstantinou, and A. Wan Pseudorandomness for Read-once Formulas Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, to appear. A. Klivans, H.K. Lee, and A. Wan Mansour's Conjecture is True for Random DNF 23rd International Conference on Learning Theory (COLT 2010), to appear, 2010 I. Diakonikolas, R.A. Servedio, L. Tan, and A. Wan A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions 25th Conference on Computational Complexity (CCC), to appear, 2010. A. Bogdanov, K. Talwar, and A. Wan Hard Instances for Satisfiability and Quasi-one-way Functions The First Symposium on Innovations in Computer Science (ICS) 2010. D. Dachman-Soled, H. Lee, T. Malkin, R. Servedio, A. Wan, H. Wee Optimal Cryptographic Hardness of Learning Monotone Functions. Theory of Computing, to appear. 35th International Conference on Automata, Languages and Programming (ICALP), 2008. I. Diakonikolas, H. Lee, K. Matulef, R. Servedio and A. Wan Efficiently Testing Sparse GF(2) Polynomials. 35th International Conference on Automata, Languages and Programming (ICALP), 2008. J. Jackson, H. Lee, R. Servedio and A. Wan Learning Random Monotone DNF Discrete Applied Mathematics, to appear. RANDOM 2008, pp 283-497. Also available as ECCC Tech Report TR07-129. I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio and A. Wan. Testing for Concise Representations 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007, pp 549-558. Homin Lee, Rocco Servedio and Andrew Wan. DNF are Teachable in the Average Case. 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. Ariel Elbaz, Homin Lee, Rocco Servedio and Andrew Wan. Separating Models of Learning from Correlated and Uncorrelated Data. 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. Rocco Servedio and Andrew Wan. Computing Sparse Permanents Faster. Information Processing Letters 96(5), 2005, pp. 89-92.

* ***