BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Helsinki Institute for Information Technology | HIIT - ECPv5.1.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Helsinki Institute for Information Technology | HIIT
X-ORIGINAL-URL:https://www.hiit.fi
X-WR-CALDESC:Events for Helsinki Institute for Information Technology | HIIT
BEGIN:VTIMEZONE
TZID:Europe/Helsinki
BEGIN:DAYLIGHT
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:EEST
DTSTART:20210328T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:EET
DTSTART:20211031T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Helsinki:20210113T140000
DTEND;TZID=Europe/Helsinki:20210113T150000
DTSTAMP:20210125T032420
CREATED:20210108T110125Z
LAST-MODIFIED:20210108T110135Z
UID:11191-1610546400-1610550000@www.hiit.fi
SUMMARY:Descriptive complexity of real computation and probabilistic team semantics
DESCRIPTION:Aalto Theory Seminar \nThe 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. \nJonni Virtema: Descriptive complexity of real computation and probabilistic team semantics\nWednesday\, 13 January at 14:15-15:00\, subscribe to receive a weekly mail on the current topic and a link for Zoom. \nBackground:\nMetafinite 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). \nOur contribution:\nWe 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. \n
URL:https://www.hiit.fi/event/descriptive-complexity-of-real-computation-and-probabilistic-team-semantics/
END:VEVENT
END:VCALENDAR