Towards a Logical Foundation of Randomized Computation: Doctoral Thesis Abstract

Abstract

Interactions between logic and theoretical computer science are multiple and profound. In the last decades, they have been deeply investigated, but, surprisingly, the study of probabilistic computation was only marginally touched by such fruitful interchanges. The overall goal of my doctoral thesis was precisely that of start bridging this gap by developing logical systems corresponding to specific aspects of randomized computation and, due to them, by generalizing standard achievements to the probabilistic realm. To do so, the key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations.