Paper Info
Title
On Levenshtein’s Channel and List Size in Information Retrieval
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 ⊆ \mathbb F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> has error-correcting capability e, we write t=e+ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> , ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> ≥ 1). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> +1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</i> +1 is the best possible. Most of our other new results rely on constant weight codes.
Year
DOI
Venue
2021
10.1109/TIT.2020.3016269
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Levenshtein’s channel,information retrieval,substitution errors,list decoding,Sauer-Shelah lemma
Journal
67
Issue
ISSN
Citations 
6
0018-9448
2
PageRank 
References 
Authors
0.37
0
3
Name
Order
Citations
PageRank
Ville Junnila14310.51
Tero Laihonen236339.39
Tuomo Lehtilä322.06