Ankur Moitra

According to our database, Ankur Moitra authored at least 120 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Fast Sampling of Satisfying Assignments from Random \(\boldsymbol{k}\)-SAT with Applications to Connectivity.

Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andrés Herrera-Poyatos, Nitya Mani, Ankur Moitra

SIAM J. Discret. Math., 2024

Edit Distance Robust Watermarks for Language Models.

Noah Golowich, Ankur Moitra

IACR Cryptol. ePrint Arch., 2024

Overcomplete Tensor Decomposition via Koszul-Young Flattenings.

Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein

CoRR, 2024

Model Stealing for Any Low-Rank Language Model.

Allen Liu, Ankur Moitra

CoRR, 2024

Towards characterizing the value of edge embeddings in Graph Neural Networks.

Dhruv Rohatgi, Tanya Marwah, Zachary Chase Lipton, Jianfeng Lu, Ankur Moitra, Andrej Risteski

CoRR, 2024

Efficiently Learning Markov Random Fields from Dynamics.

Jason Gaitonde, Ankur Moitra, Elchanan Mossel

CoRR, 2024

On Learning Parities with Dependent Noise.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

CoRR, 2024

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation.

Noah Golowich, Ankur Moitra

RLJ, 2024

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Structure Learning of Hamiltonians from Real-Time Evolution.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

High-Temperature Gibbs States are Unentangled and Efficiently Preparable.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions.

Noah Golowich, Ankur Moitra

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

The power of an adversary in Glauber dynamics.

Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Robustly Learning General Mixtures of Gaussians.

Allen Liu, Ankur Moitra

J. ACM, June, 2023

Planning and Learning in Partially Observable Systems via Filter Stability.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A New Approach to Learning Linear Dynamical Systems.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Robust Voting Rules from Algorithmic Robust Statistics.

Allen Liu, Ankur Moitra

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Provable benefits of score matching.

Chirag Pabbaraju, Dhruv Rohatgi, Anish Prasad Sevekari, Holden Lee, Ankur Moitra, Andrej Risteski

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau

Proceedings of the International Conference on Machine Learning, 2023

Provably Auditing Ordinary Least Squares in Low Dimensions.

Ankur Moitra, Dhruv Rohatgi

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Distilling Model Failures as Directions in Latent Space.

Saachi Jain, Hannah Lawrence, Ankur Moitra, Aleksander Madry

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications.

Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Noisy tensor completion via the sum-of-squares hierarchy.

Boaz Barak, Ankur Moitra

Math. Program., 2022

From algorithms to connectivity and back: finding a giant component in random k-SAT.

Zongchen Chen, Nitya Mani, Ankur Moitra

CoRR, 2022

Planning in Observable POMDPs in Quasipolynomial Time.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

CoRR, 2022

Kalman filtering with adversarial corruptions.

Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Robust Model Selection and Nearly-Proper Learning for GMMs.

Allen Liu, Jerry Li, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Learning in Observable POMDPs, without Computationally Intractable Oracles.

Noah Golowich, Ankur Moitra, Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Polynomial time guarantees for the Burer-Monteiro method.

Diego Cifuentes, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Minimax Rates for Robust Community Detection.

Allen Liu, Ankur Moitra

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Learning GMMs with Nearly Optimal Robustness Guarantees.

Allen Liu, Ankur Moitra

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Can Q-learning be Improved with Advice?

Noah Golowich, Ankur Moitra

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Spoofing Generalization: When Can't You Trust Proprietary Models?

Ankur Moitra, Elchanan Mossel, Colin Sandon

CoRR, 2021

Sparsification for Sums of Exponentials and its Algorithmic Applications.

Jerry Li, Allen Liu, Ankur Moitra

CoRR, 2021

How to Decompose a Tensor with Group Structure.

Allen Liu, Ankur Moitra

CoRR, 2021

No-go Theorem for Acceleration in the Hyperbolic Plane.

Linus Hamilton, Ankur Moitra

CoRR, 2021

Robustness meets algorithms.

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Commun. ACM, 2021

Settling the robust learnability of mixtures of Gaussians.

Allen Liu, Ankur Moitra

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Algorithmic foundations for the diffraction limit.

Sitan Chen, Ankur Moitra

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A No-go Theorem for Robust Acceleration in the Hyperbolic Plane.

Linus Hamilton, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination.

Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Learning to Sample from Censored Markov Random Fields.

Ankur Moitra, Elchanan Mossel, Colin Sandon

Proceedings of the Conference on Learning Theory, 2021

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

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability.

Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau

CoRR, 2020

Fast Convergence for Langevin Diffusion with Matrix Manifold Structure.

Ankur Moitra, Andrej Risteski

CoRR, 2020

Efficiently learning structured distributions from untrusted batches.

Sitan Chen, Jerry Li, Ankur Moitra

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Tensor Completion Made Practical.

Allen Liu, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability.

Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning Structured Distributions From Untrusted Batches: Faster and Simpler.

Sitan Chen, Jerry Li, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Parallels Between Phase Transitions and Circuit Complexity?

Ankur Moitra, Elchanan Mossel, Colin Sandon

Proceedings of the Conference on Learning Theory, 2020

Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation.

Allen Liu, Ankur Moitra

Proceedings of the Conference on Learning Theory, 2020

Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion.

William Cole Franks, Ankur Moitra

Proceedings of the Conference on Learning Theory, 2020

Semirandom Stochastic Block Models.

Ankur Moitra

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

Topic Models and Nonnegative Matrix Factorization.

Rong Ge, Ankur Moitra

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Spectral Methods from Tensor Networks.

Ankur Moitra, Alexander S. Wein

SIAM J. Comput., 2019

Robust Estimators in High-Dimensions Without the Computational Intractability.

Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart

SIAM J. Comput., 2019

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

SIAM J. Comput., 2019

Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models.

Ankur Moitra

J. ACM, 2019

The Circuit Complexity of Inference.

Ankur Moitra, Elchanan Mossel, Colin Sandon

CoRR, 2019

Beyond the low-degree algorithm: mixtures of subcubes and their applications.

Sitan Chen, Ankur Moitra

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Learning restricted Boltzmann machines via influence maximization.

Guy Bresler, Frederic Koehler, Ankur Moitra

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Improved Bounds for Randomly Sampling Colorings via Linear Programming.

Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Paulsen Problem Made Simple.

Linus Hamilton, Ankur Moitra

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models.

Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra

CoRR, 2018

Learning Restricted Boltzmann Machines via Influence Maximization.

Guy Bresler, Frederic Koehler, Ankur Moitra, Elchanan Mossel

CoRR, 2018

Linear Programming Bounds for Randomly Sampling Colorings.

Sitan Chen, Ankur Moitra

CoRR, 2018

Learning Mixtures of Product Distributions via Higher Multilinear Moments.

Sitan Chen, Ankur Moitra

CoRR, 2018

Learning topic models - provably and efficiently.

Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu

Commun. ACM, 2018

Robustness Meets Algorithms (Invited Talk).

Ankur Moitra

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Efficiently Learning Mixtures of Mallows Models.

Allen Liu, Ankur Moitra

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications.

Linus Hamilton, Frederic Koehler, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Learning Determinantal Point Processes with Moments and Cycles.

John C. Urschel, Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet

Proceedings of the 34th International Conference on Machine Learning, 2017

Being Robust (in High Dimensions) Can Be Practical.

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Proceedings of the 34th International Conference on Machine Learning, 2017

Rates of estimation for determinantal point processes.

Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, John C. Urschel

Proceedings of the 30th Conference on Learning Theory, 2017

2016

An Almost Optimal Algorithm for Computing Nonnegative Rank.

Ankur Moitra

SIAM J. Comput., 2016

Computing a Nonnegative Matrix Factorization - Provably.

Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

SIAM J. Comput., 2016

Message-passing algorithms for synchronization problems over compact groups.

Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra

CoRR, 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

How robust are reconstruction thresholds for community detection?

Ankur Moitra, William Perry, Alexander S. Wein

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Provable Algorithms for Inference in Topic Models.

Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Tensor Prediction, Rademacher Complexity and Random 3-XOR.

Boaz Barak, Ankur Moitra

CoRR, 2015

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders.

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Algorithmica, 2015

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices.

Ankur Moitra

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Nonnegative Matrix Factorization: Algorithms, Complexity and Applications.

Ankur Moitra

Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, 2015

Beyond Matrix Completion (Invited Talk).

Ankur Moitra

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Simple, Efficient, and Neural Algorithms for Sparse Coding.

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Efficient Coding for Interactive Communication.

Ran Gelles, Ankur Moitra, Amit Sahai

IEEE Trans. Inf. Theory, 2014

The Threshold for Super-resolution via Extremal Functions.

Ankur Moitra

CoRR, 2014

Smoothed analysis of tensor decompositions.

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

Proceedings of the Symposium on Theory of Computing, 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.

Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?

Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan

Proceedings of The 27th Conference on Learning Theory, 2014

New Algorithms for Learning Incoherent and Overcomplete Dictionaries.

Sanjeev Arora, Rong Ge, Ankur Moitra

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Vertex Sparsification and Oblivious Reductions.

Ankur Moitra

SIAM J. Comput., 2013

A Practical Algorithm for Topic Modeling with Provable Guarantees.

Sanjeev Arora, Rong Ge, Yonatan Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu

Proceedings of the 30th International Conference on Machine Learning, 2013

A Polynomial Time Algorithm for Lossy Population Recovery.

Ankur Moitra, Michael E. Saks

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Algorithms and Hardness for Robust Subspace Recovery.

Moritz Hardt, Ankur Moitra

Proceedings of the COLT 2013, 2013

2012

Pareto Optimal Solutions for Smoothed Analysts.

Ankur Moitra, Ryan O'Donnell

SIAM J. Comput., 2012

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank.

Ankur Moitra

Electron. Colloquium Comput. Complex., 2012

An Information Complexity Approach to Extended Formulations.

Mark Braverman, Ankur Moitra

Electron. Colloquium Comput. Complex., 2012

Can We Reconcile Robustness and Efficiency in Unsupervised Learning?

Moritz Hardt, Ankur Moitra

CoRR, 2012

Disentangling Gaussians.

Adam Tauman Kalai, Ankur Moitra, Gregory Valiant

Commun. ACM, 2012

Nearly complete graphs decomposable into large induced matchings and their applications.

Noga Alon, Ankur Moitra, Benny Sudakov

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders".

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

Learning Topic Models - Going beyond SVD.

Sanjeev Arora, Rong Ge, Ankur Moitra

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Vertex sparsification and universal rounding algorithms.

Ankur Moitra

PhD thesis, 2011

Efficiently Coding for Interactive Communication.

Ankur Moitra

Electron. Colloquium Comput. Complex., 2011

Dueling algorithms.

Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Capacitated Metric Labeling.

Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Ankur Moitra

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Efficient and Explicit Coding for Interactive Communication.

Ran Gelles, Ankur Moitra, Amit Sahai

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Some Results on Greedy Embeddings in Metric Spaces.

Tom Leighton, Ankur Moitra

Discret. Comput. Geom., 2010

Extensions and limits to vertex sparsification.

Frank Thomson Leighton, Ankur Moitra

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Efficiently learning mixtures of two Gaussians.

Adam Tauman Kalai, Ankur Moitra, Gregory Valiant

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Settling the Polynomial Learnability of Mixtures of Gaussians.

Ankur Moitra, Gregory Valiant

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms.

Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size.

Ankur Moitra

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009