math.IT — Information Theory

Average-radius list decoding of random linear matrix codes at rank-metric capacity

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

We show that for every fixed prime power $q$ and $0<p<1$, a uniformly random $\mathbb F_q$-linear rank-metric code in $\mathbb F_q^{n\times n}$ of rate $(1-p)^2-\varepsilon$ is, with high probability, average-radius list-decodable at radius $pn$ with list size $O_{p,q}(1/\varepsilon)$. This answers a question of Guruswami, Li and Singhal; the case $q=2$ was known. The failure probability is explicit and remains small when $\varepsilon$ depends on $n$ with $\varepsilon n^2\to\infty$. The proof combines a weighted affine extraction, span estimates for matrices from nearby rank shells, and Gaussian summation over rank profiles.