skip to content

Department of Computer Science and Technology

All times are in Central European Summer Time (CEST), UTC +2.

(Abstract can be found below the table.)



Monday, 4 July 2022

09.00-09.20 Registration
09.20-09.30 Opening words
09.30-10.10 Invited talk: Bartek Klin – Monads for monadic second order logic (slides)

10.10-10.30 (remote)

Adam Ó Conghaile - A sheaf-theoretic approach to (P)CSPs (slides)
10.30-11.00 Coffee break
11.00-11.20 (remote) Amar Hadzihasanovic - Data structures for topologically sound higher-dimensional diagram rewriting (slides)
11.20-11.40 Paul-André Melliès - Parsing as a lifting problem and the Chomsky-Schutzenberger representation theorem (slides)
11.40-12.00 Sam van Gool - Proaperiodic monoids via prime models (slides)
12.00-12.15 Vincent Moreau - From profinite words to profinite lambda-terms (slides)
12.15-12.30 Jade Master - How to Compose Shortest Paths (slides)
12.30-14.00 Lunch break
14.00-14.40 Invited talk: Sandra Kiefer – Graph Decompositions via Counting Logics (slides)
14.40-15.00 Pawel Sobocinski - Monoidal Width (slides)
15.00-15.15 Tim Seppelt - Recent Advances in Homomorphism Indistinguishability (slides)
15.15-15.30 (remote) Wei-Lin Wu - Query Algorithms Based on Homomorphism Counts (slides)
15.30-16.00 Coffee break
16.00-16.40 Invited talk: Libor Barto – CSPs and Set Functors (slides)
16.40-17.00 Damiano Mazza - A Categorical Approach to Descriptive Complexity Theory (slides)
17.00-17.20 Jakub Opršal - Datalog reductions between constraint satisfaction problems (slides)
17.20-17.30 Short break (no refreshments)
17.30-17.45 (remote) Siddharth Bhaskar - Indexed complexity classes (slides)
17.45-18.00 (remote) Gabriel Goren - Path Predicate Modal Logic and its Comonadic Semantics (slides)
18.00-18.15 Gabriel Istrate - Compositionality and Proof Complexity (slides)
18.15-18.30 Peter Hines - Coherence, conjectures, and congruential functions (slides)

 

Abstracts

Abstracts of the contributed talks can be found in the book of abstracts.

Bartek Klin - Monads for monadic second order logic

Abstract: Monadic second order logic (MSO) is usually studied over specific kinds of structures, be it finite words, infinite words, finite or infinite trees, total orders of various shapes, etc. One can formulate an abstract definition of MSO for a generic monad. I will explain how this is done, and I will describe some conditions on the monad that guarantee that every definable language is recognised by a finite algebra.

Sandra Kiefer - Graph Decompositions via Counting Logics

Abstract: In descriptive complexity, logic is used to define languages, e.g., graph classes. The complexity of a language is measured as the complexity of a describing formula, even though it might not be directly linked to an algorithm for deciding membership. In my talk, I will bridge this gap and discuss the power of logic to "detect" graph structure. I will elaborate on the definability of certain graph decompositions in counting logics and how this can be used algorithmically to identify entire graphs.

Libor Barto - CSPs and Set Functors

Abstract: I will explain the tight connection between fixed-template finite-domain Promise CSPs and covariant endofunctors of the category of non-empty finite sets. Next, I will suggest a more general framework, which covers an important class of fixed-template infinite-domain CSPs and which uses contravariant endofunctors of the same category.