9 citations · 21 across the 16 of their papers we have counts for
5 papers · 1 filter
Constant Degree Networks for Almost-Everywhere Reliable Transmission
Mitali Bafna, Dor Minzer
In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network that sup…
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…
Quasi-Linear Size PCPs with Small Soundness from HDX
Mitali Bafna, Dor Minzer, Nikhil Vyas
We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs w…
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…
Constant Degree Direct Product Testers with Small Soundness
Mitali Bafna, Noam Lifshitz, Dor Minzer
Let be a -dimensional simplicial complex. A function is said to be a direct product function if there exists a function …