Dear Sirs and Madams,
On Thursday, November 20, 2025, at 10:15 a.m. in room 110 INF, a
The lecture entitled “Ulam’s metric in higher dimensions” will be given by Dr. Sebastian Bala.
The Ulama metric describes the minimum number of transpositions (operations of cutting and reinserting elements of a permutation) that are needed to move from one permutation to another. Determining the elements that need to be “moved” leads to the solution of the classic Longest Common Subsequence (LCS) problem.
The research initiated by Ulam’s work has yielded a number of important results in computer science, mathematics, statistics, and physics.
In his presentation, Dr. Sebastian Bala will present a generalization of the original definition of the Ulam metric to the multidimensional case, motivated by practical applications of permutation tuples in industry. The properties of the metric defined in this way will be discussed, as well as the computational complexity and approximation possibilities in the analysis of such structures.
Ulam’s metric defines the minimal number of moves (extraction followed by re-insertion of permutation elements) to go between a~given pair of permutations, and determination of moved elements resolves the Longest Common Subsequence problem. The extensive research that followed Ulam’s work provided many influential discoveries in computer science, mathematics, statistics and physics. In this paper, motivated by successful industrial applications of $k$-tuples of permutations, we extend Ulam’s original definition to provide a framework of multidimensional metric and study its complexity and approximability.
We invite employees, doctoral students, and students interested in topics at the intersection of theoretical computer science, combinatorics, and industrial applications to attend the seminar.