Book

• Algorithmic Aspects of Machine Learning (Draft)
  Cambridge University Press, Summer 2018

Essays

• Robustness Meets Algorithms Technical Perspective: Jacob Steinhardt
  with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart
  Communications of the ACM May 2021, Research Highlights

• Learning Topic Models -- Provably and Efficiently Technical Perspective: David Blei
  with Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, David Sontag, Yichen Wu and Michael Zhu
  Communications of the ACM April 2018, Research Highlights

• 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

Manuscripts

• Precise Error Rates for Computationally Efficient Testing
  with Alex Wein
  Manuscript, 2023

Papers

• Structure Learning of Hamiltonians from Real-time Evolution
  with Ainesh Bakshi, Allen Liu and Ewin Tang
  Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear

• Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
  with Noah Golowich and Dhruv Rohatgi
  Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear

• High-Temperature Gibbs States are Unentangled and Efficiently Preparable
  with Ainesh Bakshi, Allen Liu and Ewin Tang
  Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), to appear

• The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
  with Noah Golowich
  Proceedings of the 1st Annual Reinforcement Learning Conference (RLC 2024), to appear

• Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
  with Noah Golowich
  Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), to appear

• The Power of an Adversary in Glauber Dynamics
  with Byron Chin, Elchanan Mossel and Colin Sandon
  Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), to appear

• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
  with Noah Golowich and Dhruv Rohatgi
  Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), to appear

• Learning Quantum Hamiltonians at Any Temperature in Polynomial Time
  with Ainesh Bakshi, Allen Liu and Ewin Tang
  Invited to the SIAM Journal on Computing Special Issue for STOC 2024
  Quantum Information Processing (QIP 2024) Invited Plenary
  Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), to appear

• Provable Benefits of Score Matching
  with Chirag Pabbaraju, Anish Sevekari, Holden Lee, Andrej Risteski and Dhruv Rohatgi
  Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Spotlight

• Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
  with Zongchen Chen, Kuikui Liu and Nitya Mani
  Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023)

• Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems
  with Ainesh Bakshi, Allen Liu and Morris Yau
  Proceedings of the 40th International Conference on Machine Learning (ICML 2023)

• A New Approach to Learning Linear Dynamical Systems
  with Ainesh Bakshi, Allen Liu and Morris Yau
  Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)

• Planning and Learning in Partially Observable Systems via Filter Stability
  with Noah Golowich and Dhruv Rohatgi
  Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)

• Distilling Model Failures as Directions in Latent Space
  with Saachi Jain, Hannah Lawrence and Aleksander Madry
  The 11th International Conference on Learning Representations (ICLR 2023) Spotlight

• Provably Auditing Ordinary Least Squares in Low Dimensions
  with Dhruv Rohatgi
  The 11th International Conference on Learning Representations (ICLR 2023)

• From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SAT
  with Zongchen Chen and Nitya Mani
  Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

• Robust Voting Rules from Algorithmic Robust Statistics
  with Allen Liu
  Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)

• Learning in Observable POMDPs, without Computationally Intractable Oracles
  with Noah Golowich and Dhruv Rohatgi
  Advances in Neural Information Processing Systems 35 (NeurIPS 2022)

• Robust Model Selection and Nearly-Proper Learning for GMMs
  with Jerry Li and Allen Liu
  Advances in Neural Information Processing Systems 35 (NeurIPS 2022)

• Polynomial Time Guarantees for the Burer-Monteiro Method
  with Diego Cifuentes
  Advances in Neural Information Processing Systems 35 (NeurIPS 2022)

• Minimax Rates for Robust Community Detection
  with Allen Liu
  Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022)

• Can Q-Learning be Improved with Advice?
  with Noah Golowich
  Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

• Learning GMMs with Nearly Optimal Robustness Guarantees
  with Allen Liu
  Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

• Kalman Filtering with Adversarial Corruptions
  with Sitan Chen, Frederic Koehler and Morris Yau
  Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)

• A No-go Theorem for Acceleration in the Hyperbolic Plane
  with Linus Hamilton
  Advances in Neural Information Processing Systems 34 (NeurIPS 2021)

• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
  with Sitan Chen, Frederic Koehler and Morris Yau
  Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021)

• Learning to Sample from Censored Markov Random Fields
  with Elchanan Mossel and Colin Sandon
  Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

• Settling the Robust Learnability of Mixtures of Gaussians
  with Allen Liu
  Journal of the ACM, to appear
  Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)

• Algorithmic Foundations for the Diffraction Limit
  with Sitan Chen
  Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)

• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
  with Sitan Chen, Frederic Koehler and Morris Yau
  Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Spotlight

• Tensor Completion Made Practical
  with Allen Liu
  Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

• Learning Structured Distributions from Untrusted Batches: Faster and Simpler
  with Sitan Chen and Jerry Li
  Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
  with Jonathan Kelner, Frederic Koehler and Raghu Meka
  Advances in Neural Information Processing Systems 33 (NeurIPS 2020), Spotlight

• Rigorous Guarantees for Tyler's M-estimator via Quantum Expansion
  with Cole Franks
  Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

• Parallels Between Phase Transitions and Circuit Complexity?
  with Elchanan Mossel and Colin Sandon
  Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

• Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation
  with Allen Liu
  Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

• Efficiently Learning Structured Distributions from Untrusted Batches
  with Sitan Chen and Jerry Li
  Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020)

• Spectral Methods from Tensor Networks
  with Alex Wein
  Invited to the SIAM Journal on Computing Special Issue for STOC 2019
  Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)

• Learning Restricted Boltzmann Machines via Influence Maximization
  with Guy Bresler and Frederic Koehler
  Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)

• Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
  with Sitan Chen
  Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)

• How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
  with Younhun Kim, Frederic Koehler, Elchanan Mossel and Govind Ramnarayan
  Journal of Computational Biology Special Issue for RECOMB 2019
  Proceedings of the 23rd Intl. Conference on Research in Computational Molecular Biology (RECOMB 2019)

• The Paulsen Problem Made Simple
  with Linus Hamilton
  Israel Journal of Mathematics
  Proceedings of the 10th Annual Innovations in Theoretical Computer Science (ITCS 2019)

• Improved Bounds for Sampling Colorings via Linear Programming
  with Sitan Chen, Michelle Delcourt, Guillem Perarnau and Luke Postle
  Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

• Efficiently Learning Mixtures of Mallows Models
  with Allen Liu
  Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018)

• Optimality and Suboptimality of PCA I: Spiked Random Matrix Models
  with Amelia Perry, Alex Wein and Afonso Bandeira
  Annals of Statistics, 2018

• 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)

• Message-Passing Algorithms for Synchronization Problems over Compact Groups
  with Amelia Perry, Alex Wein and Afonso Bandeira
  Communications on Pure and Applied Mathematics, 2018

• 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)

• 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
  Journal of the ACM
  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
  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 Communications of the ACM, Research Highlights
  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
  Mathematical Programming, Series B Special Issue
  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
  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