We’re excited to announce that Jan Dreier has received a prestigious Astra Award from the Austrian Science Fund FWF for his project “UNISTRUC”! The project is funded with €1 million and is set to run for five years. The FWF Astra Awards support advanced postdoctoral researchers in Austria across all disciplines as they transition into independent research leadership.

Jan’s project explores how to make complicated algorithmic problems easier to solve by analyzing the structure of the underlying data. Graphs - mathematical objects that model networks, relationships, and interactions - play a central role in this analysis. While many algorithmic problems are difficult in general, they become manageable when the input graphs have certain properties, like being sparse or decomposable. The aim of the project is to create a unified theory that clearly characterizes which types of graphs are tractable—that is, where problems can be solved efficiently. To do this, the project will use tools from theoretical computer science, including logic, algorithms theory, and graph theory, to discover useful patterns and decompositions in these graphs, and develop new algorithmic techniques with broad applications for computer science.

FWF Astra Awardees are given the opportunity to strengthen their research profile and pursue long-term, independent projects. Half the awards are for women, with additional funding and support measures to promote gender equity. The FWF Astra Awards fund outstanding, innovative research, support the careers of exceptional women researchers, and foster long-term academic leadership. The program strengthens individual careers and the global visibility of Austria’s research landscape by integrating researchers and emerging research fields into Austrian institutions.

About Jan Dreier

Jan Dreier is a post-doctoral researcher at the Research Unit Algorithms and Complexity at the Institute of Logic and Computation at TU Wien Informatics. He studied Computer Science at RWTH Aachen University, earning his PhD in 2020 before moving to Vienna in 2021. His work is at the intersection of structural graph theory, mathematical logic, and algorithm design, with a particular focus on meta-theorems that use insights from graph theory to speed up algorithms.

Abstract

Addressing hard algorithmic problems under worst-case complexity is a central challenge in computer science. This project aims to identify and characterize, in a foundational manner, well-behaved input instances on which many of these hard algorithmic problems become tractable. Nešetřil and Ossona de Mendez introduced the notion of nowhere dense graph classes, which form the foundation of their systematic theory on sparsity of graph classes. This very general notion encompasses, for example, planar graphs and graphs with bounded degree or excluded minor. A breakthrough result by Grohe, Kreutzer, and Siebertz showed that nowhere dense classes are algorithmically tractable in the sense that all problems expressible in first-order logic can be solved in almost-linear time on nowhere dense graph classes. We recently extended this result to monadically stable graph classes, a powerful notion from model theory that goes beyond classical sparsity theory. Recently, classes of bounded twin-width have obtained considerable attention. These classes are incomparable to monadically stable and nowhere dense classes, but algorithmically tractable in a similar sense.

In summary, there has been a long quest to identify larger and larger algorithmically tractable graph classes, and bounded twin-width and monadically stable classes form the current frontier of tractability. Twin-width and monadic stability are two fundamentally incompatible notions. I want to unify and generalize the two corresponding theories into a single theory of algorithmic tractability that exactly characterizes all tractable (hereditary) graph classes. As a cornerstone, I want to show that first-order model checking is fixed-parameter tractable on monadically dependent graph classes. The project will combine techniques from sparsity theory, finite model theory, stability theory, and twin-width theory to discover useful combinatorial structure in well-behaved graphs. This, in turn, will be used to compute algorithmically useful decompositions. In particular, I aim to build upon Ramsey-like properties like Uniform Quasi-Wideness, flip-flatness or flip-breakability, pursuit-evasion games such as the Flipper game or the flip-width game, and the model checking methods for nowhere dense and monadically stable graph classes. The planned project aims to unify and extend the core results of the highly influential sparsity theory, twin-width theory, and stability theory. The result would have a strong impact on various areas of theoretical computer science, in particular computational logic, graph theory, and parameterized complexity.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.