Abstract
In the study of error-correcting codes, the "zero-rate" regime focuses on the maximum number of messages that can be reliably transmitted when the message length is allowed to be arbitrarily large. This paper investigates the fundamental limits of list-decoding within this regime, specifically characterizing how the maximum code size $M$ grows as the decoding radius approaches a critical threshold $\tau_L$. The authors reveal a surprising geometric divergence between even and odd list sizes, demonstrating that while even list sizes follow a linear growth rate relative to the distance from the threshold, the case for $L=3$ exhibits a significantly faster growth of $\Theta(\epsilon^{-3/2})$.
Introduction
Classical coding theory typically focuses on maximizing the rate—the ratio of information bits to transmitted bits. However, the zero-rate regime offers a pure look at the combinatorial geometry of the space. In this context, we seek the maximum number of codewords $M$ that can be packed into a binary hypercube such that any ball of radius $\tau$ contains fewer than $L$ codewords. This is the essence of list-decoding.
For any list size $L$, there exists a well-known critical radius $\tau_L$. If the decoding radius is even slightly smaller than $\tau_L$, the number of codewords can be exponentially large. Conversely, if the radius is slightly larger (defined as $\tau_L + \epsilon$), the code size $M$ is finite. The central question addressed in this research is: as $\epsilon$ approaches zero, how rapidly does the maximum code size $M$ explode?
Methodology
The authors employ a multifaceted approach combining combinatorial geometry, probabilistic methods, and Ramsey theory to establish these bounds.
Linear Relaxation and Mean Radius
To simplify the discrete nature of the binary hypercube, the authors utilize a linear relaxation, treating the space as a continuous unit cube $[0,1]^n$. They introduce the concept of "mean radius"—the expected distance from a point to a randomly chosen codeword within a list. By applying von Neumann’s minimax theorem, they demonstrate that the actual radius of a code can be viewed as the maximum mean radius over all possible probability distributions on the codewords. This duality allows the problem to be framed as an optimization task.
Ramsey Theory and Graph-Theoretic Constructions
To establish upper bounds, the researchers use the hypergraph version of Ramsey’s theorem. This allows them to extract "monochromatic" subcodes—subsets of codewords that exhibit predictable, uniform behavior—making them susceptible to averaging arguments. For the specific case of $L=3$, the authors utilize triangle-free Cayley graphs to construct codes that exceed previously conjectured limits, proving that earlier assumptions about growth rates were incomplete.
Key Insights: The $L=3$ Anomaly
One of the most significant contributions of this work is the discovery of a "jump" in complexity when moving from unique decoding ($L=2$) to list-decoding with three candidates.
Historically, it was conjectured that the growth rate for all list sizes would be $O(1/\epsilon)$, following the pattern established by the Plotkin and Levenshtein bounds for unique decoding. The authors confirm this linear growth for all even $L$. However, they prove that for $L=3$, the growth rate is actually $\Theta(\epsilon^{-3/2})$. This indicates that odd-sized lists are subject to fundamentally different geometric constraints than even-sized ones.
This discrepancy arises from a dichotomy between "biased" and "random-like" codes. Large codes must either contain a biased subcode (where bits are not balanced) or behave like random noise. Because biased codes are naturally limited in size, the overall limit is dictated by how "random-like" the codewords can be while still maintaining the required distance properties.
Results Summary
- Binary Codes (Even $L$): The maximum code size is $\Theta(\epsilon^{-1})$. This result successfully generalizes the classical Plotkin bound to all even list sizes.
- Binary Codes ($L=3$): The maximum code size is $\Theta(\epsilon^{-3/2})$. This represents the first tight bound for a list size greater than 2 that deviates from the $1/\epsilon$ trend.
- Spherical Codes: For codes situated on a unit sphere in Euclidean space, the authors establish a lower bound of $\Omega(\epsilon^{-1})$ and a polynomial upper bound of $O(\epsilon^{-\frac{L^2-L+2}{2L}})$.
Discussion and Future Work
While the $L=3$ case has been resolved, the behavior for larger odd list sizes ($L \ge 5$) remains an open challenge. Current upper bounds for these cases rely on Ramsey theory and result in "towers of exponentials," which are likely far from the true values.
Furthermore, a gap remains in the understanding of spherical codes. While the authors provide a polynomial upper bound, they conjecture that the true growth rate for spherical codes is $O(1/\epsilon)$ for all $L$. Finally, the current constructions for optimal codes require extremely large block lengths ($n$), leaving the search for "short" optimal codes as a significant practical hurdle for future research.
Summary updated