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
-
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 …
-
April 1, 2026, 2:15 p.m.
Ruiwen Dong (University of Oxford)
The Skolem Problem in rings of positive characteristic (The Skolem Problem in rings of positive characteristic)
The Skolem Problem in a commutative ring R asks, given a linear recurrence sequence over R, decide whether it contains a zero term. Decidability of the Skolem Problem over ring of characteristic zero (such as …
-
March 18, 2026, 2:15 p.m.
Marcin Czakon (Department of Logic KUL, Poland)
Open problems in Equivalential Calculus (Open problems in Equivalential Calculus)
It has been one hundred years since research began on the equivalential calculus (EC), a proper fragment of classical propositional calculus (CPC). In this system, theorems are constructed exclusively from propositional variables and the equivalence. …
-
March 11, 2026, 2:15 p.m.
Yahia Benalioua (University of Warsaw)
Minimizing Cost Register Automata over a Field (Minimizing Cost Register Automata over a Field)
Weighted automata (WA) are an extension of finite automata that define functions from words to values in a given semiring. An alternative deterministic model, called Cost Register Automata (CRA), was introduced by Alur et al. …
