9 citations · 21 across the 12 of their papers we have counts for
5 papers · 1 filter
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…
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has…
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1
We give efficient algorithms for finding power-sum decomposition of an input polynomial with component s. The case of linear s is equivale…
Optimal Fine-grained Hardness of Approximation of Linear Equations
Mitali Bafna, Nikhil Vyas
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system , for $A \in \mathbb{R}^{n \times…
The Price of Selection in Differential Privacy
Mitali Bafna, Jonathan Ullman
In the differentially private top- selection problem, we are given a dataset , in which each row belongs to an individual and each column correspon…