List-Decodable Zero-Rate Codes

Noga Alon, Boris Bukh, Yury Polyanskiy

This paper, authored by Noga Alon, Boris Bukh, and Yury Polyanskiy, explores a fundamental limit in coding theory: how the maximum error-correction radius of a code behaves as the number of codewords increases toward infinity in the "zero-rate" regime. The authors provide precise convergence rates for binary and spherical codes, revealing a surprising mathematical "hiccup" where the behavior changes significantly depending on whether the list size is even or odd.

TL;DR

The researchers determine how quickly the maximum list-decoding radius approaches its theoretical limit as more codewords are added. They prove that for even list sizes, the convergence rate is a "nice" $1/M$, but for a list size of 3, it slows down significantly to $M^{-2/3}$, disproving previous assumptions in the field.

What Problem Does This Paper Address?

In coding theory, we usually want to maximize the "rate" (how much information we send) for a given "radius" (how many errors we can fix). This paper looks at the extreme opposite: the zero-rate regime. Here, we ask: if we want to be able to decode a message into a small list of $L-1$ possibilities, what is the maximum fraction of errors $\tau$ we can handle?

As the number of codewords $M$ goes to infinity, this maximum radius $\tau$ settles at a well-known constant $\tau_L$. However, for a finite number of codewords $M$, the radius is slightly larger: $\tau = \tau_L + \epsilon$. The core question of this paper is: How fast does $\epsilon$ shrink as $M$ grows? This is a deep combinatorial problem that bridges coding theory, geometry, and Ramsey theory.

Methods

The authors employ several sophisticated mathematical tools to bound these convergence rates:

  • Linear Relaxation: They show that the problem of finding the "center" of a decoding ball in a discrete binary space can be relaxed to a continuous space $[0, 1]^n$ with negligible loss, making the geometry easier to handle.
  • Mean Radius Duality: They introduce the concept of "mean radius" ($mrad_\omega$) and use von Neumann's minimax theorem to show that the actual radius of a set of points is equal to the maximum mean radius over all possible probability distributions on those points.
  • Ramsey Theory: To prove upper bounds, they use hypergraph versions of Ramsey’s theorem to extract "well-behaved" subcodes from any sufficiently large code.
  • Graph-Theoretic Constructions: For the $L=3$ case, they use triangle-free Cayley graphs to construct codes that achieve the specific $M^{-2/3}$ rate.
  • Euclidean Geometry: For spherical codes, they utilize Jung’s theorem (which relates the radius of a set to its diameter) and Konyagin’s "repulsion" arguments.

Datasets

Not applicable. This is a theoretical research paper in mathematics and computer science; no empirical datasets were used.

Key Insights and Ideas

  • The Parity Gap: The most striking insight is that the convergence rate depends on the parity of $L$. For even $L$, the rate is $\Theta(M^{-1})$. For $L=3$ (odd), the rate is $\Theta(M^{-2/3})$. This suggests that odd list sizes are fundamentally "harder" or more complex to analyze than even ones.
  • Disproving the $1/M$ Conjecture: A previous claim in the literature suggested the rate was always $O(1/M)$ for all $L$. The authors provide a concrete counter-example for $L=3$, showing the rate is actually much slower.
  • Geometric Duality: The use of minimax theorems to bridge the gap between the "worst-case" radius (the distance to the furthest point) and the "average" radius (mean radius) provides a powerful framework for proving these bounds.

Key Results

  • Binary Codes (Even $L$): The convergence rate is exactly $\Theta(M^{-1})$. This extends classical results from the 1960s (Plotkin and Levenshtein) to all even list sizes.
  • Binary Codes ($L=3$): The rate is $\Theta(M^{-2/3})$. This is the first time this specific rate has been established for list decoding.
  • Spherical Codes: For codes on a unit sphere in Hilbert space, the authors prove the rate is at least $\Omega(M^{-1})$ and at most $O(M^{-\frac{2L}{L^2-L+2}})$.
  • Finite Convergence: They confirm that for any $\epsilon > 0$, the maximum number of codewords is finite, but they provide much tighter bounds on how finite.

Limitations and Future Work

  • Odd $L \ge 5$: While the authors solved $L=3$, the case for larger odd list sizes remains a major open problem. Currently, the best upper bounds for $L=5, 7, \dots$ are "towers of exponentials" due to the reliance on Ramsey theory, which is likely far from the truth.
  • Spherical Gap: There is still a gap between the lower and upper bounds for spherical codes. The authors conjecture that the true rate for spherical codes should be $O(1/M)$ for all $L$, but a proof remains elusive.
  • Code Length: The constructions used to prove the lower bounds often result in codes with very long block lengths (exponential in $1/\epsilon$). Finding "short" (linear length) codes that achieve these rates is an open challenge.

Summary updated

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 τ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</sub> . In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ(M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> ) 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-(2/3)</sup> ). For the similar question about spherical codes, we prove the rate is Ω(M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> ) and O(M- <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2L/L(2)-L+2)</sup> ).
BibTeX
@article{alon2019list,
  author = {Noga Alon and Boris Bukh and Yury Polyanskiy},
  title = {{List-Decodable Zero-Rate Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=AX3vYvPDqkx},
}

Loading related content...

Figure