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