List-decodable zero-rate codes

Noga Alon, Boris Bukh, Yury Polyanskiy

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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

Original languageEnglish (US)
Article number8456617
Pages (from-to)1657-1667
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - Mar 2019

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Euclidean space
  • Hamming space
  • List decoding
  • error correction codes


Dive into the research topics of 'List-decodable zero-rate codes'. Together they form a unique fingerprint.

Cite this