Towards a Logical Foundation of Randomized Computation
Melissa Antonelli, Ugo Dal Lago, Paolo Pistone · Nordic Machine Intelligence · 2025
Interactions between logic and theoretical computer science are numerous and profound. In recent decades, they have been deeply investigated, but, surprisingly, the study of probabilistic computation was only marginally touched by such fruitful interchanges. Nowadays, such a missing connection appears even more striking, due to the increasing pervasiveness of randomized algorithms in AI. In this paper we summarize our previous studies aimed to bridge the gap by developing logical systems corresponding to specific aspects of randomized computation and by generalizing standard achievements to the probabilistic realm. The key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations.