A4 Refereed article in a conference publication
The Levenshtein's Channel and the List Size in Information Retrieval
Authors: Ville Junnila, Tero Laihonen, Tuomo Lehtilä
Conference name: IEEE International Symposium on Information Theory
Publishing place: New York
Publication year: 2019
Journal: IEEE International Symposium on Information Theory
Book title : 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
Journal acronym: IEEE INT SYMP INFO
Series title: IEEE International Symposium on Information Theory
First page : 295
Last page: 299
Number of pages: 5
ISBN: 978-1-5386-9291-2
DOI: https://doi.org/10.1109/ISIT.2019.8849616
Abstract
The Levenshtein's channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C subset of F-2(n) has error-correcting capability e, we write t = e vertical bar l, (l >= 1). In this paper, we provide new bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound l + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound l + 1 is the best possible.
The Levenshtein's channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C subset of F-2(n) has error-correcting capability e, we write t = e vertical bar l, (l >= 1). In this paper, we provide new bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound l + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound l + 1 is the best possible.
UTU Research Portal