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

ISSN 1433-8092 | Imprint