You are not logged in |
Weekly research seminar
Organizers
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Information
Wednesdays, 2:15 p.m. , room: 5440Research fields
List of talks
-
Nov. 4, 2026, 2:15 p.m.
Vincent Moreau (Tallinn University of Technology)
A cartesian closed fibration of higher-order regular languages (A cartesian closed fibration of higher-order regular languages)
Higher-order regular language, as introduced by Salvati, form a conservative extension of regular languages of finite words and ranked trees to the simply typed λ-calculus. In this work, we investigate the new closure properties enabled …
-
Oct. 28, 2026, 2:15 p.m.
Nguyễn Lê Thành Dũng (CNRS, LIS, Aix-Marseille Université)
Regularity reflection for higher-order tree transducers and its consequences (Regularity reflection for higher-order tree transducers and its consequences)
First, I will explain why the inverse image of a regular tree language by a higher-order tree transducer — an automaton that computes a tree-to-tree function by manipulating simply typed λ-terms — is itself a …
-
Oct. 21, 2026, 2:15 p.m.
Roland Guttenberg (University of Warsaw)
Determinizing and Unambiguizing Weighted Automata over the Rationals (Determinizing and Unambiguizing Weighted Automata over the Rationals)
In this talk I consider weighted automata (WA) over Q, and am interested in deciding whether there exists an equivalent (1) deterministic and (2) unambiguous WA. In the first half of the talk I state …
-
Oct. 14, 2026, 2:15 p.m.
Colin Geniet (University of Warsaw)
Reducing CMSO to unbreakable graphs cannot be computable (Reducing CMSO to unbreakable graphs cannot be computable)
In groundbreaking work, Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP '18] proved that for any fixed Counting MSO formula φ, testing φ on arbitrary graphs can be reduced to testing φ on highly-connected graphs, in the …
-
Oct. 7, 2026, 2:15 p.m.
Filip Mazowiecki (University of Warsaw)
Stronger bounds on the degree of ambiguity of finite automata (Stronger bounds on the degree of ambiguity of finite automata)
I will discuss some properties and restrictions of nondeterministic finite automata (NFA), for example unambiguous NFA. We have become a bit crazy with my co-authors and I'll write more when the paper appears on arxiv …
-
June 24, 2026, 2:15 p.m.
Paweł Parys (University of Warsaw)
Computing Tarski Fixed Points (Computing Tarski Fixed Points)
This is a not-my-theorem talk. I will present recent results by Xi Chen, Yuhao Li, Mihalis Yannakakis on computing Tarski fixed points in the black-box model. In this problem we consider a monotone function F …
-
June 10, 2026, 2:15 p.m.
Mikołaj Bojańczyk (University of Warsaw)
A machine independent characterisation of the rational string-to-string functions (A machine independent characterisation of the rational string-to-string functions)
This is a not-my-theorem talk. The subject is the rational string-to-string functions, which are those that can be computed by unambiguous automata with output. I will present a Myhill-Nerode style characterisation of these functions, which …
-
June 3, 2026, 2:15 p.m.
Łukasz Kamiński (University of Warsaw)
Integer reachability in data VASS (Integer reachability in data VASS)
Data Vector Addition Systems with States (data VASS) is an extension of plain Vector Addition Systems with States (VASS) for which the decidability status of the reachability problem is still open. We show decidability of …
-
May 20, 2026, 2:15 p.m.
Clotilde Bizière (University of Warsaw, University of Bordeaux)
Reachability in Branching Vector Addition Systems (BVAS) (Reachability in Branching Vector Addition Systems (BVAS))
The reachability problem for Vector Addition Systems (VAS) admits two fundamentally different decidability proofs. The classical KLM approach relies on a structural decomposition of runs and yields the optimal Ackermannian complexity bounds. A more recent …
-
May 13, 2026, 2:15 p.m.
Nikolas Mählmann (University of Warsaw)
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width (Hereditary 2-WQO Graph Classes Have Bounded Clique-Width)
A graph class is k-WQO if its k-labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is 2-WQO has bounded clique-width. Combined with the recent result of …
-
April 29, 2026, 2:15 p.m.
Łukasz Orlikowski (University of Warsaw)
Reachability in VASS Extended with Integer Counters (Reachability in VASS Extended with Integer Counters)
I will present our recent result (with Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg, Jérôme Leroux, Vincent Michielini, Antoni Puch and Henry Sinclair-Banks) about the reachability problem in VASS Extended with Integer Counters (VASS+Z), i.e. an …
-
April 22, 2026, 2:15 p.m.
Tim Seppelt (IT University of Copenhagen)
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs (Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs)
Lovász (1967) showed that two graphs G and H are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., G and G admit the same number of number of homomorphisms from …
-
April 16, 2026, 1 p.m.
Nagashri Krishnakumar (IIT Madras)
Solving Big Mazes in Small Space - A Monoid Labelling Approach (Solving Big Mazes in Small Space - A Monoid Labelling Approach)
Solving Mazes - more formally, the graph reachability is a fundamental algorithmic problem in space complexity: given a graph and two special vertices s and t, the task is to determine if there is a …
-
April 15, 2026, 2:15 p.m.
Ninad Rajgopal (Charles University)
Time-space Tradeoffs for Directed s-t Connectivity (Time-space Tradeoffs for Directed s-t Connectivity)
The s-t connectivity problem (STCON), i.e., deciding whether there is a path between two vertices in a directed graph, is a central primitive in graph algorithms and space-bounded complexity. A classical theorem by Savitch shows …
-
April 8, 2026, 2:15 p.m.
Benedikt Pago (University of Cambridge)
The Finite-Model-Theoretic Complexity of Symmetric Circuits (The Finite-Model-Theoretic Complexity of Symmetric Circuits)
In various areas of complexity theory, there are long-standing open conjectures that are widely believed to be true, but notoriously hard to settle. The obstacle is our apparent inability to prove lower bounds that would …
