A large part of research in algorithmic finite model theory focuses on Monadic Second-Order logic MSO and First-Order logic FO. At this point it is fairly well understood that MSO is tamed exactly on tree-like graphs, while delimiting the region of tameness of FO is the subject of a large on-going project, with the suspected dividing line provided by the notion of monadic dependence. However, between FO and MSO there is a large space for logics with intermediate expressive power, and correspondingly there is continuum of concepts in structural graph theory that are less restrictive than tree-likeness, but more restrictive than monadic dependence. During the talk we will discuss how this correspondence can be understood through the concept of monadic dependence with respect to a particular logic in question. We will also present the recent results and open questions related to logic FO+conn and its dense counterpart low rank MSO.

The Weisfeiler–Leman (WL) algorithm was initially designed as an incomplete approach to the graph isomorphism problem. In fact, it is a family of algorithms that together constitute a general combinatorial approach to identifying graphs and determining vertex properties. Indeed, WL subsumes many other ideas that researchers have explored over time. For example, despite being purely combinatorial, WL implicitly computes the eigenvalues of graphs. WL also features in Babai’s quasi-polynomial-time algorithm for computing isomorphisms.
Over time, it has become apparent that WL has a surprisingly wide range of application areas outside graph isomorphism testing. These include descriptive complexity theory (within finite model theory), the rapidly developing area of homomorphism counts, proof complexity, computational linear algebra, and, more recently, machine learning on graphs.
In this talk, I will give a gentle introduction to the algorithm and draw connections to its various application areas. I will then provide an overview of recent developments and showcase some results at the research frontier.

We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized coloring numbers. Graph classes of bounded merge-width include all classes of bounded expansion or of bounded twin-width – two central notions from the Sparsity and Twin-width frameworks. They are furthermore preserved under first-order transductions, which attests to their robustness. We conjecture that classes of bounded merge-width are equivalent to the previously introduced classes of bounded flip-width.
As our main result, we show that the model checking problem for first-order logic is fixed-parameter tractable on graph classes of bounded merge-width, assuming the input includes a witnessing construction sequence. This unites and extends two previous model checking results: the result of Dvořák, Kráľ, and Thomas for classes of bounded expansion, and the result of Bonnet, Kim, Thomassé, and Watrigant for classes of bounded twin-width. Finally, we discuss future research directions in structural and algorithmic graph theory, in particular in the study of monadically dependent graph classes, which we conjecture to coincide with classes of almost bounded merge-width. Joint work with Jan Dreier.

The workshop will be held at the Arnold Schmidt room (CD0603, prev. Kontaktraum) of the Technical University of Vienna (TU Wien). The venue is located at Gußhausstraße 27, 1040 Vienna, Austria, near the U1 subway stops Taubstumengasse and Karlsplatz.
Find the room in the TU Wien internal maps here.

A non-exhaustive list of nearby food options for lunch. Most of these places are not designed to accommodate large groups, so best split into groups of size up to 10.
The lecture room will remain open during lunch and can be used (e.g., for take-away).

Recommendations by the organizers have the * marker

1. * Swing Kitchen (Vegan Burgers) - Sit-In and Take-out
2. SHU Restaurant (Sichuan) - Sit-In and Take-out
3. Kenny's (Hawaiian, Bowls) - mainly Take-out
4. * Fein Essen (Varying Cuisine) - Take-out
5. Asia Pavillon (Chinese) - Sit-In
6. * Bep Viet (Vietnamese) - Sit-In
7. * Pizzeria Riva (Italian, venue of the workshop dinner) - Sit-In
8. * Santos (Mexican) - Sit-In
9. * Salon Wichtig (Thai Curry) - Take-out
10. * Gorilla Kitchen (Mexican, Burritos) - Sit-In and Take-out
11. Wieden Bräu (Austrian) - Sit-in, limited vegan options
12. * Chang (Asian) - Sit-in
13. Wiener Wirtschaft (Austrian) - Sit-in, limited vegan options
14. Banh Mi Hoi An (Vietnamese) - Sit-In and Take-out
15. Allergikercafé (Varying Cuisine, Cakes, allergy friendly) - Sit-In
16. Noodle King (Noodles, Rice, Sushi) - Sit-In and Take-out
17. Nr. 13 (Burritos, Bowls) - Take-out
18. * Nam Nam Dabba (Indian) - Take-out
19. Taste of India (Indian) - Sit-In
20. Mensa TU Wien (University cantine) - Sit-In

1. Billa (Supermarket)
2. Hofer (Supermarket)
3. Spar Gourmet (Supermarket)
4. Anker (Bakery)