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
-
Dec. 17, 2025, 2:15 p.m.
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 …
-
Dec. 10, 2025, 2:15 p.m.
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, …
-
Dec. 3, 2025, 2:15 p.m.
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 …
-
Nov. 26, 2025, 2:15 p.m.
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.
-
Nov. 19, 2025, 2:15 p.m.
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 …
-
Nov. 12, 2025, 2:15 p.m.
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 …
-
Nov. 5, 2025, 2:15 p.m.
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, …
-
Oct. 29, 2025, 2:15 p.m.
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 …
-
Oct. 22, 2025, 2:15 p.m.
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 …
-
Oct. 15, 2025, 2:15 p.m.
Mikołaj Bojańczyk (University of Warsaw)
Functions computed by Alice and Bob (Functions computed by Alice and Bob)
I will return to a topic discussed by Omid in the last semester, namely functions that can be computed in a distributed protocol by two parties, called Alice and Bob. I will be mainly interested …
-
Oct. 8, 2025, 2:15 p.m.
Roland Guttenberg (University of Warsaw)
PVASS Reachability is Decidable (PVASS Reachability is Decidable)
Reachability in pushdown vector addition systems with states (PVASS) used to be among the longest standing open problems in Theoretical Computer Science. The PVASS reachability problem consists of deciding whether the intersection of a VASS …
-
Aug. 20, 2025, 2:15 p.m.
Subbarao Venkatesh Guggilam (UiT- The Arctic University of Norway)
Shuffle-Rational Series and Doubly-Rational Series (Shuffle-Rational Series and Doubly-Rational Series)
Formal power series have long played a central role in both Mathematical Systems Theory and Automata Theory. A foundational result by Marcel-Paul Schützenberger established that recognizable series (the semantics of weighted automata) are precisely the …
-
July 23, 2025, 2:15 p.m.
George Kenison (Liverpool John Moores University)
Decision Problems for P-finite Sequences (Decision Problems for P-finite Sequences)
This talk will discuss the algorithmic analysis of the class of P-finite sequences. These sequences satisfy linear recurrence relations with polynomial coefficients and are common across the quantitative sciences (examples include the Fibonacci, Motzkin, Harmonic, …
-
July 9, 2025, 2:15 p.m.
Omid Yaghoubi (University of Warsaw)
Two-party computation for functions with string inputs (Two-party computation for functions with string inputs)
I will describe a model of computation, which describes functions that input strings, and output elements from some domain, such as the Booleans, or strings, or a field. The idea is that there are two …
-
June 11, 2025, 2:15 p.m.
Arka Ghosh (LaBRI, Université de Bordeaux)
Equivariant ideals and their membership problem (Equivariant ideals and their membership problem)
For an infinite set X (of variables) and a group G acting on X, an ideal J in the polynomial ring K[X] in X over the field K is called equivariant (w.r.t. G) if J …
