SchwentickFest

Scientific program

9:00–9:15	Welcome
9:15–9:30	Martin Grohe: Locality (A Personal Perspective)
9:30–10:00	Etienne Grandjean: Where are we with linear time complexity?
10:00–10:30	Arnaud Durand: Enumeration Classes Defined by Circuits
10:30–11:00	Coffee break
11:00–11:15	R Ramanujam: Some news on first order modal logic
11:15–11:30	Nicole Schweikardt: On winning Ehrenfeucht games using Schwentick’s Extension Theorem
11:30–12:00	Mikolaj Bojanczyk: Infinite alphabets and pebbles
12:00–12:30	Thomas Zeume: Dynamic research
12:30–14:00	Lunch Break
14:00–14:15	Georg Gottlob: The Model Checking Problem for Prefix Classes of Second-Order Logic
14:15–14:30	Frank Neven: Reminiscing on 25-years of collaboration
14:30–15:00	Henrik Björklund: What happens when you internalise the Internet? Bias in large language models
15:00–15:30	Wim Martens: A characterization
15:30–16:00	Coffee break

Dinner

On the evening of February 17 at 8pm there will be a workshop dinner.
Restaurant: Bistro Warszawa, ul. Rynek Starego Miasta 1/3, Warsaw.

Program details

Martin Grohe: Locality (A Personal Perspective)
Abstract: Starting from Gaifman’s and Hanf’s Theorems long predating Finite Model Theory as a field, locality has always been central in studying logics on finite structures. In 1999, Thomas and I (in a paper that’m still proud of) proved a theorem on the locality of order-invariant first-order logic. Since then, locality has entered my work in various ways, and it often played a crucial role. My talk will be walk through some of these results.

Etienne Grandjean: Where are we with linear time complexity?
Abstract: Linear time is an intuitive notion in the analysis of algorithms. It has been studied in complexity theory since the 1990s. Although it seems a fragile concept, linear time is very present today in theoretical computer science, in particular in logic and in database theory. I’ll try to take stock of what we currently know or don’t know about linear time complexity.

Arnaud Durand: Enumeration Classes Defined by Circuits
Abstract: We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes.
In this way we obtain a framework to distinguish between the complexity of different problems known to be solvable with polynomial delay.

R Ramanujam: Some news on first order modal logic
Abstract: We mention some recent results on decidable fragments of first order modal logic, which lead to many interesting questions for further study.

Nicole Schweikardt: On winning Ehrenfeucht games using Schwentick’s Extension Theorem

Abstract: I’ll focus on Thomas’ early research at the University of Mainz, where he was a Post-Doc while I was a PhD student at Clemens Lautemann’s chair. Thomas and Clemens introduced me to the beauty of Ehrenfeucht games and the many tricks that help to find winning strategies. In particular, Thomas’ PhD thesis introduced me to the game’s protagonists Spoiler and Duplicator and provided a method for combining winning strategies – later dubbed “Schwentick’s Extension Theorem”.

Mikolaj Bojanczyk: Infinite alphabets and pebbles
Abstract: I would like to talk about two separate topics: data words (i.e. words over infinite alphabets) and pebble automata (i.e. automata that use pebbles to mark positions in their inputs). I will describe how Thomas introduced me to these topics, and what results we achieved together (and other co-authors). It so happens that these continue to be the two main topics of my research, and I will also try to discuss more recent developments.

Georg Gottlob: The Model Checking Problem for Prefix Classes of Second-Order Logic
Abstract: This talk presents a short and very incomplete overview of various results on model-checking for prefix-classes of Prefix classes of Second order Logic (SO) over (possibly restricted) finite structures. Among various other results, the classification of existential SO over graphs (and general finite structures) will be mentioned, to which Thomas Schwentick has made an important contribution.

Henrik Björklund: What happens when you internalise the Internet? Bias in large language models
Abstract: The last few years have seen the rise of the truly large language models, such as BERT, GPT3, and lately GPT-Chat. These models are trained on very large sets of natural language text data. While some corpora are more carefully curated than others, all of them contain large amounts of random internet content. Unfortunately, as so often in life, what you get out of something depends on what you put into it. The models struggle with avoiding hate speech and bias based on categories such as gender, ethnicity, sexual orientation, religon, etc.