SAMSA Workshop
Workshop on Series, Automata, Matrices, Symbolic dynamics, and their Applications
Aim:
The aim of the workshop is to create a fruitful discussion forum for researchers in mathematics and theoretical computer science working on combinatorial, algebraic and algorithmic aspects of
- automata and their matrix representations,
- combinatorial matrix theory.
- linear dynamical systems,
- matrix semigroups,
- power series,
- program analysis,
- recurrence sequences,
- semigroup theory,
- symbolic computation,
- symbolic dynamics.
The plan is to discuss recent results, emerging research directions, promising applications, open problems and stimulate cooperation among researchers working in these fields.
Programme
The programme will consist of invited talks and tutorials, and short contributed talks from participants.
Invited Speakers:
Survey talk: Mathematical and computational perspectives on the Boolean and binary rank and their relation to the real rank
Abstract (click to expand)
This talk will survey the main known results and open problems relating to the Boolean and binary rank of 0,1 matrices, with particular emphasis on their relationship to the real rank. We will review the basic definitions of these rank functions and present the main alternative formulations of the binary and Boolean rank, together with their computational complexity and their deep connection to the field of communication complexity. We will see some examples of techniques used to establish lower and upper bounds on the binary and Boolean rank, from both mathematics and theoretical computer science, and also highlight the main mathematical properties of these ranks in comparison with those of the real rank. Finally, we will present some algorithmic approaches for computing and approximating these rank functions.
Tutorial talk: The Boolean and binary rank of Kronecker products: theory and applications.
Abstract (click to expand)
The Kronecker product is a useful tool to build large structured matrices from smaller ones, with applications in mathematics and computer science. We will discuss Kronecker products of 0,1 matrices, and applications such as direct sum problems in communication complexity or how Kronecker products are used to amplify the gap between the Boolean, binary and real rank. We will show some of the main mathematical techniques used to give lower and upper bounds on the rank of Kronecker products, as well as prove that the Boolean rank is not always multiplicative under this product. The multiplicativity of the binary rank is still an open problem.
Lunch
Participants are invited to go to lunch in the local area in small groups. There are many options within a short walk of the venue including a modern food court at the nearby Elektrownia Powiśle.
Picnic Dinner
One evening, we plan a (bring your own food and drink) picnic. Further details to follow.
Organisation
SAMSA Workshop: Series, Automata, Matrices, Symbolic dynamics, and their Applications is organised by:
Antoni Puch
University of Warsaw, Poland
Contact:
Click to email all four organisers.Location:
The SAMSA workshop takes place in person at the Faculties of Modern Languages (Wydział Neofilologii).
Address: 55 Dobra street at the University of Warsaw, Poland. (The closest entrance to the room is on Browarna.)
Sessions will take place in Room 1.110 (first floor, zero indexed).
Attending:
If you are interested in attending in the Workshop, please contact the organisers (please include all).
Financial support:
We gratefully acknowledge support from Le Trójkąt CNRS International Research Project.
Past editions:
Samsa 2025, Warsaw