default search action
Ankur Moitra
Person information
- affiliation: Massachusetts Institute of Technology, MA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j18]Noah Golowich, Ankur Moitra:
The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation. RLJ 1: 302-341 (2024) - [j17]Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andrés Herrera-Poyatos, Nitya Mani, Ankur Moitra:
Fast Sampling of Satisfying Assignments from Random \(\boldsymbol{k}\)-SAT with Applications to Connectivity. SIAM J. Discret. Math. 38(4): 2750-2811 (2024) - [c82]Byron Chin, Ankur Moitra, Elchanan Mossel, Colin Sandon:
The power of an adversary in Glauber dynamics. COLT 2024: 1102-1124 - [c81]Noah Golowich, Ankur Moitra:
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions. COLT 2024: 1939-1981 - [c80]Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
High-Temperature Gibbs States are Unentangled and Efficiently Preparable. FOCS 2024: 1027-1036 - [c79]Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
Structure Learning of Hamiltonians from Real-Time Evolution. FOCS 2024: 1037-1050 - [c78]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. FOCS 2024: 1953-1967 - [c77]Noah Golowich
, Ankur Moitra
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. STOC 2024: 183-193 - [c76]Ainesh Bakshi
Learning Quantum Hamiltonians at Any Temperature in Polynomial Time. STOC 2024: 1470-1477 - [i84]Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
High-Temperature Gibbs States are Unentangled and Efficiently Preparable. CoRR abs/2403.16850 (2024) - [i83]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. CoRR abs/2404.03774 (2024) - [i82]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
On Learning Parities with Dependent Noise. CoRR abs/2404.11325 (2024) - [i81]Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
Structure learning of Hamiltonians from real-time evolution. CoRR abs/2405.00082 (2024) - [i80]Noah Golowich, Ankur Moitra:
Edit Distance Robust Watermarks for Language Models. CoRR abs/2406.02633 (2024) - [i79]Noah Golowich, Ankur Moitra:
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions. CoRR abs/2406.11640 (2024) - [i78]Noah Golowich, Ankur Moitra:
The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation. CoRR abs/2406.11686 (2024) - [i77]Jason Gaitonde, Ankur Moitra, Elchanan Mossel:
Efficiently Learning Markov Random Fields from Dynamics. CoRR abs/2409.05284 (2024) - [i76]Dhruv Rohatgi, Tanya Marwah, Zachary Chase Lipton, Jianfeng Lu, Ankur Moitra, Andrej Risteski:
Towards characterizing the value of edge embeddings in Graph Neural Networks. CoRR abs/2410.09867 (2024) - [i75]Noah Golowich, Ankur Moitra:
Edit Distance Robust Watermarks for Language Models. IACR Cryptol. ePrint Arch. 2024: 898 (2024) - 2023
- [j16]Allen Liu
Robustly Learning General Mixtures of Gaussians. J. ACM 70(3): 21:1-21:53 (2023) - [c75]Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra:
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. FOCS 2023: 810-845 - [c74]Saachi Jain, Hannah Lawrence, Ankur Moitra, Aleksander Madry:
Distilling Model Failures as Directions in Latent Space. ICLR 2023 - [c73]Ankur Moitra, Dhruv Rohatgi:
Provably Auditing Ordinary Least Squares in Low Dimensions. ICLR 2023 - [c72]Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau:
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems. ICML 2023: 1549-1563 - [c71]Chirag Pabbaraju, Dhruv Rohatgi, Anish Prasad Sevekari, Holden Lee, Ankur Moitra, Andrej Risteski:
Provable benefits of score matching. NeurIPS 2023 - [c70]Allen Liu, Ankur Moitra:
Robust Voting Rules from Algorithmic Robust Statistics. SODA 2023: 3471-3512 - [c69]Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau:
A New Approach to Learning Linear Dynamical Systems. STOC 2023: 335-348 - [c68]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Planning and Learning in Partially Observable Systems via Filter Stability. STOC 2023: 349-362 - [i74]Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau:
A New Approach to Learning Linear Dynamical Systems. CoRR abs/2301.09519 (2023) - [i73]Zongchen Chen, Kuikui Liu, Nitya Mani, Ankur Moitra:
Strong spatial mixing for colorings on trees and its algorithmic applications. CoRR abs/2304.01954 (2023) - [i72]Chirag Pabbaraju, Dhruv Rohatgi, Anish Prasad Sevekari, Holden Lee, Ankur Moitra, Andrej Risteski:
Provable benefits of score matching. CoRR abs/2306.01993 (2023) - [i71]Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau:
Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems. CoRR abs/2307.06538 (2023) - [i70]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. CoRR abs/2309.09457 (2023) - [i69]Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang:
Learning quantum Hamiltonians at any temperature in polynomial time. CoRR abs/2310.02243 (2023) - 2022
- [j15]Boaz Barak, Ankur Moitra:
Noisy tensor completion via the sum-of-squares hierarchy. Math. Program. 193(2): 513-548 (2022) - [c67]Allen Liu, Ankur Moitra:
Learning GMMs with Nearly Optimal Robustness Guarantees. COLT 2022: 2815-2895 - [c66]Noah Golowich, Ankur Moitra:
Can Q-learning be Improved with Advice? COLT 2022: 4548-4619 - [c65]Allen Liu, Ankur Moitra:
Minimax Rates for Robust Community Detection. FOCS 2022: 823-831 - [c64]Diego Cifuentes, Ankur Moitra:
Polynomial time guarantees for the Burer-Monteiro method. NeurIPS 2022 - [c63]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Learning in Observable POMDPs, without Computationally Intractable Oracles. NeurIPS 2022 - [c62]Allen Liu, Jerry Li, Ankur Moitra:
Robust Model Selection and Nearly-Proper Learning for GMMs. NeurIPS 2022 - [c61]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Kalman filtering with adversarial corruptions. STOC 2022: 832-845 - [i68]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Planning in Observable POMDPs in Quasipolynomial Time. CoRR abs/2201.04735 (2022) - [i67]Ankur Moitra, Dhruv Rohatgi:
Provably Auditing Ordinary Least Squares in Low Dimensions. CoRR abs/2205.14284 (2022) - [i66]Noah Golowich, Ankur Moitra, Dhruv Rohatgi:
Learning in Observable POMDPs, without Computationally Intractable Oracles. CoRR abs/2206.03446 (2022) - [i65]Saachi Jain, Hannah Lawrence, Ankur Moitra, Aleksander Madry:
Distilling Model Failures as Directions in Latent Space. CoRR abs/2206.14754 (2022) - [i64]Zongchen Chen, Nitya Mani, Ankur Moitra:
From algorithms to connectivity and back: finding a giant component in random k-SAT. CoRR abs/2207.02841 (2022) - [i63]Allen Liu, Ankur Moitra:
Minimax Rates for Robust Community Detection. CoRR abs/2207.11903 (2022) - 2021
- [j14]Ilias Diakonikolas, Gautam Kamath
Robustness meets algorithms. Commun. ACM 64(5): 107-115 (2021) - [c60]Ankur Moitra, Elchanan Mossel, Colin Sandon:
Learning to Sample from Censored Markov Random Fields. COLT 2021: 3419-3451 - [c59]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. FOCS 2021: 684-695 - [c58]Linus Hamilton, Ankur Moitra:
A No-go Theorem for Robust Acceleration in the Hyperbolic Plane. NeurIPS 2021: 3914-3924 - [c57]Sitan Chen, Ankur Moitra:
Algorithmic foundations for the diffraction limit. STOC 2021: 490-503 - [c56]Allen Liu, Ankur Moitra:
Settling the robust learnability of mixtures of Gaussians. STOC 2021: 518-531 - [i62]Linus Hamilton, Ankur Moitra:
No-go Theorem for Acceleration in the Hyperbolic Plane. CoRR abs/2101.05657 (2021) - [i61]Ankur Moitra, Elchanan Mossel, Colin Sandon:
Learning to Sample from Censored Markov Random Fields. CoRR abs/2101.06178 (2021) - [i60]Allen Liu, Ankur Moitra:
Learning GMMs with Nearly Optimal Robustness Guarantees. CoRR abs/2104.09665 (2021) - [i59]Allen Liu, Ankur Moitra:
How to Decompose a Tensor with Group Structure. CoRR abs/2106.02680 (2021) - [i58]Jerry Li, Allen Liu, Ankur Moitra:
Sparsification for Sums of Exponentials and its Algorithmic Applications. CoRR abs/2106.02774 (2021) - [i57]Ankur Moitra, Elchanan Mossel, Colin Sandon:
Spoofing Generalization: When Can't You Trust Proprietary Models? CoRR abs/2106.08393 (2021) - [i56]Noah Golowich, Ankur Moitra:
Can Q-Learning be Improved with Advice? CoRR abs/2110.13052 (2021) - [i55]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Kalman Filtering with Adversarial Corruptions. CoRR abs/2111.06395 (2021) - [i54]Allen Liu, Ankur Moitra:
Robust Voting Rules from Algorithmic Robust Statistics. CoRR abs/2112.06380 (2021) - 2020
- [j13]Younhun Kim, Frederic Koehler, Ankur Moitra, Elchanan Mossel, Govind Ramnarayan:
How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories. J. Comput. Biol. 27(4): 613-625 (2020) - [c55]William Cole Franks, Ankur Moitra:
Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion. COLT 2020: 1601-1632 - [c54]Allen Liu, Ankur Moitra:
Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation. COLT 2020: 2780-2829 - [c53]Ankur Moitra, Elchanan Mossel, Colin Sandon:
Parallels Between Phase Transitions and Circuit Complexity? COLT 2020: 2910-2946 - [c52]Sitan Chen, Jerry Li, Ankur Moitra:
Learning Structured Distributions From Untrusted Batches: Faster and Simpler. NeurIPS 2020 - [c51]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Evolvability. NeurIPS 2020 - [c50]Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra:
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. NeurIPS 2020 - [c49]Allen Liu, Ankur Moitra:
Tensor Completion Made Practical. NeurIPS 2020 - [c48]Sitan Chen, Jerry Li, Ankur Moitra:
Efficiently learning structured distributions from untrusted batches. STOC 2020: 960-973 - [p2]Ankur Moitra:
Semirandom Stochastic Block Models. Beyond the Worst-Case Analysis of Algorithms 2020: 212-233 - [p1]Rong Ge, Ankur Moitra:
Topic Models and Nonnegative Matrix Factorization. Beyond the Worst-Case Analysis of Algorithms 2020: 445-464 - [i53]Cole Franks, Ankur Moitra:
Rigorous Guarantees for Tyler's M-estimator via quantum expansion. CoRR abs/2002.00071 (2020) - [i52]Ankur Moitra, Andrej Risteski:
Fast Convergence for Langevin Diffusion with Matrix Manifold Structure. CoRR abs/2002.05576 (2020) - [i51]Sitan Chen, Jerry Li, Ankur Moitra:
Learning Structured Distributions From Untrusted Batches: Faster and Simpler. CoRR abs/2002.10435 (2020) - [i50]Sitan Chen, Ankur Moitra:
Algorithmic Foundations for the Diffraction Limit. CoRR abs/2004.07659 (2020) - [i49]Allen Liu, Ankur Moitra:
Tensor Completion Made Practical. CoRR abs/2006.03134 (2020) - [i48]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability. CoRR abs/2006.04787 (2020) - [i47]Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. CoRR abs/2010.04157 (2020) - [i46]Allen Liu, Ankur Moitra:
Settling the Robust Learnability of Mixtures of Gaussians. CoRR abs/2011.03622 (2020)
2010 – 2019
- 2019
- [j12]Ankur Moitra:
Approximate Counting, the Lovász Local Lemma, and Inference in Graphical Models. J. ACM 66(2): 10:1-10:25 (2019) - [j11]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. 48(2): 687-735 (2019) - [j10]Ilias Diakonikolas, Gautam Kamath
Robust Estimators in High-Dimensions Without the Computational Intractability. SIAM J. Comput. 48(2): 742-864 (2019) - [c47]Linus Hamilton, Ankur Moitra:
The Paulsen Problem Made Simple. ITCS 2019: 41:1-41:6 - [c46]Younhun Kim, Frederic Koehler, Ankur Moitra, Elchanan Mossel, Govind Ramnarayan:
How Many Subpopulations Is Too Many? Exponential Lower Bounds for Inferring Population Histories. RECOMB 2019: 136-157 - [c45]Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle:
Improved Bounds for Randomly Sampling Colorings via Linear Programming. SODA 2019: 2216-2234 - [c44]Guy Bresler, Frederic Koehler, Ankur Moitra:
Learning restricted Boltzmann machines via influence maximization. STOC 2019: 828-839 - [c43]Sitan Chen, Ankur Moitra:
Beyond the low-degree algorithm: mixtures of subcubes and their applications. STOC 2019: 869-880 - [c42]Ankur Moitra, Alexander S. Wein:
Spectral methods from tensor networks. STOC 2019: 926-937 - [i45]Ankur Moitra, Elchanan Mossel, Colin Sandon:
The Circuit Complexity of Inference. CoRR abs/1904.05483 (2019) - [i44]Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra:
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. CoRR abs/1905.01282 (2019) - [i43]Sitan Chen, Jerry Li, Ankur Moitra:
Efficiently Learning Structured Distributions from Untrusted Batches. CoRR abs/1911.02035 (2019) - 2018
- [j9]Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
Learning topic models - provably and efficiently. Commun. ACM 61(4): 85-93 (2018) - [c41]Allen Liu, Ankur Moitra:
Efficiently Learning Mixtures of Mallows Models. FOCS 2018: 627-638 - [c40]Ilias Diakonikolas, Gautam Kamath
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. SODA 2018: 2683-2702 - [c39]Ankur Moitra:
Robustness Meets Algorithms (Invited Talk). SWAT 2018: 3:1-3:1 - [i42]Sitan Chen, Ankur Moitra:
Learning Mixtures of Product Distributions via Higher Multilinear Moments. CoRR abs/1803.06521 (2018) - [i41]Sitan Chen, Ankur Moitra:
Linear Programming Bounds for Randomly Sampling Colorings. CoRR abs/1804.03156 (2018) - [i40]Guy Bresler, Frederic Koehler, Ankur Moitra, Elchanan Mossel:
Learning Restricted Boltzmann Machines via Influence Maximization. CoRR abs/1805.10262 (2018) - [i39]Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra:
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models. CoRR abs/1807.00891 (2018) - [i38]Allen Liu, Ankur Moitra:
Efficiently Learning Mixtures of Mallows Models. CoRR abs/1808.05731 (2018) - [i37]Linus Hamilton, Ankur Moitra:
The Paulsen Problem Made Simple. CoRR abs/1809.04726 (2018) - [i36]Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle:
Improved Bounds for Randomly Sampling Colorings via Linear Programming. CoRR abs/1810.12980 (2018) - [i35]Ankur Moitra, Alexander S. Wein:
Spectral Methods from Tensor Networks. CoRR abs/1811.00944 (2018) - 2017
- [c38]Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, John C. Urschel:
Rates of estimation for determinantal point processes. COLT 2017: 343-345 - [c37]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Being Robust (in High Dimensions) Can Be Practical. ICML 2017: 999-1008 - [c36]John C. Urschel, Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet:
Learning Determinantal Point Processes with Moments and Cycles. ICML 2017: 3511-3520 - [c35]Linus Hamilton, Frederic Koehler, Ankur Moitra:
Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications. NIPS 2017: 2463-2472 - [c34]Ankur Moitra:
Approximate counting, the Lovasz local lemma, and inference in graphical models. STOC 2017: 356-369 - [i34]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Being Robust (in High Dimensions) Can Be Practical. CoRR abs/1703.00893 (2017) - [i33]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. CoRR abs/1704.03866 (2017) - [i32]Linus Hamilton, Frederic Koehler, Ankur Moitra:
Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications. CoRR abs/1705.11107 (2017) - 2016
- [j8]Ankur Moitra:
An Almost Optimal Algorithm for Computing Nonnegative Rank. SIAM J. Comput. 45(1): 156-173 (2016) - [j7]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization - Provably. SIAM J. Comput. 45(4): 1582-1611 (2016) - [c33]Boaz Barak, Ankur Moitra:
Noisy Tensor Completion via the Sum-of-Squares Hierarchy. COLT 2016: 417-445 - [c32]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS 2016: 428-437 - [c31]Ilias Diakonikolas, Gautam Kamath
Robust Estimators in High Dimensions without the Computational Intractability. FOCS 2016: 655-664 - [c30]Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra:
Provable Algorithms for Inference in Topic Models. ICML 2016: 2859-2867 - [c29]Ankur Moitra, William Perry, Alexander S. Wein:
How robust are reconstruction thresholds for community detection? STOC 2016: 828-841 - [i31]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR abs/1604.03084 (2016) - [i30]Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Ankur Moitra, Alistair Stewart:
Robust Estimators in High Dimensions without the Computational Intractability. CoRR abs/1604.06443 (2016) - [i29]Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra:
Provable Algorithms for Inference in Topic Models. CoRR abs/1605.08491 (2016) - [i28]Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra:
Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization. CoRR abs/1609.05573 (2016) - [i27]Ankur Moitra:
Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models. CoRR abs/1610.04317 (2016) - [i26]Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra:
Message-passing algorithms for synchronization problems over compact groups. CoRR abs/1610.04583 (2016) - [i25]Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j6]Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. Algorithmica 72(1): 215-236 (2015) - [c28]Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM 2015: 110-123 - [c27]Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra:
Simple, Efficient, and Neural Algorithms for Sparse Coding. COLT 2015: 113-149 - [c26]Ankur Moitra:
Beyond Matrix Completion (Invited Talk). FSTTCS 2015: 8-8 - [c25]Ankur Moitra:
Nonnegative Matrix Factorization: Algorithms, Complexity and Applications. ISSAC 2015: 15-16 - [c24]Ankur Moitra:
Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. STOC 2015: 821-830 - [i24]Boaz Barak, Ankur Moitra:
Tensor Prediction, Rademacher Complexity and Random 3-XOR. CoRR abs/1501.06521 (2015) - [i23]Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra:
Simple, Efficient, and Neural Algorithms for Sparse Coding. CoRR abs/1503.00778 (2015) - [i22]Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright:
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR abs/1505.03424 (2015) - [i21]Ankur Moitra, William Perry, Alexander S. Wein:
How Robust are Reconstruction Thresholds for Community Detection? CoRR abs/1511.01473 (2015) - [i20]Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright:
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j5]Ran Gelles, Ankur Moitra, Amit Sahai:
Efficient Coding for Interactive Communication. IEEE Trans. Inf. Theory 60(3): 1899-1913 (2014) - [c23]Sanjeev Arora, Rong Ge, Ankur Moitra:
New Algorithms for Learning Incoherent and Overcomplete Dictionaries. COLT 2014: 779-806 - [c22]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? COLT 2014: 1280-1282 - [c21]Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. SODA 2014: 628-644 - [c20]Aditya Bhaskara, Moses Charikar
Smoothed analysis of tensor decompositions. STOC 2014: 594-603 - [i19]Ankur Moitra:
The Threshold for Super-resolution via Extremal Functions. CoRR abs/1408.1681 (2014) - 2013
- [j4]Ankur Moitra:
Vertex Sparsification and Oblivious Reductions. SIAM J. Comput. 42(6): 2400-2423 (2013) - [c19]Moritz Hardt, Ankur Moitra:
Algorithms and Hardness for Robust Subspace Recovery. COLT 2013: 354-375 - [c18]Ankur Moitra, Michael E. Saks:
A Polynomial Time Algorithm for Lossy Population Recovery. FOCS 2013: 110-116 - [c17]Sanjeev Arora, Rong Ge, Yonatan Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
A Practical Algorithm for Topic Modeling with Provable Guarantees. ICML (2) 2013: 280-288 - [c16]Ankur Moitra:
An Almost Optimal Algorithm for Computing Nonnegative Rank. SODA 2013: 1454-1464 - [c15]Mark Braverman, Ankur Moitra:
An information complexity approach to extended formulations. STOC 2013: 161-170 - [i18]Ankur Moitra, Michael E. Saks:
A Polynomial Time Algorithm for Lossy Population Recovery. CoRR abs/1302.1515 (2013) - [i17]Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio:
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. CoRR abs/1307.3621 (2013) - [i16]Sanjeev Arora, Rong Ge, Ankur Moitra:
New Algorithms for Learning Incoherent and Overcomplete Dictionaries. CoRR abs/1308.6273 (2013) - [i15]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Smoothed Analysis of Tensor Decompositions. CoRR abs/1311.3651 (2013) - 2012
- [j3]Adam Tauman Kalai, Ankur Moitra, Gregory Valiant:
Disentangling Gaussians. Commun. ACM 55(2): 113-120 (2012) - [j2]Ankur Moitra, Ryan O'Donnell:
Pareto Optimal Solutions for Smoothed Analysts. SIAM J. Comput. 41(5): 1266-1284 (2012) - [c14]Sanjeev Arora, Rong Ge, Ankur Moitra:
Learning Topic Models - Going beyond SVD. FOCS 2012: 1-10 - [c13]Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva:
"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders". NIPS 2012: 2384-2392 - [c12]Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra:
Computing a nonnegative matrix factorization - provably. STOC 2012: 145-162 - [c11]Noga Alon, Ankur Moitra, Benny Sudakov:
Nearly complete graphs decomposable into large induced matchings and their applications. STOC 2012: 1079-1090 - [i14]Sanjeev Arora, Rong Ge, Ankur Moitra:
Learning Topic Models - Going beyond SVD. CoRR abs/1204.1956 (2012) - [i13]Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. CoRR abs/1205.0044 (2012) - [i12]Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva:
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. CoRR abs/1206.5349 (2012) - [i11]Moritz Hardt, Ankur Moitra:
Can We Reconcile Robustness and Efficiency in Unsupervised Learning? CoRR abs/1211.1041 (2012) - [i10]Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
A Practical Algorithm for Topic Modeling with Provable Guarantees. CoRR abs/1212.4777 (2012) - [i9]Mark Braverman, Ankur Moitra:
An Information Complexity Approach to Extended Formulations. Electron. Colloquium Comput. Complex. TR12 (2012) - [i8]Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [b1]Ankur Moitra:
Vertex sparsification and universal rounding algorithms. Massachusetts Institute of Technology, Cambridge, MA, USA, 2011 - [c10]Ran Gelles, Ankur Moitra, Amit Sahai:
Efficient and Explicit Coding for Interactive Communication. FOCS 2011: 768-777 - [c9]Matthew Andrews, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Ankur Moitra:
Capacitated Metric Labeling. SODA 2011: 976-995 - [c8]Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz:
Dueling algorithms. STOC 2011: 215-224 - [c7]Ankur Moitra, Ryan O'Donnell:
Pareto optimal solutions for smoothed analysts. STOC 2011: 225-234 - [i7]Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz:
Dueling Algorithms. CoRR abs/1101.2883 (2011) - [i6]Noga Alon, Ankur Moitra, Benny Sudakov:
Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications. CoRR abs/1111.0253 (2011) - [i5]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization -- Provably. CoRR abs/1111.0952 (2011) - [i4]Ankur Moitra:
Efficiently Coding for Interactive Communication. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j1]Tom Leighton, Ankur Moitra:
Some Results on Greedy Embeddings in Metric Spaces. Discret. Comput. Geom. 44(3): 686-705 (2010) - [c6]Ankur Moitra, Gregory Valiant:
Settling the Polynomial Learnability of Mixtures of Gaussians. FOCS 2010: 93-102 - [c5]Moses Charikar
Vertex Sparsifiers and Abstract Rounding Algorithms. FOCS 2010: 265-274 - [c4]Frank Thomson Leighton, Ankur Moitra:
Extensions and limits to vertex sparsification. STOC 2010: 47-56 - [c3]Adam Tauman Kalai, Ankur Moitra, Gregory Valiant:
Efficiently learning mixtures of two Gaussians. STOC 2010: 553-562 - [i3]Ankur Moitra, Gregory Valiant:
Settling the Polynomial Learnability of Mixtures of Gaussians. CoRR abs/1004.4223 (2010) - [i2]Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra:
Vertex Sparsifiers and Abstract Rounding Algorithms. CoRR abs/1006.4536 (2010) - [i1]Ankur Moitra, Ryan O'Donnell:
Pareto Optimal Solutions for Smoothed Analysts. CoRR abs/1011.2249 (2010)
2000 – 2009
- 2009
- [c2]Ankur Moitra:
Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. FOCS 2009: 3-12 - 2008
- [c1]Ankur Moitra, Tom Leighton:
Some Results on Greedy Embeddings in Metric Spaces. FOCS 2008: 337-346
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-10 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: