Seminar
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
NN: TBA
Wed 17.9.2025 12 -14, C124
Ur Ya'ar: TBA
Wed 24.9.2025 12 -14, C124
Kerkko Luosto: Regular representations of uniform TC^0
Wed 1.10.2025 12 -14, C124
Wed 8.10.2025 12 -14, C124
Wed 15.10.2025 12 -14, C124
Wed 22.10.2025 12 -14, C124
Exam week, no seminar
Wed 29.10.2025 12 -14, C124
Wed 5.11.2025 12 -14, C124
Wed 12.11.2025 12 -14, C124
Wed 19.11.2025 12 -14, C124
Wed 26.11.2025 12 -14, C124
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