Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with sampling algorithm:
TR95-039 | 11th July 1995
Tomoyuki Yamakami

Polynomial Time Samplable Distributions

Revisions: 2

This paper studies distributions which
can be ``approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
... more >>>

TR18-128 | 11th July 2018
Ewin Tang

A quantum-inspired classical algorithm for recommendation systems

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