UTU Seminar in Discrete Mathematics

Time: 4.5.2021 at 13:00

Speaker: Alexander Tiskin, St Petersburg University

Title: The surprising algebra of string comparison

Abstract:We consider the classical Longest Common Subsequence (LCS) problem on a pair of strings, also known as the Sequence Alignment problem in bioinformatics. The textbook solution for this problem is based on dynamic programming, and seems to be the only possible. We will show that this is not the case: a suitably generalised version of the LCS problem can be solved efficiently by a divide-and-conquer algorithm. In this alternative solution, subproblems are combined using a seemingly unrelated structure, known as the Hecke (or “sticky braid”) monoid, which can be defined via tropical matrix multiplication, and bears a close resemblance with the classical braid group. Such an approach is not only of theoretical interest, but also allows us to obtain efficient algorithms for approximate pattern matching on compressed strings without decompression, parallel string comparison, the maximum clique problem on circle graphs, as well as some real-life bioinformatics problems.

Time: 6.4.2021 at 13:00

Speaker: Anni Hakanen, University of Turku

Title: On the Forced Vertices of Resolving Sets and Metric Bases of Graphs

Abstract: A resolving set of a graph is a subset of the vertices which gives a unique combination of distances to each vertex of the graph. Resolving sets can be used to locate vertices in a graph. A resolving set of minimum cardinality is called a metric basis of the graph. In this talk, we will discuss how the concept of a resolving set can be generalised to locate vertex sets instead of individual vertices. Special emphasis is placed on characterising vertices that are necessary to locate vertex sets. A vertex that is in all such resolving sets is called a forced vertex. Forced vertices do not exist for resolving sets that can locate one vertex at a time. However, we can define a similar concept for the metric bases of graphs.

Time: 9.3.2021 13:00

Speaker: Esa Sahla, University of Turku

Title: Self-shuffles with substitutions

Abstract: In formal language theory the operation of shuffling has been an occurring concept for over half a century. The operation has been studied in the context of formal languages as well as computability and process algebras. In this talk we will present some basic results on word shuffling with emphasis on shuffling a word with itself, i.e. the self-shuffle. We will then focus on a variant of the self-shuffle where a word is shuffled with its image under a letter-to-letter substitution. We will show that for a given regular language R it is undecidable whether there exists a word such that the forementioned self-shuffle intersects with R. The problem is reduced to the Post Correspondence Problem with a brief overview of PCP itself.

Time: 15.12.2020 13:00

Speaker: Toni Hotanen, University of Turku

Title: Lyapunov Exponents and Topological Entropy of Cellular Automata and Turing Machines

Abstract: Lyapunov exponents are an important concept in differentiable dynamical systems and they measure stability or sensitivity in the system. Their analogues for cellular automata were proposed by Shereshevsky and since then they have been further developed and studied. It was conjectured that there does not exist such a sensitive cellular automaton, that would have both the right and the left pointwise Lyapunov exponents taking the value zero, for each configuration. In this talk we prove the conjecture false by constructing such a cellular automaton, using aperiodic, complete Turing machines as a building block. In the second part of the talk we will work on several related decision problems in the setting of reversible Turing machines and cellular automata. The decision problems we are interested in are related to the notions of periodicity, topological entropy, speed and Lyapunov exponents. We will prove several of these problems to be undecidable in the setting of reversible Turing machines and as a corollary we get analogous results in the setting of reversible cellular automata.

Time: 1.12.2020 13:00

Speaker: Tuomo Lehtilä, University of Turku

Title: Levenshtein’s channel and list decoding

Abstract: The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. We consider a situation where the information is stored using an e-error-correcting code C in binary Hamming space. A codeword x is sent through N channels and in each of the channels there can occur at most t=e+k (k> 0) errors. Now, the decoder tries to recover the information with the aid of multiple channel outputs. Recently, Yaakobi and Bruck expanded this framework by considering the problem where the decoder provides a list of codewords which might have been sent instead of a unique output. We have continued studying this problem and in this talk I present how the size of the list is connected to the number of the channels N and some other variables. In particular, the exact number of the channels required to have a constant size list is presented. Most of the results rely especially on the Sauer-Shelah lemma.

This talk is based on joint work with Ville Junnila and Tero Laihonen: “On Levenshtein’s Channel and List Size in Information Retrieval”,  https://doi.org/10.1109/TIT.2020.3016269

Time: 17.11.2020, 13.00

Speaker: Ion Petre, University of Turku

Title: Network controllability: algorithmics and applications

Abstract: The problem of controlling a dynamic network has a long history in control theory, with roots in a diversity of mathematical methods from complex analysis to topology, graph theory and computational complexity. The basic problem setup is that of a dynamical system represented as a directed graph, with nodes influencing each other’s dynamics. Control is sought over a given set of targets, in the sense of being able to change their configuration through external interventions on some well-chosen input nodes in the network, taking advantage of the network topology. We are interested in finding a minimal set of input nodes in the network such that the behavior of the target nodes may be changed arbitrarily through a well-chosen sequence of signals to the input nodes, cascaded throughout the network through its wiring. We focus on formalizations of this network controllability problem that maximize its applicability in biomedicine, including a specific set of targets to choose from (e.g., disease-specific essential genes), a specific set of inputs to choose from (e.g., drug targets), as well as non-linear network topologies. We discuss some of our recent results on the computational complexity of the structural targeted network controllability problem, some fast heuristics for it, and some applications in cancer medicine. 

Time: 3.11.2020, 13.00

Speaker: Professor Jöel Ouaknine from  MPI for Software Systems (Germany) and  University of Oxford (UK)

Title: Holonomic Techniques, Periods, and Decision Problems

Abstract: Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades. In this talk, I will give an overview of the area, and in particular will present a select survey of known and original results on decision problems for holonomic sequences and functions. I will also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I will relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier.

Parts of this talk will be based on the paper “On Positivity and Minimality for Second-Order Holonomic Sequences”, https://arxiv.org/abs/2007.12282