Rares-Darius Buhai

activity

20242026

collaborators

7 papers

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.DS2025

Finding Colorings in One-Sided Expanders

Rares-Darius Buhai, Yiding Hua, David Steurer +1

We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example,…

cs.CC2025

The Quasi-Polynomial Low-Degree Conjecture is False

Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…

math.ST2025

Lasso and Partially-Rotated Designs

Rares-Darius Buhai

We consider the sparse linear regression model $y = X I^^{2} + w$ , where $X \in R^{n \times d}$ is the design, $I^^{2} \in R^{d}$ is a $k$ -sparse secret, a…

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 $O (n^{I ¨ + 0.5}) = O (n^{2.872})$ -time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds whe…

cs.LG2024

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…