Author: terolai

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: 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