Ankur Moitra

According to our database1, Ankur Moitra authored at least 100 papers between 2008 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2019
Robust Estimators in High-Dimensions Without the Computational Intractability.
SIAM J. Comput., 2019

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
SIAM J. Comput., 2019

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

The Circuit Complexity of Inference.
CoRR, 2019

Improved Bounds for Randomly Sampling Colorings via Linear Programming.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories.
Proceedings of the Research in Computational Molecular Biology, 2019

The Paulsen Problem Made Simple.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018
Spectral Methods from Tensor Networks.
CoRR, 2018

Improved Bounds for Randomly Sampling Colorings via Linear Programming.
CoRR, 2018

The Paulsen Problem Made Simple.
CoRR, 2018

Efficiently Learning Mixtures of Mallows Models.
CoRR, 2018

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

Learning Restricted Boltzmann Machines via Influence Maximization.
CoRR, 2018

Linear Programming Bounds for Randomly Sampling Colorings.
CoRR, 2018

Learning Mixtures of Product Distributions via Higher Multilinear Moments.
CoRR, 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
Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications.
CoRR, 2017

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.
CoRR, 2017

Being Robust (in High Dimensions) Can Be Practical.
CoRR, 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
An Almost Optimal Algorithm for Computing Nonnegative Rank.
SIAM J. Comput., 2016

Computing a Nonnegative Matrix Factorization - Provably.
SIAM J. Comput., 2016

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Message-passing algorithms for synchronization problems over compact groups.
CoRR, 2016

Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization.
CoRR, 2016

Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models.
CoRR, 2016

Robust Estimators in High Dimensions without the Computational Intractability.
CoRR, 2016

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

Provable Algorithms for Inference in Topic Models.
CoRR, 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
Beating the random assignment on constraint satisfaction problems of bounded degree.
Electronic Colloquium on Computational Complexity (ECCC), 2015

How Robust are Reconstruction Thresholds for Community Detection?
CoRR, 2015

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

Tensor Prediction, Rademacher Complexity and Random 3-XOR.
CoRR, 2015

Simple, Efficient, and Neural Algorithms for Sparse Coding.
CoRR, 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

The Threshold for Super-resolution via Extremal Functions.
CoRR, 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

A Polynomial Time Algorithm for Lossy Population Recovery
CoRR, 2013

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

Smoothed Analysis of Tensor Decompositions.
CoRR, 2013

New Algorithms for Learning Incoherent and Overcomplete Dictionaries.
CoRR, 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
Pareto Optimal Solutions for Smoothed Analysts.
SIAM J. Comput., 2012

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank.
Electronic Colloquium on Computational Complexity (ECCC), 2012

An Information Complexity Approach to Extended Formulations.
Electronic Colloquium on Computational Complexity (ECCC), 2012

A Practical Algorithm for Topic Modeling with Provable Guarantees
CoRR, 2012

Can We Reconcile Robustness and Efficiency in Unsupervised Learning?
CoRR, 2012

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

A Singly-Exponential Time Algorithm for Computing Nonnegative Rank
CoRR, 2012

Learning Topic Models - Going beyond SVD
CoRR, 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

Computing a Nonnegative Matrix Factorization -- Provably
CoRR, 2011

Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
CoRR, 2011

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

Pareto Optimal Solutions for Smoothed Analysts
CoRR, 2010

Vertex Sparsifiers and Abstract Rounding Algorithms
CoRR, 2010

Settling the Polynomial Learnability of Mixtures of Gaussians
CoRR, 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


  Loading...