| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Probabilistic Recursion Theory and Implicit Computational Complexity
Abstract : We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of polytime sampleable distributions, a key concept in average-case complexity and cryptography.
Cited literature [18 references]
https://hal.inria.fr/hal-01091595
Contributor : Ugo Dal Lago Connect in order to contact the contributor
Submitted on : Friday, December 5, 2014 - 4:39:02 PM
Last modification on : Friday, October 30, 2020 - 12:04:03 PM
Long-term archiving on: : Monday, March 9, 2015 - 6:04:57 AM
Contributor : Ugo Dal Lago Connect in order to contact the contributor
Submitted on : Friday, December 5, 2014 - 4:39:02 PM
Last modification on : Friday, October 30, 2020 - 12:04:03 PM
Long-term archiving on: : Monday, March 9, 2015 - 6:04:57 AM
File
main.pdf
Files produced by the author(s)