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)).|
|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|
|Pages:||1657 - 1667|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||IEEE TRANSACTIONS ON INFORMATION THEORY|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.