We are happy to announce that the third talk of the LUCI group seminar series (https://luci.unimi.it/) will be given by Melissa Antonelli(University of Bologna & INRIA Sophia Antipolis) via Zoom (please, see details below) on Friday, March 3rd, starting from 2pm (Milan time).
Title: On Classical Counting Propositional Logic
Abstract: Interactions between logic and theoretical computer science are several and deep, and the development of deterministic computational models has considerably benefitted from their study. Strikingly, randomized computation was only marginally touched by such fruitful interchanges. Our project precisely aims to start bridging this gap by developing inherently quantitative logics and investigating their relations with specific aspects of probabilistic computation.

In this talk, I will deal with the connection between quantitative logics and counting complexity. First, I will introduce the counting propositional logic CPL, the language of which extends that of PL with counting quantifiers, expressing that a formula is true in a certain portion of its possible interpretations. Then, I will show that the complexity of the decision problem for (a special prenex form of) counting formulas perfectly matches the appropriate level of Wagner’s hierarchy, and so CPL provides a probabilistic generalization of the standard purely logical characterization of the polynomial hierarchy via QPL. In the second part of the talk, I will focus on the univariate fragment CPL_0 trying to make its connection with stochastic experiments explicit. To do so, I will prove that any (and only) event(s) associated with dyadic distributions can be simulated in this formalism, and present an effective procedure to measure the probability of counting formulas.All the results that I am going to introduce are part of a joint work with Ugo Dal Lago and Paolo Pistone.

Zoom Link:   https://us02web.zoom.us/j/4293425101