Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

14 października 2026 14:15
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 …
7 października 2026 14:15
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 …
24 czerwca 2026 14:15
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 …
10 czerwca 2026 14:15
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 …
3 czerwca 2026 14:15
Ł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 …
20 maja 2026 14:15
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 …
13 maja 2026 14:15
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 …
29 kwietnia 2026 14:15
Ł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 …
22 kwietnia 2026 14:15
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 …
16 kwietnia 2026 13:00
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 …
15 kwietnia 2026 14:15
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 …
8 kwietnia 2026 14:15
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 …
1 kwietnia 2026 14:15
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 …
18 marca 2026 14:15
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. …
11 marca 2026 14:15
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. …