Lower Bounds for all List-Decodable Deletion Codes
En palabras de los autores
A length- binary -deletion code is a set of binary strings such that if we delete any bits of a string, leaving a length- binary string, we can uniquely recover the codeword. In this paper, we consider -list decodable deletion codes, where after bits of a codeword are deleted, we can identify a list of size at most such that the original codeword lies in the list. We prove a lower bound of on the optimal size of a -list decodable -deletion code, giving a improvement over the previously best known bounds for -list decodable -deletion codes [GH21] and providing the first nontrivial lower bound when or . Our bound holds for all , showing that list decodable deletion codes have optimal size , asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.