Categories
General

UTU Seminar in Discrete Mathematics

The Turku Seminar in Discrete Mathematics is a new seminar series, organized on  biweekly bases. The topics of the seminar cover a wide range of topics in Discrete Mathematics with international, national and local speakers. During spring 2021 the seminar dates are Tuesdays afternoons (usually at 1pm) starting from 9th March and the presentations will be streamed on Zoom (see link and details below). The seminar is open for everybody (including students).  The announcement of the first session is below. Welcome!
Note: if you are interested in giving a talk in the seminar, please contact one of the organizers.
Note for (PhD) students: it is possible to get 1 cu for a presentation and participation in 10 seminars.  

Organizers: Vesa Halava, Jarkko Kari, Tero Laihonen and Ion Petre

Seminar schedule spring 2021
9th March: Esa Sahla (UTU)
23rd March (Note: 12:00): Mikhail Barash (University of Bergen, Norway)
6th April: Anni Hakanen (UTU)
20th April: Ville Salo (UTU)
4th May: Alexander Tiskin (St. Petersburg State University, Russia)
18th May: TBA

Seminar schedule fall 2020:
3rd November: J. Ouaknine (MPI for Software Systems (Germany) and  University of Oxford (UK))
17th November: Ion Petre (UTU)
1st December: Tuomo Lehtilä (UTU)
15th December: Toni Hotanen (UTU)

Zoom details:
https://utu.zoom.us/j/66347704083
Meeting ID: 663 4770 4083
Passcode: email vesa.halava@utu.fi for passcode.
Join by SIP
66347704083@109.105.112.236
66347704083@109.105.112.235
Join by H.323
109.105.112.236
109.105.112.235
Meeting ID: 663 4770 4083

Categories
Session

4.5.2021 Alexander Tiskin

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.

Categories
Uncategorized

20.4.2021 Ville Salo

Time: 20.4.2021 at 13:00

Speaker: Ville Salo, University of Turku

Title: Self-simulable groups

Abstract: We say a group G simulates a subgroup H < G if every effective H-system on the Cantor set can be realized as a dynamical factor of the H-subaction of a tiling system on G. A theorem of Hochman shows that Z^3 simulates Z, and a theorem of Durand-Romashenko-Shen/Aubrun-Sablik shows that Z^2 simulates every effective subshift on Z. It is open whether any group simulates itself, but it is known that any such must be group is non-amenable and one-ended. We give the first examples of such self-simulable groups. The examples include almost all braid groups, [outer] automorphism groups of free groups, general linear groups over integers, Brin-Thompson groups nV, Burger-Mozes lattices, many right-angled Artin groups, and non-amenable branch groups. For almost all of these groups this also gives the first examples of strongly aperiodic tiling systems. In the talk, we give the necessary background, outline how self-simulation is obtained for the square of any non-abelian free group, and explain how to get the more interesting examples using closure properties.

Categories
Session

6.4.2021 Anni Hakanen

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.

Categories
Uncategorized

23.3.2021 Mikhail Barash

Time: 23.3.2021 at 12.00

Speaker: Mikhail Barash, University of Bergen, Norway

Title: Beyond Grammars and Parsing

Abstract: I will discuss how grammar models can be used to define syntax and static semantics of programming languages, and what the limitations of such models are. I will then talk about “projectional editing”, which enables direct manipulation of abstract syntax trees and does not require parsing. The talk is based on papers at STAF 2020 [ http://ceur-ws.org/Vol-2707/oopslepaper4.pdf ] and NIK 2020 [ https://ojs.bibsys.no/index.php/NIK/article/view/839 ].

Categories
Session

9.3. 2021 Esa Sahla

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.

Categories
Session

15.12.2020 Toni Hotanen

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.

Categories
Session

1.12.2020 Tuomo Lehtilä

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

Categories
Session

17.11.2020 Ion Petre

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. 

Categories
Session

3.11.2020 Joel Ouaknine

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