193 citations · 529 across the 33 of their papers we have counts for
44 papers
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai +2
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that fi…
Robust Mixture Learning when Outliers Overwhelm Small Groups
Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel +5
We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fractio…
Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi +3
We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant numbe…
Semirandom Planted Clique and the Restricted Isometry Property
Jarosław Błasiok, Rares-Darius Buhai, Pravesh K. Kothari +1
We give a simple, greedy -time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds when…
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
Jingqiu Ding, Tommaso d'Orsi, Yiding Hua +1
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $…
Robust Mean Estimation Without Moments for Symmetric Distributions
Gleb Novikov, David Steurer, Stefan Tiegel
We study the problem of robustly estimating the mean or location parameter without moment assumptions. We show that for a large class of symmetric distributions, the same error as…