On the List-Decodability of Random Linear Rank-Metric Codes
Venkatesan Guruswami, Nicolas Resch · 2018
The list-decodability of random linear rank-metric codes is shown to match that of random rank-metric codes. Specifically, an Fq-linear rank-metric code over Fqm×nof rate R=(1-ρ)(1-[n/m]ρ)-ε is shown to be (with high probability) list-decodable up to fractional radius ρ ∈ (0,1) with lists of size at most [(Cp,q)/(ε)], where Cρ,qis a constant depending only on ρ and q. This matches the bound for random rank-metric codes (up to constant factors). The proof adapts the approach of Guruswami, Håstad, Kopparty (STOC 2010), who established a similar result for the Hamming metric case, to the rank-metric setting. A full version of this paper is accessible at https://arxiv.org/abs/1710.11516.