All reports by Author Santosh Vempala:

__
TR14-148
| 8th November 2014
__

Vitaly Feldman, Will Perkins, Santosh Vempala#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

__
TR12-169
| 22nd November 2012
__

Noga Alon, Santosh Vempala#### The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

__
TR12-064
| 10th May 2012
__

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao#### Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

__
TR06-102
| 15th August 2006
__

Luis Rademacher, Santosh Vempala#### Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

__
TR06-042
| 16th March 2006
__

Amit Deshpande, Santosh Vempala#### Adaptive Sampling and Fast Low-Rank Matrix Approximation

__
TR04-067
| 20th July 2004
__

hadi salmasian, ravindran kannan, Santosh Vempala#### The Spectral Method for Mixture Models

Vitaly Feldman, Will Perkins, Santosh Vempala

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

Noga Alon, Santosh Vempala

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

Luis Rademacher, Santosh Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>

Amit Deshpande, Santosh Vempala

We prove that any real matrix $A$ contains a subset of at most

$4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of

rank at most $k$ with error only $(1+\eps)$ times the error of the

best rank-$k$ approximation of $A$. This leads to an algorithm to

find such ...
more >>>

hadi salmasian, ravindran kannan, Santosh Vempala

We present an algorithm for learning a mixture of distributions.

The algorithm is based on spectral projection and

is efficient when the components of the mixture are logconcave

distributions.