Monograph
- Algorithmic Aspects of Machine Learning
18.409: Topics in Theoretical Computer Science, Spring 2015
18.S996: Special Subject in Mathematics, Fall 2013
Essays
- Disentangling Gaussians Technical Perspective: Santosh Vempala
with Adam Kalai and Greg Valiant
Communications of the ACM February 2012, Research Highlights
See also this related paper of Belkin and Sinha
Papers
- Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), to appear
- Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
with Linus Hamilton and Frederic Koehler
Advances in Neural Information Processing Systems 30 (NIPS 2017), to appear
- Optimality and Suboptimality of PCA I: Spiked Random Matrix Models
with Amelia Perry, Alex Wein and Afonso Bandeira
Annals of Statistics, to appear
- Message-Passing Algorithms for Synchronization Problems over Compact Groups
with Amelia Perry, Alex Wein and Afonso Bandeira
Communications on Pure and Applied Mathematics, to appear
- Learning Determinantal Point Processes with Moments and Cycles
with John Urschel, Victor-Emmanuel Brunel and Philippe Rigollet
Proceedings of the 34th International Conference on Machine Learning (ICML 2017)
- Being Robust (in High Dimensions) Can Be Practical
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Proceedings of the 34th International Conference on Machine Learning (ICML 2017)
- Maximum Likelihood Estimation of Determinantal Point Processes
with Victor-Emmanuel Brunel, Philippe Rigollet and John Urschel
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)
- Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017)
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
with Boaz Barak, Sam Hopkins, Jonathan Kelner, Pravesh Kothari and Aaron Potechin
Invited to the SIAM Journal on Computing Special Issue for FOCS 2016
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
- Robust Estimators in High Dimensions without the Computational Intractability
with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
Invited to the SIAM Journal on Computing Special Issue for FOCS 2016
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
- Provable Algorithms for Inference in Topic Models
with Sanjeev Arora, Rong Ge, Frederic Koehler and Tengyu Ma
Proceedings of the 33rd International Conference on Machine Learning (ICML 2016)
- How Robust are Reconstruction Thresholds for Community Detection?
with Will Perry and Alex Wein
Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)
- Noisy Tensor Completion via the Sum-of-Squares Hierarchy
with Boaz Barak
Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)
- Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree
with Boaz Barak, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer and John Wright
Workshop on Approximation, Randomization and Combinatorial Optimization (APPROX 2015)
- Simple, Efficient and Neural Algorithms for Sparse Coding
with Sanjeev Arora, Rong Ge and Tengyu Ma
Proceedings of the 28th Annual Conference on Learning Theory (COLT 2015)
- Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015)
- New Algorithms for Learning Incoherent and Overcomplete Dictionaries
with Sanjeev Arora and Rong Ge
Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014)
- Smoothed Analysis of Tensor Decompositions
with Aditya Bhaskara, Moses Charikar and Aravindan Vijayaraghavan
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)
- A Polynomial Time Approximation Scheme for Fault-tolerant Distributed
Storage
with Constantinos Daskalakis, Anindya De, Ilias Diakonikolas and Rocco Servedio
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
- A Polynomial Time Algorithm for Lossy Population Recovery
with Michael Saks
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
- Algorithms and Hardness for Robust Subspace Recovery
with Moritz Hardt
Proceedings of the 26th Annual Conference on Learning Theory (COLT 2013)
- A Practical Algorithm for Topic Modeling with Provable Guarantees
with Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, David Sontag, Yichen Wu and Michael Zhu
Invited to Communications of the ACM, Research Highlights
Proceedings of the 30th International Conference on Machine Learning (ICML 2013)
- An Information Complexity Approach to Extended Formulations
with Mark Braverman
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013)
- An Almost Optimal Algorithm for Computing Nonnegative Rank
SIAM Journal on Computing
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
- Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders
with Sanjeev Arora, Rong Ge and Sushant Sachdeva
Algorithmica Special Issue for Machine Learning
Advances in Neural Information Processing Systems 25 (NIPS 2012)
- Learning Topic Models -- Going Beyond SVD
with Sanjeev Arora and Rong Ge
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
- Computing a Nonnegative Matrix Factorization -- Provably
with Sanjeev Arora, Rong Ge and Ravi Kannan
SIAM Journal on Computing Special Issue for STOC 2012
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)
- Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
with Noga Alon and Benny Sudakov
Journal of the European Mathematical Society, to appear
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)
- On Entropy and Extensions of Posets
with Tom Leighton
Manuscript, 2011
- Efficient and Explicit Coding for Interactive Communication
with Ran Gelles and Amit Sahai
IEEE Transactions on Information Theory
Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)
- Pareto Optimal Solutions for Smoothed Analysts
with Ryan O'Donnell
SIAM Journal on Computing Special Issue for STOC 2011
Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011)
- Dueling Algorithms Related: MIT News
with Nicole Immorlica, Adam Kalai, Brendan Lucier, Andrew Postlewaite and Moshe Tennenholtz
Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011)
- Capacitated Metric Labeling
with Matthew Andrews, Mohammadtaghi Hajiaghayi and Howard Karloff
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
- Settling the Polynomial Learnability of Mixtures of Gaussians
with Greg Valiant
Invited to Communications of the ACM, Research Highlights
Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
- Vertex Sparsifiers and Abstract Rounding Algorithms
with Moses Charikar, Tom Leighton and Shi Li
Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)
- Efficiently Learning Mixtures of Two Gaussians
with Adam Kalai and Greg Valiant
Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010)
- Extensions and Limits to Vertex Sparsification
with Tom Leighton
Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010)
- Vertex Sparsification and Oblivious Reductions
SIAM Journal on Computing Special Issue for FOCS 2009
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)
- Some Results on Greedy Embeddings in Metric Spaces
with Tom Leighton
Discrete and Computational Geometry (Invited)
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)
Thesis
- Vertex Sparsification and Universal Rounding Algorithms
George M. Sprowls Award for Best PhD Thesis in Computer Science
Ph.D. Thesis 2011
- A Solution to the Papadimitriou-Ratajczak Conjecture
William A. Martin Memorial Award for Best Master's Thesis in Computer Science
S. M. Thesis 2009