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

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 …
15 października 2025 14:15
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 …
8 października 2025 14:15
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 …
20 sierpnia 2025 14:15
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 …
23 lipca 2025 14:15
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, …
9 lipca 2025 14:15
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 …
11 czerwca 2025 14:15
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 …
21 maja 2025 14:15
Antonio Casares (University of Warsaw)
A canonical model of automata over infinite words (A canonical model of automata over infinite words)
Contrary to the case of automata over finite words, deterministic parity automaton cannot be minimised in polynomial time, and omega-regular languages do not admit a unique, minimal deterministic automaton. Yet, not all hope is lost! …
14 maja 2025 14:15
Wojciech Przybyszewski (University of Warsaw)
Flip-separability (Flip-separability)
Nešetřil and Ossona de Mendez proved that for every nowhere dense graph class C, integer r, and ε > 0 there is some integer k with the following property: For every n-vertex graph G in …
30 kwietnia 2025 14:15
Łukasz Kamiński (University of Warsaw)
Reachability in symmetric VASS (Reachability in symmetric VASS)
We investigate the reachability problem in symmetric VASS, where transitions are invariant under a group of permutations of coordinates. One extremal case, the trivial groups, yields general VASS. In another extremal case, the symmetric groups, …
23 kwietnia 2025 14:15
Mathieu Lehaut (University of Warsaw)
Asynchronous automata, trees, and reconfigurability (Asynchronous automata, trees, and reconfigurability)
I will present some results about Zielonka's asynchronous automata, which are a popular automata model for concurrent programs. Zielonka's seminal result about distributivity shows that one can go from a centralized specification given by a …
16 kwietnia 2025 14:15
Henry Sinclair-Banks (University of Warsaw)
Reaching Semilinear Target Sets in Automata with One Counter (Reaching Semilinear Target Sets in Automata with One Counter)
I will introduce a (novel) generalised reachability problem in automata with one counter with a variety of semantics. The goal of the seminar is to identify what features of target sets make the reachability problem …
9 kwietnia 2025 14:15
Aliaume Lopez (University of Warsaw)
Well-quasi-ordered classes of graphs and bounded linear clique-width (Well-quasi-ordered classes of graphs and bounded linear clique-width)
A quasi-ordered set (X, ≤) is a well-quasi-order (WQO) whenever it contains neither infinite antichains, nor infinite decreasing sequences. A cornerstone result of structural graph theory is the Graph Minor Theorem of Robertson and Seymour, …