The list-decodable code has been an active topic in theoretical computer science.There are general results about the list-decodability to the Johnson radius and the list-decoding capacity theorem. In this paper we show that rates, list-decodable radius and list sizes are closely related to the classical topic of covering codes. We prove new general simple but strong upper bounds for list-decodable codes in general finite metric spaces based on various covering codes. The general covering code upper bounds can be applied to the case that the volumes of the balls depend on the centers, not only on the radius. Then any good upper bound on the covering radius or the size of covering code imply a good upper bound on the sizes of list-decodable codes. Our results give exponential improvements on the recent generalized Singleton upper bound in STOC 2020 for Hamming metric list-decodable codes, when the code lengths are large. A generalized Singleton upper bound for average-radius list-decodable codes is also given from our general covering code upper bound. Even for the list size $L=1$ case our covering code upper bounds give highly non-trivial upper bounds on the sizes of codes with the given minimum distance. We also suggest to study the combinatorial covering list-decodable codes as a natural generalization of combinatorial list-decodable codes. We apply our general covering code upper bounds for list-decodable rank-metric codes, list-decodable subspace codes, list-decodable insertion codes list-decodable deletion codes and list-decodable sum-rank-metric codes. Some new better results about non-list-decodability of rank-metric codes, subspace codes and sum-rank-metric codes are obtained.
翻译:在理论计算机科学中, 列表标记代码是一个活跃的主题。 包含代码上限界限的通用代码可以适用于球量取决于中心, 不仅在半径上。 然后, 在覆盖半径或列表解码能力标语中, 任何好的上限都意味着在列表标记代码的大小上有一个良好的上限。 在覆盖代码的经典主题上, 我们的结果表明, 在基于各种覆盖代码的普通有限计量空间中, 列表标记代码具有新的简单但强大的上界。 覆盖代码的普通代码中, 覆盖代码上限的通用单吨上限可以适用于球量取决于中心, 不仅取决于半径。 然后, 在覆盖代码半径或列表解码的大小上下限中, 任何好的上限都意味着列表半径或列表的分解码的大小上下限。 我们的最近通用SteOC 2020 的 Starton 上限定义有指数的指数, 当代码长度大时, 我们的普通可下限列表的上限代码中也具有通用的上限的上限。 即使列表的列表中的列表值为 $=1美元, 包含代码的上限, 我们的上限的上限的代码的上层的代码的上限的代码中, 我们的上限的上层的代码中, 也显示的上限的上限的代码。