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

Venkatesan Guruswami, Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

Ewin Tang

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an $m\times n$ matrix of small rank $k$. We give the first classical algorithm to produce a recommendation in $O(\text{poly}(k)\text{polylog}(m,n))$ time, which is an exponential improvement on previous ... more >>>