Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR12-169 | 22nd November 2012
Noga Alon, Santosh Vempala

The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

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 >>>

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

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 >>>

TR06-102 | 15th August 2006
Luis Rademacher, Santosh Vempala

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

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 >>>

TR06-042 | 16th March 2006
Amit Deshpande, Santosh Vempala

Adaptive Sampling and Fast Low-Rank Matrix Approximation

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 >>>

TR04-067 | 20th July 2004
hadi salmasian, ravindran kannan, Santosh Vempala

The Spectral Method for Mixture Models

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

more >>>

ISSN 1433-8092 | Imprint