Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2024
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 whe…
cs.DS2024
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…