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

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 …
26 listopada 2025 14:15
Szymon Toruńczyk (University of Warsaw)
Not my theorem: some results in VC-combinatorics and applications to logic (Not my theorem: some results in VC-combinatorics and applications to logic)
I will present the notion of Vapnik-Chervonenkis dimension and several fundamental results about it. I will then show some applications to logic.
19 listopada 2025 14:15
Jędrzej Kołodziejski (University of Warsaw)
Modal Logic and Separation: the Surprising Difference Between Binary and Ternary Trees (Modal Logic and Separation: the Surprising Difference Between Binary and Ternary Trees)
Assume logical formulae φ,φ' which are mutually exclusive in the sense that φ entails ¬φ'. A separator is a formula ψ such that φ entails ψ and ψ entails ¬φ'. We will look at separation …
12 listopada 2025 14:15
David Evans (Imperial College London)
Permutation modules for omega-categorical structures (Permutation modules for omega-categorical structures)
Suppose F is a field and G is a group acting on a set W. We consider the FG-module FW in the case where G is the automorphism group of an omega-categorical structure M, and …
5 listopada 2025 14:15
Paweł Parys (University of Warsaw)
Sampling from Language Models under Syntactic Constraints (Sampling from Language Models under Syntactic Constraints)
In recent years, large language models (LLMs) have revolutionized code writing. Using LLMs, one can quickly arrive at solutions that are close to the correct answer for many tasks, though mistakes still occur frequently. However, …
29 października 2025 14:15
Yangluo Zheng (Shanghai Jiao Tong University)
Geometrically 2-Dimensional Vector Addition System with States (Geometrically 2-Dimensional Vector Addition System with States)
In the line of work addressing the reachability problem of VASS, the concept of geometrical dimension (the dimension of the vector space spanned by simple cycle effects) was found important to complexity analysis. It is …
22 października 2025 14:15
Nikolas Mählmann (University of Warsaw)
Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO (Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO)
The graph parameter shrub-depth is a dense analog of tree-depth with strong ties to logic and combinatorics. I will characterize graph classes of bounded shrub-depth by forbidden induced subgraphs. As an application, I will show …