Average-radius list decoding of random linear matrix codes at rank-metric capacity
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00242
curl -X POST /api/v1/records/hexagon/2610.00242/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00242/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'