All reports by Author Ewin Tang:

__
TR18-128
| 11th July 2018
__

Ewin Tang#### A quantum-inspired classical algorithm for recommendation systems

Revisions: 3

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