165 citations · 950 across the 71 of their papers we have counts for
9 papers · 1 filter
Spectral Methods from Tensor Networks
Ankur Moitra, Alexander S. Wein
A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problem…
How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories
Younhun Kim, Frederic Koehler, Ankur Moitra +2
Reconstruction of population histories is a central problem in population genetics. Existing coalescent-based methods, like the seminal work of Li and Durbin (Nature, 2011), attemp…
Improved Bounds for Randomly Sampling Colorings via Linear Programming
Sitan Chen, Michelle Delcourt, Ankur Moitra +2
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of -colorings of a graph on vertices with maximum degree is r…
The Paulsen Problem Made Simple
Linus Hamilton, Ankur Moitra
The Paulsen problem is a basic problem in operator theory that was resolved in a recent tour-de-force work of Kwok, Lau, Lee and Ramachandran. In particular, they showed that every…
Efficiently Learning Mixtures of Mallows Models
Allen Liu, Ankur Moitra
Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, reco…
Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
Amelia Perry, Alexander S. Wein, Afonso S. Bandeira +1
A central problem of random matrix theory is to understand the eigenvalues of spiked random matrix models, introduced by Johnstone, in which a prominent eigenvector (or "spike") is…