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
-
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. …
-
Feb. 25, 2026, 2:15 p.m.
Yijia Chen (Shanghai Jiao Tong University)
Lovász meets Łoś and Tarski (Lovász meets Łoś and Tarski)
A classical result of Lovász states that a graph G contains a vertex cover of size at most k if and only if G does not contain some graphs H_1, \ldots, H_\ell as (induced) subgraphs, …
-
Feb. 18, 2026, 2:15 p.m.
Roland Guttenberg (University of Warsaw)
Revisiting Finiteness of Matrix Monoids (Revisiting Finiteness of Matrix Monoids)
This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented matrix monoid is in \pspace, improving the known $\conexp^{\np}$ bound. We also show …
-
Feb. 4, 2026, 2:15 p.m.
Katzper Michno (University of Warsaw)
Fourier Analysis in Boolean Promise Constraint Satisfaction (Fourier Analysis in Boolean Promise Constraint Satisfaction)
Promise Constraint Satisfaction Problems (PCSPs) are NP problems defined by a pair of relational structures A and B over the same signature, where A admits a homomorphism to B. Given an input structure X, the …
-
Jan. 28, 2026, 2:15 p.m.
Mathieu Lehaut (University of Warsaw)
Separability and games for 1-register automata (Separability and games for 1-register automata)
The separability problem asks whether two disjoint "complex" sets can be separated by a "simple" one, in the sense that the simple one fully contains one of the complex set and is disjoint from the …
-
Jan. 21, 2026, 2:15 p.m.
Mikołaj Bojańczyk (University of Warsaw)
Automata for MSO over infinite trees with quantification over Borel sets of branches (Automata for MSO over infinite trees with quantification over Borel sets of branches)
Joint work with Antonio Casares, Sven Manthe and Paweł Parys. Rabin's Tree Theorem says that the MSO theory of the infinite binary tree is decidable. Shelah showed that MSO logic becomes undecidable if we allow …
