Probabilistic Recursion Theory and Implicit Computational Complexity

Ugo Dal Lago 1, 2 Sara Zuppiroli 2
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01091595
Contributor : Ugo Dal Lago <>
Submitted on : Friday, December 5, 2014 - 4:39:02 PM
Last modification on : Saturday, January 27, 2018 - 1:30:51 AM
Long-term archiving on : Monday, March 9, 2015 - 6:04:57 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ugo Dal Lago, Sara Zuppiroli. Probabilistic Recursion Theory and Implicit Computational Complexity. 11th International Colloquium on Theoretical Aspects of Computing., Sep 2014, Bucharest, Romania. ⟨10.1007/978-3-319-10882-7_7⟩. ⟨hal-01091595⟩

Share

Metrics

Record views

316

Files downloads

202