We are very pleased to announce the invited ICDT 2025 tutorial speaker.
Abstract: A central problem in database theory concerns the complexity of the query evaluation problem, also called the model-checking problem in finite model theory: the problem of evaluating a given formula in a given structure. Here, I will focus on formulas of first-order logic, and study the data complexity (or parameterized complexity) of the evaluation problem. Furthermore, leveraging tools from structural graph theory, I will assume that the input structure is a graph which comes from a fixed class of well-structured graphs, such as the class of planar graphs, as well as much more general 'tame' graph classes. I will survey the recent progress in this fascinating area, which connects various notions originating in structural graph theory – such as nowhere denseness, treewidth and twin-width – with notions originating in model theory – such as stability and dependence – as well as notions originating in statistical learning theory and computational geometry – such as VC-dimension and ε-nets.
Link to the paper.
Szymon Toruńczyk received his PhD at the University of Warsaw in 2011, where he is now employed as an associate professor. His research is in logic in computer science, with a special emphasis on connections between finite model theory, structural graph theory, and parameterized complexity. He is a recipient of the ERC Consolidator grant (2024), the Ackerman award (2011), best paper awards at PODS (2013), ETAPS (2021), and ICALP (2022).