# Ankur Moitra

According to our database

Collaborative distances:

^{1}, Ankur Moitra authored at least 52 papers between 2008 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Improved Bounds for Randomly Sampling Colorings via Linear Programming.

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

The Paulsen Problem Made Simple.

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

2018

Learning topic models - provably and efficiently.

Commun. ACM, 2018

Robustness Meets Algorithms (Invited Talk).

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

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

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

Efficiently Learning Mixtures of Mallows Models.

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

2017

Approximate counting, the Lovasz local lemma, and inference in graphical models.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

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

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.

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

Being Robust (in High Dimensions) Can Be Practical.

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

Rates of estimation for determinantal point processes.

Proceedings of the 30th Conference on Learning Theory, 2017

2016

How robust are reconstruction thresholds for community detection?

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

Provable Algorithms for Inference in Topic Models.

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

Robust Estimators in High Dimensions without the Computational Intractability.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

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

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Noisy Tensor Completion via the Sum-of-Squares Hierarchy.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

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

Algorithmica, 2015

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

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

Nonnegative Matrix Factorization: Algorithms, Complexity and Applications.

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

Beyond Matrix Completion (Invited Talk).

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.

Proceedings of The 28th Conference on Learning Theory, 2015

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.

Proceedings of the Approximation, 2015

2014

Efficient Coding for Interactive Communication.

IEEE Trans. Information Theory, 2014

Smoothed analysis of tensor decompositions.

Proceedings of the Symposium on Theory of Computing, 2014

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

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

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

Proceedings of The 27th Conference on Learning Theory, 2014

New Algorithms for Learning Incoherent and Overcomplete Dictionaries.

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Vertex Sparsification and Oblivious Reductions.

SIAM J. Comput., 2013

An information complexity approach to extended formulations.

Proceedings of the Symposium on Theory of Computing Conference, 2013

An Almost Optimal Algorithm for Computing Nonnegative Rank.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

A Practical Algorithm for Topic Modeling with Provable Guarantees.

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

A Polynomial Time Algorithm for Lossy Population Recovery.

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

Algorithms and Hardness for Robust Subspace Recovery.

Proceedings of the COLT 2013, 2013

2012

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Disentangling Gaussians.

Commun. ACM, 2012

Computing a nonnegative matrix factorization - provably.

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

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

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

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

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.

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

2011

Vertex sparsification and universal rounding algorithms.

PhD thesis, 2011

Efficiently Coding for Interactive Communication.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Pareto optimal solutions for smoothed analysts.

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

Dueling algorithms.

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

Capacitated Metric Labeling.

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

Efficient and Explicit Coding for Interactive Communication.

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

2010

Some Results on Greedy Embeddings in Metric Spaces.

Discrete & Computational Geometry, 2010

Extensions and limits to vertex sparsification.

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

Efficiently learning mixtures of two Gaussians.

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

Settling the Polynomial Learnability of Mixtures of Gaussians.

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

Vertex Sparsifiers and Abstract Rounding Algorithms.

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.

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

2008

Some Results on Greedy Embeddings in Metric Spaces.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008