165 citations · 950 across the 71 of their papers we have counts for
28 papers · 1 filter
Color Coding for the Sherrington-Kirkpatrick Model
Alina Harbuzova, Saba Lepsveridze, Mahbod Majid +1
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed -spin models to arbitrarily high accuracy throughout the second-moment regime. T…
Strong spatial mixing for colorings on trees and its algorithmic applications
Zongchen Chen, Kuikui Liu, Nitya Mani +1
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical com…
Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolera…
From algorithms to connectivity and back: finding a giant component in random k-SAT
Zongchen Chen, Nitya Mani, Ankur Moitra
We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree -CNFs for large . In the course of doing so, we establi…
Robust Voting Rules from Algorithmic Robust Statistics
Allen Liu, Ankur Moitra
Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. However the MLE can usually be badly corrupted by a single outlying sa…
Robust Model Selection and Nearly-Proper Learning for GMMs
Jerry Li, Allen Liu, Ankur Moitra
In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? The pro…