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

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