Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > EWIN TANG:
All reports by Author Ewin Tang:

TR18-128 | 11th July 2018
Ewin Tang

A quantum-inspired classical algorithm for recommendation systems

Revisions: 3

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




ISSN 1433-8092 | Imprint