Logic Seminar

The Logic seminar is held on Wednesdays, usually at 12-14. If not separately specified, the talks always start at a quarter past.

We occasionally have online talks - the permanent Zoom room for the seminar is: https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09 (Meeting ID: 628 9140 0777, Passcode: 164195)

The seminar is led by prof. Juha Kontinen and Åsa Hirvonen.

Schedule of the fall term 2025

Wed 3.9.2025 12 -14, C124

Arne Meier (Hannover): Disjunctions of Two Dependence Atoms

Abstract: Dependence logic is a formalism that augments the syntax of first-order logic with dependence atoms asserting that the value of a variable is determined by the values of some other variables, i.e., dependence atoms express functional dependencies in relational databases. On finite structures, dependence logic captures NP, hence there are sentences of dependence logic whose model-checking problem is NP-complete. In fact, it is known that there are disjunctions of three dependence atoms whose model-checking problem is NP-complete.

Motivated from considerations in database theory, we study the model-checking problem for disjunctions of two unary dependence atoms and establish a trichotomy theorem, namely, for every such formula, one of the following is true for the model-checking problem:  it is NL-complete; (ii) it is LOGSPACE-complete; (iii) it is first-order definable (hence, in AC[0]). Furthermore, we classify the complexity of the model-checking problem for disjunctions of two arbitrary dependence atoms, and also characterize when such a disjunction is coherent, i.e., when it satisfies a certain small-model property. Along the way, we identify a new class of 2CNF-formulas whose satisfiability problem is LOGSPACE-complete. This talk is presenting parts of this joint work with Nicolas Fröhlich and Phokion Kolaitis.

Wed 10.9.2025 12 -14, C124

Timon Barlag (Hannover): Arithmetic Circuits and Metafinite First-Order Logic over Semirings

and

Laura Strieker (Hannover): Graph Neural Networks and Arithmetic Circuits

Wed 17.9.2025 12 -14, C124

Ur Ya'ar: Inner models from extended logics and the Δ-operation

Abstract: If ℒ is an abstract logic, we can define the inner model C(ℒ) by replacing first order logic with ℒ in Gödel's definition of the inner model L of constructible sets. Set theoretic properties of such inner models C(ℒ) have been investigated recently and a spectrum of new inner models is emerging between L and HOD. 

The Δ-extension of a logic, Δ(ℒ), is generally considered a "mild" extension of ℒ - this is a closure operator on logics, producing a logic with a weak form of interpolation, while preserving properties such as Löwenheim- and Hanf-numbers, axiomatizability and compactness.

In this talk, based on joint work with Jouko Väänänen, we will investigate the effect of the Δ-operation on C(ℒ). We will see examples of logics ℒ for which provably C(Δ(ℒ))=C(ℒ), examples where C(ℒ) is consistently strictly smaller than C(Δ(ℒ)), and in one case we show this follows from the existence of 0-sharp.

Wed 24.9.2025 12 -14, C124

Kerkko Luosto: Regular representations of uniform TC^0

Wed 1.10.2025 12 -14, C124

No seminar

Wed 8.10.2025 12 -14, C124

Max Sandström: Time and Multiplicity: Asynchronous Team Semantics for Linear Temporal Logic

Wed 15.10.2025 12 -14, C124

Jouko Väänänen: On Borel subsets of generalized Baire spaces

Abstract: This is joint work with Miguel Moreno and Tapani Hyttinen. We develop Descriptive Set Theory in Generalized Baire Spaces without assuming $\kappa^{<\kappa}=\kappa$. We point out that without this assumption the basic topological concepts of these spaces have to be slightly modified in order to obtain a meaningful theory. This modification has no effect if $\kappa^{<\kappa}=\kappa$. After developing the basic theory we apply it to the question whether the orbits of models of a fixed cardinality $\kappa$ in the space  $\kappa^\kappa$ are $\kappa$-Borel in our generalized sense. It turns out that this question depends, as is the case when $\kappa^{<\kappa}=\kappa$, on stability theoretic properties (structure vs. non-structure) of the first order theory of the model. 

Wed 22.10.2025 12 -14 (exam week), C124

Andrés Uribe-Zapata (TU Wien)

Wed 29.10.2025 12 -14, C124

Aleksi Anttila (TBA)

Wed 5.11.2025 12 -14, C124

Wed 12.11.2025 12 -14, C124

Wed 19.11.2025 12 -14, C124

Lorenz Hornung (TBA) 

Wed 26.11.2025 12 -14, C124

Matilda Häggblom (TBA)

Wed 3.12.2025 12 -14, C124

Wed 10.12.2025 12 -14, C124

Wed 17.12.2025 12 -14, C124

Exam week, no seminar

Past talks