Source-linked AI summary
On the List-Decodability of Random Linear Codes
Venkatesan Guruswami, Johan Hastad, Swastik Kopparty
TL;DR
The paper asks whether linear codes require much larger lists than general codes near the rate 1−Hq(p). It analyzes low-rank structure through random vectors and their spans, proving that random linear codes achieve near-capacity list-decodability with list size O(1/ε).
Problem
The paper asks whether linear codes can achieve list sizes close to the O(1/ε) bound known for general codes at rate 1−Hq(p)−ε.
Method
The proof reduces random linear-code list-decodability to weight distributions of constant-dimensional random linear codes and controls low-rank subsets via Hamming-ball span bounds.
Results
A random Fq-linear code of rate 1−Hq(p)−ε is (p, Cp,q/ε)-list-decodable with high probability.
Takeaways & Limitations
Linear codes match general random codes up to constant factors in list size, resolving the open question over all finite-field alphabets.
Takeaways & Limitations
The result assumes p<1−1/q, since decoding from at least that error fraction is impossible except for trivial codes.
Abstract
from arXiv · showhide
For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $ε> 0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-ε)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/ε)$ codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of $O(1/ε)$ suffices to have rate within $ε$ of the "capacity" $1-H_q(p)$. Our result matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of $q^{O(1/ε)}$. The main technical ingredient in our proof is a strong upper bound on the probability that $\ell$ random vectors chosen from a Hamming ball centered at the origin have too many (more than $Θ(\ell)$) vectors from their linear span also belong to the ball.
1 Introduction
List decoding studies how code rate, correctable error fraction, and output list-size trade off, with capacity 1−Hq(p) as the target rate. This work shows that random linear codes achieve near-capacity list-decodability with list size O(1/ε), matching general random codes up to constants.
- List decoding allows a decoder to output a bounded candidate list containing every codeword within pn errors, with list-size measuring maximum ambiguity.
- For q-ary codes, the capacity benchmark is rate 1−Hq(p), with p restricted to below 1−1/q.
- Lq,p(ε) asks what list size suffices for q-ary codes of rate at least 1−Hq(p)−ε, and this size must diverge as ε approaches zero.
- General random codes achieve list size O(1/ε), whereas prior linear-code bounds could be exponentially worse.
- The paper proves Llin_q,p(ε) ≤ Cq,p/ε and that random linear codes attain list size Cp,q/ε with high probability.
- The proof controls low-rank codeword subsets through a bound showing that random vectors in a Hamming ball rarely have too many span vectors remaining in that ball.
2 Results and Methods
The paper proves that random linear codes achieve list sizes O(1/ε) near rate 1−H_q(p), using bounds on spans of random points in Hamming balls and a Ramsey-theoretic argument.
- Main results: O(1/ε) list size suffices for random linear codes at rate 1−H_q(p)−ε over fixed finite fields.The result applies to q-ary linear codes for p ∈ (0,1−1/q).
- Proof strategy: The proof reduces list-decodability at linear dimension to the weight distribution of constant-dimensional random linear codes.This reduction forms the combinatorial core of the argument.
- Proof strategy: For p ∈ (0,1/2), ℓ=o(√n) independent uniform points from B_n(0,p) have more than C·ℓ span points in the ball with probability at most 2^-5n.This span bound is the central probabilistic ingredient.
- Proof strategy: The proof bounds the probability for each large subset S of coefficient vectors by finding a translated structured subset containing an increasing chain, then applies a union bound.The increasing-chain structure is obtained through a Ramsey-theoretic lemma proved using the Sauer-Shelah lemma.
- Larger alphabet: The q-ary extension follows the same outline but uses a non-standard larger-alphabet generalization of the Sauer-Shelah lemma.The geometric arguments otherwise generalize readily to constant q.
3 Proof of Theorem 2
The proof reduces list-decodability to bounding the probability that a random linear code has a large intersection with some Hamming ball. A union bound over low-rank subsets, combined with the span estimate, yields the theorem.
- Reduction to bad balls: The proof studies the probability that some Hamming ball contains more than L codewords of a random linear code.It analyzes Pr_C,x[|B_n(x,p) ∩ C| > L].
- Low-rank configurations: Any bad ball contains a translated set generated by linearly independent codewords, so the argument enumerates such low-rank configurations.The construction uses a maximal independent subset or L+1 independent vectors, depending on the intersection size.
- Low-rank configurations: Conditioned on previously included independent vectors, each additional vector enters the random subspace with probability 2^(Rn+1−n).This follows from the dimensions of the ambient and random subspaces after conditioning.
- Conclusion: Combining the tuple bounds with the union bound establishes the claimed high-probability list-decodability theorem.The proof assembles the estimates from the two ℓ regimes into an upper bound on the bad-ball probability.
- Counting cases: For ℓ < 4/ε, Theorem 3 bounds the number of problematic tuples by |B_n(0,p)|^ℓ 2^-5n.For ℓ ≥ 4/ε, the proof instead uses the trivial estimate |F_ℓ| ≤ |B_n(0,p)|^ℓ.
4 Proof of Theorem 3
The proof of Theorem 3 shows that a small collection of random points in a Hamming ball is very unlikely to have too many span points in the same ball. A combinatorial increasing-chain argument and a two-sample estimate provide the exponential bound.
- Pairwise estimate: Lemma 7 gives an exponentially small bound, 2^-δ_p n, for two independent ball samples whose sum lies in any radius-p ball.The estimate holds uniformly for every x ∈ F_n.
- Main span bound: Theorem 3 states that for ℓ = o(√n), the span of ℓ independent uniform samples from B_n(0,p) contains more than C·ℓ ball points with probability at most 2^-5n.Here p ∈ (0,1/2), n is sufficiently large, and C is a constant depending on p.
- Increasing-chain argument: The proof bounds selected collections of linear combinations of the samples by applying the two-sample estimate along a large c-increasing chain.The chain supplies many combinations whose coordinates can be controlled through pairs of sampled vectors.
- Increasing-chain argument: A union bound over all sets of L+1 span combinations shows that the probability of more than L ball points is exponentially small.Taking L = C·ℓ and choosing C sufficiently large completes the theorem.
5 Proof of Lemma 5
Lemma 5 supplies the combinatorial structure needed by the span argument: every sufficiently large set of binary vectors contains a translate with a long increasing chain. The proof uses Sauer–Shelah and induction.
- Inductive construction: The proof invokes the Sauer–Shelah lemma to find c coordinates on which a large set realizes every binary pattern.This coordinate set enables the inductive construction of the chain.
- Inductive construction: After fixing a frequent restriction on selected coordinates, the argument reduces to a smaller-dimensional set with at least L/2^c elements.The reduced set is formed from vectors sharing the chosen restriction.
- Inductive construction: The induction yields a chain length satisfying d′ ≥ (1/c)log(L/2^c+1) − (1−1/c)log(ℓ−c).A complementary vector and a suitable translate complete the required support property.
6 Larger alphabets
The binary span analysis extends to every fixed prime-power alphabet by replacing the binary combinatorial lemma with a q-ary increasing-chain result. A specialized q-ary Sauer–Shelah statement avoids the exponential loss of the traditional generalization.
- q-ary span theorem: Theorem 10 gives the q-ary span bound for p ∈ (0,1−1/q) and ℓ = o(√n), with constants depending on q.The samples are chosen independently and uniformly from the q-ary Hamming ball B_n^q(0,p).
- q-ary increasing chains: The q-ary proof follows the binary strategy by bounding probabilities through a large c-increasing chain.The chain is obtained from a q-ary analogue of Lemma 5.
- q-ary combinatorics: The traditional Karpovsky–Milman bound would require a set larger than 2^ℓ in this application, leading to exponential list-size bounds.The paper therefore develops a different combinatorial property tailored to the proof.
- q-ary combinatorics: The q-ary Sauer–Shelah lemma finds c coordinates such that every q-ary pattern differs from some restricted vector in every coordinate.Its threshold is |S| > 2·((q−1)·ℓ)^(c−1).
- q-ary combinatorics: An induction on dimension and c proves the lemma by partitioning projected vectors according to whether one or at least two final-coordinate values occur.The two projection sets are S1 and S2, whose sizes satisfy |S| ≤ |S1| + (q−1)|S2|.
7 Proof of q-ary increasing chain lemma
The proof establishes Lemma 12 by induction on the ambient dimension, reducing the nontrivial case to a coordinate restriction and an induced smaller-dimensional set. Once Lemma 12 is available, the q-ary theorem follows by the same strategy as the binary analogue.
- Lemma 12 is proved by induction on ℓ, with the claim immediate when ℓ ≤ c.
- When L ≤ 2((q −1) · ℓ)^(c−1), the lemma is treated as trivial; otherwise Lemma 13 supplies c coordinates U with the required coverage property.
- A value u0 is selected so that at least L/q^c vectors in S restrict to u0 on U, producing a smaller set S′ with |S′| ≥ L/q^c.
- The induction hypothesis is then applied to the restricted set S′, after which vectors w and v1, …, vd are constructed to satisfy the desired properties.
- Given Lemma 12, Theorem 10 follows virtually identically to its binary analogue, and Theorem 6 follows from Theorem 10 as Theorem 2 followed from Theorem 3.