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 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)).