Skip to main content

List-Decodable Zero-Rate Codes

Author(s): Alon, Noga M.; Bukh, Boris; Polyanskiy, Yury

To refer to this page use:
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 tau is an element of[0, 1] for which there exists an arrangement of M halls of relative Hamming radius tau 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 -> infinity the maximal tau decreases to a well-known critical value tau(L). In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Theta(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 Theta(M-(2/3)). For the similar question about sherical codes, we prove the rate is Omega(M-1) O(M-(2L/L2-L+2)).
Publication Date: Mar-2019
Electronic Publication Date: 6-Sep-2018
Citation: Alon, Noga, Bukh, Boris, Polyanskiy, Yury. (2019). List-Decodable Zero-Rate Codes. IEEE TRANSACTIONS ON INFORMATION THEORY, 65 (1657 - 1667. doi:10.1109/TIT.2018.2868957
DOI: doi:10.1109/TIT.2018.2868957
ISSN: 0018-9448
EISSN: 1557-9654
Pages: 1657 - 1667
Type of Material: Journal Article
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.