6 citations · 8 across the 10 of their papers we have counts for
13 papers
A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus th…
A Better-than- Approximation for -Median Part II: Stable Instances
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann +6
We consider the -median problem on general metric spaces, subject to the condition that the instances are -stable (i.e., the optimal solution using centers has a cost a…
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,…
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…
Lasso and Partially-Rotated Designs
Rares-Darius Buhai
We consider the sparse linear regression model , where is the design, is a -sparse secret, and…
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…
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…
Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel
We study computational-statistical gaps for improper learning in sparse linear regression. More specifically, given samples from a -sparse linear model in dimension , we…
Algorithms approaching the threshold for semi-random planted clique
Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian 2001. The previous best algorithms for this mo…
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures
Rares-Darius Buhai, David Steurer
We consider mixtures of Gaussian components with unknown means and unknown covariance (identical for all components) that are well-separated, i.e., distinct components ha…
Learning Restricted Boltzmann Machines with Sparse Latent Variables
Guy Bresler, Rares-Darius Buhai
Restricted Boltzmann Machines (RBMs) are a common family of undirected graphical models with latent variables. An RBM is described by a bipartite graph, with all observed variables…
Empirical Study of the Benefits of Overparameterization in Learning Latent Variable Models
Rares-Darius Buhai, Yoni Halpern, Yoon Kim +2
One of the most surprising and exciting discoveries in supervised learning was the benefit of overparameterization (i.e. training a very large model) to improving the optimization…