Seminar
Logic Seminar
The Logic seminar is held on Wednesdays, usually at 12-14. During the fall 2023 we will have both on-site and online talks, and we try to keep the page updated on when we have which kind.
The permanent Zoom room for the seminar is: https://helsinki.zoom.us/j/62891400777?pwd=UldCeThTaTJVQjUzUFo4S2ErcndNQT09 (Meeting ID: 628 9140 0777, Passcode: 164195)
PLEASE NOTE: Due to the prevalence of zoom talks given by scholars based in various time zones, the times that the seminar meets will occasionally change from the usual 12-14 slot. Also, if not separately specified, the talks always start at a quarter past.
The seminar is led by prof. Juha Kontinen and Ulla Karhumäki.
Schedule of the spring term 2024
Wed 17.01.2024 12-14, C124
Miguel Moreno: On the Borel reducibility Main Gap
One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:
If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.
In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:
Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.
If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.
This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510
Wed 24.01.2024 12-14, C124
Miguel Moreno: On the Borel reducibility Main Gap (continuation of last week)
One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:
If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.
In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:
Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.
If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.
This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510
Wed 31.01.2024 12-14, C124
Teemu Hankala: From Neural Network Training to Tarski's Exponential Function Problem
For simple network architectures, the weights and biases of a neural network can be trained to optimal values in polynomial time. However, in a general setting the decision variant of the training problem is known to be NP-hard, and gradient descent is often used in the training phase. In 2021 it was shown by Abrahamsen, Kleist and Miltzow that the training problem with piecewise algebraic activation functions is polynomial-time reducible to the satisfiability problem of the existential theory of the real numbers and, in addition, that it is polynomial-time bireducible to this satisfiability problem even if restricted to the identity activation function. In this talk, the connection between neural network training and real numbers is extended to arbitrary activation functions. In particular, the standard logistic function leads to a training problem that is polynomial-time equivalent to Tarski's exponential function problem, whereas neural activations using the sine function lead to undecidability.
This talk is based on joint work with Miika Hannula, Juha Kontinen and Jonni Virtema.
Wed 07.02.2024 12-14, C124
Fausto Barbero: Probabilistic counterfactuals in multiteam semantics
An appropriate generalization of multiteams can be used as semantics for probabilistic intrventionist counterfactuals, e.g. expressions of the form:
"If X were set to value x, then the probability of Y taking value y is e"
In joint works with G. Sandu and J. Virtema, we have studied the properties of languages of causal inference under this interpretation, and considered extensions with infinitary Boolean operators and with strict tensor.
On the model-theoretic side, we see that the infinitary language displays an interesting type of expressive completeness. Understanding the much less expressive finitary languages involves the identification of four classes of linear inequalities and an understanding of their geometry in simplexes. The characterization results can be sharpened into a strict hierarchy of expressivity (of the languages and, in parallel, of the classes of inequalities) and serve as a basis for undefinability results.
On the proof-theoretic side, we provide strongly complete, infinitary axiom systems for both the finitary and infinitary languages. The latter problem led us to the identification of sufficient criteria for the truth of Lindenbaum lemmas.
Wed 14.02.2024 12-14, C124
Miika Hannula: Query output size, entropic inequalities, and conditional independence
We consider the following problem: given an open formula over a relational vocabulary, and size bounds for relations, determine the least upper bound for the number variable assignments satisfying the formula. Even for simple logical formulae, such as conjunctive queries, this problem is non-trivial. The problem also occurs in practice, as estimating the output sizes of intermediate joins (i.e., conjunctive queries) is a critical component of the database query execution plan. Entropic inequalities, in turn, govern the laws of Shannon entropy, and in this talk we consider how these topics connect to one another.We also discuss how entropic inequalities relate to logical entailment through the notion of conditional independence, and, time permitting, explore howconditional independence generalizes in semiring semantics.
Wed 21.02.2024 12-14, C124
Ulla Karhumäki: Small supersimple pseudofinite groups
A simple group is pseudofinite if and only if it is isomorphic to a (twisted) Chevalley group over a pseudofinite field. This celebrated result mostly follows from the work of Wilson in 1995 and heavily relies on the classification of finite simple groups (CFSG). It easily follows that any simple pseudofinite group G has a supersimple theory and that the SU-rank of G is finite. In particular, if SU(G)=3 then G is isomorphic to PSL_2(F) for some pseudofinite field F. In this talk we discuss `small’ pseudofinite groups with supersimple theory. In particular, we will see that the classification G \cong PSL_2(F) above does not require CFSG. This is joint work with F. O. Wagner.
Wed 28.02.2024, No seminar (most of the group not in Helsinki)
Wed 06.03.2024, Exam week (no seminar)
Wed 13.03.2024 12-14, No seminar (most of the group not in Helsinki)
Wed 20.03.2024 12-14, C124
Miguel Moreno: On the Borel reducibility Main Gap (continuation of weeks 1-2)
One of the biggest motivations in Generalized Descriptive Set Theory has been the program of identifying counterparts of classification theory in the setting of Borel reducibility. The most important has been the division line classifiable vs non-classifiable, i.e. identify Shelah's Main Gap in the Borel reducibility hierarchy. This was studied by Friedman, Hyttinen and Weinstein (ne Kulikov) in their book "Generalized descriptive set theory and classification theory". Their work led them to conjecture the following:
If T is a classifiable theory and T' is a non-classifiable theory, then the isomorphism relation of T is Borel reducible to the isomorphism relation of T'.
In this talk we will prove this conjecture, discuss the objects introduced, and provide a detailed overview of the gaps between classifiable shallow theories, classifiable non-shallow theories, and non-classifiable theories. The main result that will be presented is the following:
Suppose \kappa=\lambda^+=2^\lambda, 2^c \leq \lambda = \lambda^{\omega_1} and T_1 and T_2 are countable complete first-order theories in a countable vocabulary.
If T_1 is a classifiable theory and T_2 is a non-classifiable theory, then the isomorphism relation of T_1 is continuously reducible to the isomorphism relation of T_2, and the isomorphism relation of T_2 is strictly above the isomorphism relation of T_1 in the Borel reducibility hierarchy.
This talk will be based on the article Shelah's Main Gap and the generalized Borel-reducibility (https://arxiv.org/abs/2308.07510
Wed 27.03.2024 12-14, C124
Minna Hirvonen: Axiomatization of implication for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence
A set of atoms S is said to logically imply another atom s if every suitable object (e.g. a database or a distribution) that satisfies all of the atoms in S also satisfies the atom s. An implication problem is the task of deciding whether a given set of atoms S logically implies another given atom s.
In this talk, we consider the implication problem for probabilistic independence and unary variants of marginal identity and marginal distribution equivalence over finite probability distributions. Two variables x and y satisfy a unary marginal identity when they are identically distributed. If the multisets of the marginal probabilities of all possible values for variables x and y are equal, the variables satisfy a unary marginal distribution equivalence. I will present a sound and complete finite axiomatization and a polynomial-time algorithm for the implication problem for probabilistic independence, unary marginal identity, and unary marginal distribution equivalence.
Slides of the talk are.
Wed 03.04.2024, 12-14, C124
Kai Sauerwald: A Semantic Perspective of AGM Belief Revision in Tarskian Logics
Changing theories according to new information minimally is axiomatically captured by the famous approach to revision from Alchourrón, Gärdenfors, and Makinson (AGM). We studied and characterized this notion of change in a very general framework on the ground of Tarskian logics semantically. Our starting point is the approach by Katsuno and Mendelzon (K&M), who provided such a characterization for propositional logic over finite signatures. We generalize K&M's approach to the setting of AGM-style revision over bases in arbitrary Tarskian logics, where base may refer to one of the various ways of representing an agent's beliefs (such as belief sets, arbitrary or finite sets of
sentences, or single sentences). The first result is a representation theorem providing a two-way correspondence between AGM-style revision operators and specific
assignments: functions associating every base to a "preference" relation over interpretations, which must be total but is - in contrast to prior approaches - not always transitive. The second contribution presented is a characterization of all Tarskian logics for which our result can be strengthened to assignments that produce transitive preference relations
(as in K&M's original work).
Wed 10.04.2024, 12-14, C124
Ville Salo: Automatic structures and some applications
We define automatic structures and discuss some of their applications in logic (Presburger arithmetic), group theory (Cayley graph (bi-)automatic groups), combinatorics on words (Thue-Morse word and the Fibonacci word) and symbolic dynamics (the domino problem and dynamics of cellular automata).
Wed 17.04.2024, 12-14, C124
Werner Mérian: Logical characterization of complexity classes for enumeration problems
The problems related to complexity theory most commonly studied are the so-called decision problems. They consist in deciding whether, given an input instance, a certain condition is verified or not. Most often, these problems raise the question of whether there exists a solution or not. For their part, enumeration problems are interested in enumerating all solutions. Enumeration problems have been studied in the context of computational complexity theory, and several complexity classes have been introduced for these problems (for tractable ones, we can cite EnumP, TotalP, IncP, DelayP). Our work aims to bring the mission of descriptive complexity to the world of enumeration. The ultimate goal is to successfully capture a tractable enumeration complexity class (namely IncP) with a certain logic. We will then be able to say that an enumeration problem is in this complexity class if and only if there is a formula from the logic associated to this complexity class which characterizes this problem. Our trip will lead us to study fragments of third-order logic and to capture natural enumeration problems.
Wed 24.04.2024, 12-14, C124
Sándor Kisfaludi-Bak: ER-completeness in geometric algorithms
Geometric algorithms often run into precision difficulties: for example, computing the total length of n segments (even when the segments have integer-coordinate endpoints) is of unknown complexity. We have discovered that several problem flavors, such as incidence, packing, visibility where the optimum output "requires" exponential precision numbers in some manner, which intuitively places them outside NP. Recently the class ER or (ETR), the existential theory of the reals arose as the natural complexity class for such continuous geometric problems. ER consists of those problems that can in polynomial time be reduced to checking if a semi-algebraic set is empty, or equivalently, to an existentially quantified Boolean formula of polynomial inequalities over the reals with integer coefficients. Today we have a wealth of problems that are ER-complete, including prominent problems such as art gallery, low-rank matrix completion, or training neural networks. During the talk I will introduce the complexity class and we will get an intuition about some of its complete problems. We will learn about how one can know (and attempt to prove) that a problem belongs there, as well as the state of the art for solving such problems.
Tue 30.04.2024, 12-14, D123 (note unusual time and place)
Tuomas Hakoniemi: Picking mushrooms
Proving superpolynomial lower bounds for constant depth refutations with modular counting connectives is a major open question in propositional proof complexity. In this talk we present the problem, map out a possible path towards its resolution and discuss some recent off-path discoveries along the way. This talk is based on joint works with Nashlen Govindasamy, Nutan Limaye and Iddo Tzameret.
Wed 08.05.2024, Exam week (no seminar)
Talks of the spring term 2023
Talks of the fall term 2022
Talks of the spring term 2022
Talks of the fall term 2021
Talks of the spring term 2021
Talks of the fall term 2020
Talks of the spring term 2020
Talks of the fall term 2019
Talks of the spring term 2019
Talks of the fall term 2018Seminar talks fall 2018
Talks of the spring term 2018Seminar talks spring 2018
Talks of the fall term 2017Seminar talks fall 2017
Talks of the spring term 2017Seminar talks spring 2017
Talks of the fall term 2016Seminar talks fall 2016
Talks of the spring term 2016Seminar talks spring 2016
Talks of the fall term 2015Seminar talks fall 2015
Talks of the spring term 2015Seminar talks spring 2015
Talks of the fall term 2014Seminar talks fall 2014
Talks of the spring term 2014Seminar talks spring 2014
Talks of the fall term 2013Seminar talks fall 2013
Talks of the spring term 2013Seminar talks spring 2013
Talks of the fall term 2012Seminar talks fall 2012
Older talks (2011-2012)