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

Original language | English (US) |
---|---|

Article number | 8456617 |

Pages (from-to) | 1657-1667 |

Number of pages | 11 |

Journal | IEEE Transactions on Information Theory |

Volume | 65 |

Issue number | 3 |

DOIs | |

State | Published - Mar 2019 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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