We invite you to join the celebration of the scientific work of Thomas Schwentick on the occasion of his 60th birthday. In this daylong event we will honor Thomas’ role as a leading researcher in computational logic, database theory and automata theory via a number of scientific talks on logic and computer science.
- What: SchwentickFest, a scientific event in honour of Thomas Schwentick
- When: February 17, 2023
- Where: Warsaw, collocated with CSL 2023
|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|
|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|
|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|
On the evening of February 17 at 8pm there will be a workshop dinner.
Restaurant: Bistro Warszawa, ul. Rynek Starego Miasta 1/3, Warsaw.
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.
The registration for the SchwentickFest is via the registration for CSL. Registration either only for the SchwentickFest or for both SchwentickFest and CSL is possible.
For questions please contact Thomas Zeume (firstname.lastname@example.org).