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.
Type de document :
Communication dans un congrès
11th International Colloquium on Theoretical Aspects of Computing., Sep 2014, Bucharest, Romania. 〈10.1007/978-3-319-10882-7_7〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01091595
Contributeur : Ugo Dal Lago <>
Soumis le : vendredi 5 décembre 2014 - 16:39:02
Dernière modification le : samedi 27 janvier 2018 - 01:30:51
Document(s) archivé(s) le : lundi 9 mars 2015 - 06:04:57

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

221

Téléchargements de fichiers

97