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 fall 2020 the seminar dates are Tuesdays afternoons (usually at 1pm) starting from 3rd November 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 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:
Meeting ID: 663 4770 4083
Passcode: email for passcode.
Join by SIP
Join by H.323
Meeting ID: 663 4770 4083


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”,


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. 


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”,