@article{6975646e01a44e0481950bd876351bd9,
title = "List-decodable zero-rate codes",
abstract = " We consider list decoding in the zero-rate regime for two cases - the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ϵ [0,1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by L or more of them. As M → ∞ the maximal τ decreases to a well-known critical value τ L . In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ (M -1 ) when L is even, thus extending the classical results of Plotkin and Levenshtein for L=2. For L=3 , the rate is shown to be Θ (M -(2/3) ). For the similar question about spherical codes, we prove the rate is Ω (M -1 ) and O(M- (2L/L 2 -L+2) ). ",
keywords = "Euclidean space, Hamming space, List decoding, error correction codes",
author = "Noga Alon and Boris Bukh and Yury Polyanskiy",
note = "Funding Information: Manuscript received November 4, 2017; revised May 16, 2018 and August 18, 2018; accepted August 23, 2018. Date of publication September 6, 2018; date of current version February 14, 2019. This work was supported in part by ISF under Grant 281/17, in part by GIF under Grant G-1347-304.6/2016, and in part by the Simons Foundation. N. Alon was supported in part by a BSF Grant, in part by an ISF Grant and a in part by GIF Grant. B. Bukh was supported in part by the Sloan Research Fellowship and in part by the U.S. taxpayers through NSF CAREER under Grant DMS-1555149, in part by NSF under Grant DMS-1301548, and in part by LabEx B{\'e}zout under Grant ANR-10-LABX-58. Y. Polyanskiy was supported in part by the NSF under Grant CCF-13-18620 and Grant CCF-17-17842 and in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under Grant CCF-09-39370. Part of the work was done when B. Bukh was on visit to the Universit{\'e} Paris-Est Marne-la-Vall{\'e}e. Funding Information: This work was supported in part by ISF under Grant 281/17, in part by GIF under Grant G-1347- 304.6/2016, and in part by the Simons Foundation. N. Alon was supported in part by a BSF Grant, in part by an ISF Grant and a in part by GIF Grant. B. Bukh was supported in part by the Sloan Research Fellowship and in part by the U.S. taxpayers through NSF CAREER under Grant DMS-1555149, in part by NSF under Grant DMS-1301548, and in part by LabEx B?zout under Grant ANR-10-LABX-58. Y. Polyanskiy was supported in part by the NSF under Grant CCF-13-18620 and Grant CCF-17-17842 and in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under Grant CCF-09-39370. Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",
year = "2019",
month = mar,
doi = "10.1109/TIT.2018.2868957",
language = "English (US)",
volume = "65",
pages = "1657--1667",
journal = "IRE Professional Group on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "3",
}