93 citations · 578 across the 83 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman, Will Perkins, Santosh Vempala
The problem of identifying a planted assignment given a random -SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes u…
A Cubic Algorithm for Computing Gaussian Volume
Ben Cousins, Santosh Vempala
We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general…
Fourier PCA and Robust Tensor Decomposition
Navin Goyal, Santosh Vempala, Ying Xiao
Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution.We make this method algor…
Principal Component Analysis and Higher Correlations for Distributed Data
Ravindran Kannan, Santosh Vempala, David Woodruff
We consider algorithmic problems in the setting in which the input data has been partitioned arbitrarily on many servers. The goal is to compute a function of all the data, and the…
The Complexity of Approximating Vertex Expansion
Anand Louis, Prasad Raghavendra, Santosh Vempala
We study the complexity of approximating the vertex expansion of graphs , defined as \[ Φ^V := \min_{S \subset V} n \cdot \frac{|N(S)|}{|S| |V \backslash S|}. \] We give…