Seminar Computer Science - Dr. J. Virtema

Title: Descriptive complexity of higher-order logics and quantitative reasoning

Abstract:
In this talk, I give a short overview of my perspective to logic in computer science and survey some of my past and current works on the topic. My perspective to logic comes from the field of finite model theory, where principal objects of interest are finite structures, formulae, and the semantical satisfaction relation between these two. Structures can be seen to encode systems, or states of affairs, and formulae to express possible properties of those systems. Two important properties of any logic are its expressive power and the complexity of related fundamental reasoning problems. Descriptive complexity theory aims to give insight to complexity classes by analysing the richness of logical languages needed to express the problems in a given complexity class. For example, the celebrated Fagin’s theorem states that a property (e.g., of graphs) can be decided in non-deterministic polynomial time if and only if the property can be expressed in existential second-order logic.

Many of my works consider complexity and expressivity of logics in the framework of team semantics. This framework allows one to consider a plethora of important properties, such as notions of dependence and independence, that cannot be expressed directly in the standard Tarskian semantics. I will give a brief introduction to team semantics and its relationship to database dependencies and verification. Finally, I will give a more detailed exposition of my recent article Descriptive complexity of real computation and probabilistic independence logic published in LICS 2020. In the paper we relate probabilistic independence logic (a logic that expresses properties of probability distributions) to a variant of existential second-order logic that has access to real arithmetics, and to complexity classes defined with the so-called BSS-machines (register machines that can operate on real numbers using arithmetical operations in unit step).

Time permitting, I will give a brief glance to one of my older works Weak models of distributed computing, with connections to modal logic in which we identified formulae of modal logic to distributed algorithms in the spirit of descriptive complexity theory.