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

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
Charles University (Charles University)
ime-space Tradeoffs for Directed s-t Connectivity (ime-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. …
25 lutego 2026 14:15
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, …
18 lutego 2026 14:15
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 …
4 lutego 2026 14:15
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 …
28 stycznia 2026 14:15
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 …
21 stycznia 2026 14:15
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 …
14 stycznia 2026 14:15
Pierre Bourhis (University of Lille)
Circuits for Querying Trees: A Little Survey (Circuits for Querying Trees: A Little Survey)
Querying trees via Tree automata presents lot of interest because several important questions can be executed with a guaranteed efficient time. Over the last decades, different approaches have presented to solve major query answering questions …
17 grudnia 2025 14:15
Antoni Puch (University of Warsaw)
Pumping Sequence Families: An Inexpressibility Result for Copyless Cost Register Automata (Pumping Sequence Families: An Inexpressibility Result for Copyless Cost Register Automata)
nexpressibility results are among the most natural questions in automata theory. They are also often some of the most difficult. One of the few reliable tools for proving them are pumping lemmas, but most models …
10 grudnia 2025 14:15
Jakub Gajarský (University of Warsaw)
Efficient reversal of transductions of sparse graph classes (Efficient reversal of transductions of sparse graph classes)
First-order transductions are graph transformations based in logic that allow us to create new graphs from old ones. They are of fundamental importance in understanding the interplay between logic and structural and algorithmic graph theory, …
3 grudnia 2025 14:15
Lorenzo Clemente (University of Warsaw)
Commutative algebras of series (Commutative algebras of series)
We study an expressive syntax in which one can coinductively define product operations on series. For instance, we can model the known Hadamard, shuffle, and infiltration products, and in fact any binary operation obeying a …