Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. - Ankur Moitra (FOCS, 2009)

Vertex Sparsifiers and Abstract Rounding Algorithms. - Moses Charikar; Tom Leighton; Shi Li 001; Ankur Moitra (FOCS, 2010)

Settling the Polynomial Learnability of Mixtures of Gaussians. - Ankur Moitra; Gregory Valiant (FOCS, 2010)

Efficiently learning mixtures of two Gaussians. - Adam Tauman Kalai; Ankur Moitra; Gregory Valiant (STOC, 2010)

Extensions and limits to vertex sparsification. - Frank Thomson Leighton; Ankur Moitra (STOC, 2010)

Some Results on Greedy Embeddings in Metric Spaces. - Tom Leighton; Ankur Moitra (Discret. Comput. Geom., 2010)

Efficient and Explicit Coding for Interactive Communication. - Ran Gelles; Ankur Moitra; Amit Sahai (FOCS, 2011)

Capacitated Metric Labeling. - Matthew Andrews; Mohammad Taghi Hajiaghayi; Howard J. Karloff; Ankur Moitra (SODA, 2011)

Dueling algorithms. - Nicole Immorlica; Adam Tauman Kalai; Brendan Lucier; Ankur Moitra; Andrew Postlewaite; Moshe Tennenholtz (STOC, 2011)

Efficiently Coding for Interactive Communication. - Ankur Moitra (Electron. Colloquium Comput. Complex., 2011)

Vertex sparsification and universal rounding algorithms. - Ankur Moitra (2011)

Learning Topic Models - Going beyond SVD. - Sanjeev Arora; Rong Ge 001; Ankur Moitra (FOCS, 2012)

"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders". - Sanjeev Arora; Rong Ge 001; Ankur Moitra; Sushant Sachdeva (NIPS, 2012)

Nearly complete graphs decomposable into large induced matchings and their applications. - Noga Alon; Ankur Moitra; Benny Sudakov (STOC, 2012)

Disentangling Gaussians. - Adam Tauman Kalai; Ankur Moitra; Gregory Valiant (Commun. ACM, 2012)

Can We Reconcile Robustness and Efficiency in Unsupervised Learning? - Moritz Hardt; Ankur Moitra (CoRR, 2012)

An Information Complexity Approach to Extended Formulations. - Mark Braverman; Ankur Moitra (Electron. Colloquium Comput. Complex., 2012)

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. - Ankur Moitra (Electron. Colloquium Comput. Complex., 2012)

Pareto Optimal Solutions for Smoothed Analysts. - Ankur Moitra; Ryan O'Donnell (SIAM J. Comput., 2012)

Algorithms and Hardness for Robust Subspace Recovery. - Moritz Hardt; Ankur Moitra (COLT, 2013)

A Polynomial Time Algorithm for Lossy Population Recovery. - Ankur Moitra; Michael E. Saks (FOCS, 2013)

A Practical Algorithm for Topic Modeling with Provable Guarantees. - Sanjeev Arora; Rong Ge 001; Yonatan Halpern; David M. Mimno; Ankur Moitra; David A. Sontag; Yichen Wu; Michael Zhu (ICML (2), 2013)

Vertex Sparsification and Oblivious Reductions. - Ankur Moitra (SIAM J. Comput., 2013)

New Algorithms for Learning Incoherent and Overcomplete Dictionaries. - Sanjeev Arora; Rong Ge 001; Ankur Moitra (COLT, 2014)

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? - Aditya Bhaskara; Moses Charikar; Ankur Moitra; Aravindan Vijayaraghavan (COLT, 2014)

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. - Constantinos Daskalakis; Anindya De; Ilias Diakonikolas; Ankur Moitra; Rocco A. Servedio (SODA, 2014)

Smoothed analysis of tensor decompositions. - Aditya Bhaskara; Moses Charikar; Ankur Moitra; Aravindan Vijayaraghavan (STOC, 2014)

The Threshold for Super-resolution via Extremal Functions. - Ankur Moitra (CoRR, 2014)

Efficient Coding for Interactive Communication. - Ran Gelles; Ankur Moitra; Amit Sahai (IEEE Trans. Inf. Theory, 2014)

Simple, Efficient, and Neural Algorithms for Sparse Coding. - Sanjeev Arora; Rong Ge 001; Tengyu Ma 001; Ankur Moitra (COLT, 2015)

Beyond Matrix Completion (Invited Talk). - Ankur Moitra (FSTTCS, 2015)

Nonnegative Matrix Factorization: Algorithms, Complexity and Applications. - Ankur Moitra (ISSAC, 2015)

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. - Ankur Moitra (STOC, 2015)

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. - Sanjeev Arora; Rong Ge 001; Ankur Moitra; Sushant Sachdeva (Algorithmica, 2015)

Tensor Prediction, Rademacher Complexity and Random 3-XOR. - Boaz Barak; Ankur Moitra (CoRR, 2015)

Beating the random assignment on constraint satisfaction problems of bounded degree. - Boaz Barak; Ankur Moitra; Ryan O'Donnell; Prasad Raghavendra; Oded Regev 001; David Steurer; Luca Trevisan 001; Aravindan Vijayaraghavan; David Witmer; John Wright 004 (Electron. Colloquium Comput. Complex., 2015)

Provable Algorithms for Inference in Topic Models. - Sanjeev Arora; Rong Ge 001; Frederic Koehler; Tengyu Ma 001; Ankur Moitra (ICML, 2016)

How robust are reconstruction thresholds for community detection? - Ankur Moitra; William Perry; Alexander S. Wein (STOC, 2016)

Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization. - Amelia Perry; Alexander S. Wein; Afonso S. Bandeira; Ankur Moitra (CoRR, 2016)

Message-passing algorithms for synchronization problems over compact groups. - Amelia Perry; Alexander S. Wein; Afonso S. Bandeira; Ankur Moitra (CoRR, 2016)

Computing a Nonnegative Matrix Factorization - Provably. - Sanjeev Arora; Rong Ge 001; Ravi Kannan; Ankur Moitra (SIAM J. Comput., 2016)

An Almost Optimal Algorithm for Computing Nonnegative Rank. - Ankur Moitra (SIAM J. Comput., 2016)

Rates of estimation for determinantal point processes. - Victor-Emmanuel Brunel; Ankur Moitra; Philippe Rigollet; John C. Urschel (COLT, 2017)

Being Robust (in High Dimensions) Can Be Practical. - Ilias Diakonikolas; Gautam Kamath 001; Daniel M. Kane; Jerry Li 001; Ankur Moitra; Alistair Stewart (ICML, 2017)

Learning Determinantal Point Processes with Moments and Cycles. - John C. Urschel; Victor-Emmanuel Brunel; Ankur Moitra; Philippe Rigollet (ICML, 2017)

Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications. - Linus Hamilton; Frederic Koehler; Ankur Moitra (NIPS, 2017)

Efficiently Learning Mixtures of Mallows Models. - Allen Liu; Ankur Moitra (FOCS, 2018)

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. - Ilias Diakonikolas; Gautam Kamath 001; Daniel M. Kane; Jerry Li 001; Ankur Moitra; Alistair Stewart (SODA, 2018)

Robustness Meets Algorithms (Invited Talk). - Ankur Moitra (SWAT, 2018)

Learning topic models - provably and efficiently. - Sanjeev Arora; Rong Ge 001; Yoni Halpern; David M. Mimno; Ankur Moitra; David A. Sontag; Yichen Wu; Michael Zhu (Commun. ACM, 2018)

Learning Mixtures of Product Distributions via Higher Multilinear Moments. - Sitan Chen; Ankur Moitra (CoRR, 2018)

Linear Programming Bounds for Randomly Sampling Colorings. - Sitan Chen; Ankur Moitra (CoRR, 2018)

Learning Restricted Boltzmann Machines via Influence Maximization. - Guy Bresler; Frederic Koehler; Ankur Moitra; Elchanan Mossel (CoRR, 2018)

Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models. - Amelia Perry; Alexander S. Wein; Afonso S. Bandeira; Ankur Moitra (CoRR, 2018)

The Paulsen Problem Made Simple. - Linus Hamilton; Ankur Moitra (ITCS, 2019)

Improved Bounds for Randomly Sampling Colorings via Linear Programming. - Sitan Chen; Michelle Delcourt; Ankur Moitra; Guillem Perarnau; Luke Postle (SODA, 2019)

Learning restricted Boltzmann machines via influence maximization. - Guy Bresler; Frederic Koehler; Ankur Moitra (STOC, 2019)

Beyond the low-degree algorithm: mixtures of subcubes and their applications. - Sitan Chen; Ankur Moitra (STOC, 2019)

The Circuit Complexity of Inference. - Ankur Moitra; Elchanan Mossel; Colin Sandon (CoRR, 2019)

Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models. - Ankur Moitra (J. ACM, 2019)

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. - Boaz Barak; Samuel B. Hopkins 001; Jonathan A. Kelner; Pravesh K. Kothari; Ankur Moitra; Aaron Potechin (SIAM J. Comput., 2019)

Robust Estimators in High-Dimensions Without the Computational Intractability. - Ilias Diakonikolas; Gautam Kamath 001; Daniel Kane 001; Jerry Li 001; Ankur Moitra; Alistair Stewart (SIAM J. Comput., 2019)

Spectral Methods from Tensor Networks. - Ankur Moitra; Alexander S. Wein (SIAM J. Comput., 2019)

Topic Models and Nonnegative Matrix Factorization. - Rong Ge 001; Ankur Moitra (Beyond the Worst-Case Analysis of Algorithms, 2020)

Semirandom Stochastic Block Models. - Ankur Moitra (Beyond the Worst-Case Analysis of Algorithms, 2020)

Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion. - William Cole Franks; Ankur Moitra (COLT, 2020)

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation. - Allen Liu; Ankur Moitra (COLT, 2020)

Parallels Between Phase Transitions and Circuit Complexity? - Ankur Moitra; Elchanan Mossel; Colin Sandon (COLT, 2020)

Learning Structured Distributions From Untrusted Batches: Faster and Simpler. - Sitan Chen; Jerry Li 001; Ankur Moitra (NeurIPS, 2020)

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability. - Sitan Chen; Frederic Koehler; Ankur Moitra; Morris Yau (NeurIPS, 2020)

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Ankur Moitra (NeurIPS, 2020)

Tensor Completion Made Practical. - Allen Liu; Ankur Moitra (NeurIPS, 2020)

Efficiently learning structured distributions from untrusted batches. - Sitan Chen; Jerry Li 001; Ankur Moitra (STOC, 2020)

Fast Convergence for Langevin Diffusion with Matrix Manifold Structure. - Ankur Moitra; Andrej Risteski (CoRR, 2020)

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability. - Sitan Chen; Frederic Koehler; Ankur Moitra; Morris Yau (CoRR, 2020)

How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories. - Younhun Kim; Frederic Koehler; Ankur Moitra; Elchanan Mossel; Govind Ramnarayan (J. Comput. Biol., 2020)

Learning to Sample from Censored Markov Random Fields. - Ankur Moitra; Elchanan Mossel; Colin Sandon (COLT, 2021)

Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. - Sitan Chen; Frederic Koehler; Ankur Moitra; Morris Yau (FOCS, 2021)

A No-go Theorem for Robust Acceleration in the Hyperbolic Plane. - Linus Hamilton; Ankur Moitra (NeurIPS, 2021)

Algorithmic foundations for the diffraction limit. - Sitan Chen; Ankur Moitra (STOC, 2021)

Settling the robust learnability of mixtures of Gaussians. - Allen Liu; Ankur Moitra (STOC, 2021)

Robustness meets algorithms. - Ilias Diakonikolas; Gautam Kamath 001; Daniel M. Kane; Jerry Li 001; Ankur Moitra; Alistair Stewart (Commun. ACM, 2021)

No-go Theorem for Acceleration in the Hyperbolic Plane. - Linus Hamilton; Ankur Moitra (CoRR, 2021)

How to Decompose a Tensor with Group Structure. - Allen Liu; Ankur Moitra (CoRR, 2021)

Sparsification for Sums of Exponentials and its Algorithmic Applications. - Jerry Li 001; Allen Liu; Ankur Moitra (CoRR, 2021)

Spoofing Generalization: When Can't You Trust Proprietary Models? - Ankur Moitra; Elchanan Mossel; Colin Sandon (CoRR, 2021)

Can Q-learning be Improved with Advice? - Noah Golowich; Ankur Moitra (COLT, 2022)

Learning GMMs with Nearly Optimal Robustness Guarantees. - Allen Liu; Ankur Moitra (COLT, 2022)

Minimax Rates for Robust Community Detection. - Allen Liu; Ankur Moitra (FOCS, 2022)

Polynomial time guarantees for the Burer-Monteiro method. - Diego Cifuentes; Ankur Moitra (NeurIPS, 2022)

Learning in Observable POMDPs, without Computationally Intractable Oracles. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (NeurIPS, 2022)

Robust Model Selection and Nearly-Proper Learning for GMMs. - Allen Liu; Jerry Li 001; Ankur Moitra (NeurIPS, 2022)

Kalman filtering with adversarial corruptions. - Sitan Chen; Frederic Koehler; Ankur Moitra; Morris Yau (STOC, 2022)

Planning in Observable POMDPs in Quasipolynomial Time. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (CoRR, 2022)

From algorithms to connectivity and back: finding a giant component in random k-SAT. - Zongchen Chen; Nitya Mani; Ankur Moitra (CoRR, 2022)

Noisy tensor completion via the sum-of-squares hierarchy. - Boaz Barak; Ankur Moitra (Math. Program., 2022)

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. - Zongchen Chen; Kuikui Liu; Nitya Mani; Ankur Moitra (FOCS, 2023)

Distilling Model Failures as Directions in Latent Space. - Saachi Jain; Hannah Lawrence; Ankur Moitra; Aleksander Madry (ICLR, 2023)

Provably Auditing Ordinary Least Squares in Low Dimensions. - Ankur Moitra; Dhruv Rohatgi (ICLR, 2023)

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems. - Ainesh Bakshi; Allen Liu; Ankur Moitra; Morris Yau (ICML, 2023)

Provable benefits of score matching. - Chirag Pabbaraju; Dhruv Rohatgi; Anish Prasad Sevekari; Holden Lee; Ankur Moitra; Andrej Risteski (NeurIPS, 2023)

Robust Voting Rules from Algorithmic Robust Statistics. - Allen Liu; Ankur Moitra (SODA, 2023)

A New Approach to Learning Linear Dynamical Systems. - Ainesh Bakshi; Allen Liu; Ankur Moitra; Morris Yau (STOC, 2023)

Planning and Learning in Partially Observable Systems via Filter Stability. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (STOC, 2023)

Robustly Learning General Mixtures of Gaussians. - Allen Liu; Ankur Moitra (J. ACM, 2023)

The power of an adversary in Glauber dynamics. - Byron Chin; Ankur Moitra; Elchanan Mossel; Colin Sandon (COLT, 2024)

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions. - Noah Golowich; Ankur Moitra (COLT, 2024)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable. - Ainesh Bakshi; Allen Liu; Ankur Moitra; Ewin Tang (FOCS, 2024)

Structure Learning of Hamiltonians from Real-Time Evolution. - Ainesh Bakshi; Allen Liu; Ankur Moitra; Ewin Tang (FOCS, 2024)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (FOCS, 2024)

Edit Distance Robust Watermarks via Indexing Pseudorandom Codes. - Noah Golowich; Ankur Moitra (NeurIPS, 2024)

The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation. - Noah Golowich; Ankur Moitra (RLJ, 2024)

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time. - Ainesh Bakshi; Allen Liu; Ankur Moitra; Ewin Tang (STOC, 2024)

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (STOC, 2024)

On Learning Parities with Dependent Noise. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (CoRR, 2024)

Efficiently Learning Markov Random Fields from Dynamics. - Jason Gaitonde; Ankur Moitra; Elchanan Mossel (CoRR, 2024)

Towards characterizing the value of edge embeddings in Graph Neural Networks. - Dhruv Rohatgi; Tanya Marwah; Zachary Chase Lipton; Jianfeng Lu 001; Ankur Moitra; Andrej Risteski (CoRR, 2024)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings. - Pravesh K. Kothari; Ankur Moitra; Alexander S. Wein (CoRR, 2024)

Edit Distance Robust Watermarks for Language Models. - Noah Golowich; Ankur Moitra (IACR Cryptol. ePrint Arch., 2024)

Fast Sampling of Satisfying Assignments from Random ( boldsymbol{k} )-SAT with Applications to Connectivity. - Zongchen Chen; Andreas Galanis; Leslie Ann Goldberg; Heng Guo 001; Andrés Herrera-Poyatos; Nitya Mani; Ankur Moitra (SIAM J. Discret. Math., 2024)

Conference on Learning Theory 2025: Preface. - Nika Haghtalab; Ankur Moitra (COLT, 2025)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics. - Jason Gaitonde; Ankur Moitra; Elchanan Mossel (STOC, 2025)

Model Stealing for Any Low-Rank Language Model. - Allen Liu; Ankur Moitra (STOC, 2025)

Better Models and Algorithms for Learning Ising Models from Dynamics. - Jason Gaitonde; Ankur Moitra; Elchanan Mossel (CoRR, 2025)