Before joining IBM in Aug 2007 I spent 5 very enjoyable years at Harvard University as a PhD student advised by Leslie Valiant and as a postdoc.
My research interests are primarily in Machine Learning Theory and Computational Complexity. I'm particularly interested in questions in the overlap of these areas. I also work on understanding of natural learning systems: learning by the brain and evolution as learning. This work is based on the models pioneered by Leslie Valiant (brain, evolvability).
- July 2015: instructor at Berkeley summer course in mining and modeling of neuroscience data (with Christos Papadimitriou).
- March-May 2015: visiting scientist at Simons Institute for the Theory of Computing, UC Berkeley. Information Theory.
- March-May 2014: visiting scientist at Simons Institute for the Theory of Computing, UC Berkeley. Evolutionary Biology and the Theory of Computing.
- Sep-Oct 2013: visiting researcher at LIAFA, Universite Paris Diderot.
Recent/upcoming conference program committees:
- COLT 2016: Co-chair (with Sasha Rakhlin).
- AJCAI-ML 2015, ALT 2015, COLT 2015, ITCS 2015 , NIPS 2014, ALT 2014, COLT 2014 (publication chair), ALT 2013, COLT 2013.
Some recent talks:
- Preserving statistical validity in adaptive data analysis. @STOC 2015: slides.
- Approximate resilience, monotonicity, and the complexity of agnostic learning. @SODA 2015: slides.
- Sample complexity bounds on differentially private learning via communication complexity. @COLT 2014 and ITA 2015: slides.
- Using data privacy for better adaptive predictions. Foundations of Learning Theory workshop @COLT 2014 : slides.
- On the power and the limits of evolvability. Simons Institute workshop on Computational Theories of Evolution: slides.
- Optimal bounds on approximation of submodular and XOS functions by juntas. Simons Institute workshop on Real Analysis at @FOCS 2013 : slides.
- Generalization in Adaptive Data Analysis and Holdout Reuse.
With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. Preprint. June, 2015 .
- Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS Functions.
With Jan Vondrak. FOCS 2015 (to appear) .
- Preserving Statistical Validity in Adaptive Data Analysis.
With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. STOC 2015 .
- On the Complexity of Random Satisfiability Problems with Planted Solutions .
With Will Perkins and Santosh Vempala. STOC 2015 .
- Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's .
With Will Perkins and Santosh Vempala. Preprint, 2014 .
- Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions.
With Pravesh Kothari and Jan Vondrak. Preprint. Apr, 2014 .
- Agnostic Learning of Disjunctions on Symmetric Distributions.
With Pravesh Kothari. JMLR 2015 (to appear) .
- Approximate resilience, monotonicity, and the complexity of agnostic learning .
With Dana Dachman-Soled, Li-Yang Tan, Andrew Wan and Karl Wimmer. SODA, 2015 .
- The Statistical Query Complexity of Learning Sparse Halfspaces.
Open Problem at COLT 2014.
- Learning Coverage Functions and Private Release of Marginals.
With Pravesh Kothari. COLT 2014.
- Sample Complexity Bounds on Differentially Private Learning via Communication Complexity .
With David Xiao. COLT 2014.
- Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.
With Nina Balcan. NIPS 2013 . Algorithmica. Special Issue on New Theoretical Challenges in Machine Learning (by invitation)
- Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
With Jan Vondrak. FOCS 2013 . SICOMP 2015 (to appear), Special Issue on FOCS (by invitation), SIGecom Exchanges 12.2 (invited letter)
- Learning using Local Membership Queries.
With Pranjal Awasthi and Varun Kanade. COLT 2013, Best Student (Co-authored) Paper Award .
- Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
With Pravesh Kothari and Jan Vondrak. COLT 2013 .
- Provenance-based Dictionary Refinement in Information Extraction.
With Sudeepa Roy, Laura Chiticariu, Frederick Reiss and Huaiyu Zhu. SIGMOD 2013 .
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
With Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao. STOC 2013 . Full version updated in 2015.
- Computational Bounds on Statistical Query Learning.
With Varun Kanade. COLT 2012.
- Learning DNF Expressions from Fourier Spectrum.
- Nearly Optimal Solutions for the Chow Parameters Problem and Low-weight Approximation of Halfspaces.
With Anindya De, Ilias Diakonikolas and Rocco Servedio. STOC 2012; JACM 2014 .
- Distribution-Independent Evolvability of Linear Threshold Functions.
- Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
With Homin Lee and Rocco Servedio. COLT 2011.
- Distribution-Specific Agnostic Boosting.
ITCS (formerly ICS) 2010.
- Agnostic Learning of Monomials by Halfspaces is Hard.
With Venkatesan Guruswami, Prasad Raghavendra and Yi Wu. FOCS 2009; SICOMP 2012 .
- A Complete Characterization of Statistical Query Learning with Applications to Evolvability.
FOCS 2009; JCSS 2012 (by invitation).
- Sorting and Selection with Imprecise Comparisons.
With Miklos Ajtai, Avinatan Hassidim and Jelani Nelson. ICALP A, 2009; TALG 2015
- Robustness of Evolvability.
- Experience-Induced Neural Circuits That Achieve High Capacity..
With Leslie Valiant. Neural Computation 21:10, 2009.
- On The Power of Membership Queries in Agnostic Learning.
COLT 2008; JMLR 10, 2009
- The Learning Power of Evolution.
With Leslie Valiant. Open Problems/New Directions at COLT 2008.
- Evolvability from Learning Algorithms.
- Separating Models of Learning with Faulty Teachers.
With Shrenik Shah. ALT 2007; TCS 410(19), 2009 (by invitation)
- New Results for Learning Noisy Parities and Halfspaces.
With Parikshit Gopalan, Subhash Khot, and Ashok Ponnuswami. FOCS 2006; SICOMP 39(2), 2009 (by invitation)
- Optimal Hardness Results for Maximizing Agreements with Monomials.
CCC 2006; SICOMP 39(2), 2009 (by invitation)
- Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
STOC 2006; JCSS 75(1), 2009 (by invitation)
- Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
COLT 2005, Best Student Paper Award; JMLR 8, 2007 (by invitation)
- The Complexity of Properly Learning Simple Concept Classes.
With Misha Alekhnovich, Mark Braverman, Adam Klivans, and Toni Pitassi.
FOCS 2004; JCSS 74(1), 2008 (by invitation)
Ph.D. thesis. Efficiency and Computational Limitations of Learning Algorithms. Harvard University. January 2007
- Hardness of Proper Learning.
The Encyclopedia of Algorithms. Springer-Verlag, 2015
- Statistical Query Learning.
The Encyclopedia of Algorithms. Springer-Verlag, 2015
A bit more about me
Some of my favorite hobbies are ballroom dancing, mountain biking, photography, hiking, skiing, drinking tea and visiting Paris.