Polynomial Time Samplable Distributions |
| |
Authors: | Tomoyuki Yamakami |
| |
Institution: | Department of Computer Science, University of Toronto, Toronto, Canada, M5S 3G4f1 |
| |
Abstract: | This paper studies the complexity of the polynomial-time samplable (P-samplable) distributions, which can be approximated within an exponentially small factor by sampling algorithms in time polynomial in the length of their outputs. The paper shows that common assumptions in complexity theory yield the separation of polynomial-time samplable distributions from the polynomial-time computable distributions with respect to polynomial domination, average-polynomial domination, polynomial equivalence, and average-polynomial equivalence. |
| |
Keywords: | average-case complexity sampling algorithm domination condition strong one-way functions |
本文献已被 ScienceDirect 等数据库收录! |
|