Aalto Theory Seminar

The seminar is a weekly series of talks on a broad scope of CS theory hosted by the Aalto CS Theory Group. For the time being, all talks will be hosted on Zoom.

Jonni Virtema: Descriptive complexity of real computation and probabilistic team semantics
Wednesday, 13 January at 14:15-15:00, subscribe to receive a weekly mail on the current topic and a link for Zoom.

Background:
Metafinite model theory (Grädel & Gurevich 1998) generalizes the approach of finite model theory by shifting to two-sorted structures that extend finite structures with another (often infinite) domain with some arithmetic (such as the reals with multiplication and addition), and weight functions bridging the two sorts. Finite structures enriched with real arithmetic are called R-structures. Blum-Shub-Smale machines (Blum, Shub & Smale 1989), BSS machine for short, are essentially random access machines with registers that can store real numbers and which can compute arithmetic operations on reals in a single time step. In addition for recognizing languages over the reals, BSS machines can also be used to recognize languages on the Boolean alphabeth {0,1}; e.g. Boolean languages recognizable by BSS-machiness in non-determinitic polynomial time coincides with the complexity class existsR (problems PTIME reducible to the existential theory of the reals) which lies somewhere between NP and PSPACE (defined with Turing machines). NP on BSS machines was logically captured by a variant of existential second-order logic over R-structures in (Grädel & Meer 1995).

Our contribution:
We study descriptive complexity of logics in the setting of probabilistic team semantics. This is a family of logics built-up from atomic expressions stating quantitative notions of dependence between random variables. E.g., probabilistic independence logic is built around an atomic statement that declares conditional probabilistic independence between tuples of random variables. Formulae, in this setting, describe properties of real-weighted distributions over first-order assignments. Hence, it turns out, that the descriptive complexity of related logics lie in the realm of BSS-machines. For pinpointing the exact complexity of logics in the probabilistic team semantics setting, we introduced a novel restricted variant of BSS machines, coined “separate-branching BSS-machines” or SBSS-machines. This led to various connections between logics using probabilistic team semantics, complexity classes defined via SBSS-machines, complexity classes defined via Turing machines, and restrictions of the variant of existential second-order logic of Grädel and Meer.