Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [18 references]  Display  Hide  Download
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


Files produced by the author(s)




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⟩



Les métriques sont temporairement indisponibles