93 citations · 578 across the 83 of their papers we have counts for
9 papers · 1 filter
A Unified View of Graph Regularity via Matrix Decompositions
Greg Bodwin, Santosh Vempala
We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…
Robustly Clustering a Mixture of Gaussians
He Jia, Santosh Vempala
We give an efficient algorithm for robustly clustering of a mixture of two arbitrary Gaussians, a central open problem in the theory of computationally efficient robust estimation,…
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, Santosh Vempala
Motivated by the Dikin walk, we develop aspects of an interior-point theory for sampling in high dimension. Specifically, we introduce a symmetric parameter and the notion of stron…
A Generalized Central Limit Conjecture for Convex Bodies
Haotian Jiang, Yin Tat Lee, Santosh S. Vempala
The central limit theorem for convex bodies says that with high probability the marginal of an isotropic log-concave distribution along a random direction is close to a Gaussian, w…
The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator toge…
Human-Usable Password Schemas: Beyond Information-Theoretic Security
Elan Rosenfeld, Santosh Vempala, Manuel Blum
Password users frequently employ passwords that are too simple, or they just reuse passwords for multiple websites. A common complaint is that utilizing secure passwords is too dif…