Technical Program

Paper Detail

Paper Title The Levenshtein's Channel and the List Size in Information Retrieval
Paper IdentifierMO2.R7.2
Authors Ville Junnila, Tero Laihonen, Tuomo Antinpoika Lehtilä, University of Turku, Finland
Session Substitution Errors
Location Bièvre, Level 5
Session Time Monday, 08 July, 11:40 - 13:00
Presentation Time Monday, 08 July, 12:00 - 12:20
Manuscript  Click here to download the manuscript
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\subseteq \F_2^n$ has error-correcting capability $e$, we write $t=e+\ell$, ($\ell\ge 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 $\ell+1$ on the list size for large enough $n$ provided that we have a sufficient number of channels. We also show that the bound $\ell+1$ is the best possible.