{"id":"arxiv/2609.06570","url":"https://arxiv.org/abs/2609.06570","tags":["cs.IT","cs.DM","math.CO"],"score":0,"title":"The list size of random linear codes at capacity","domain":"cs.IT","source":"arxiv","authors":["Shashwat Silas"],"reviews":0,"subject":"cs.IT","summary":"Let $C \\le \\mathbb{F}_q^n$ be a uniformly random $\\mathbb{F}_q$-linear code of rate $1 - h_q(ρ) - \\varepsilon$, and let $L^*(C,ρ)$ be the least $L$ such that every Hamming ball of relative radius $ρ$ contains at most $L$ codewords of $C$. That $L^* = Θ_{q,ρ}(1/\\varepsilon)$ has been known since work of Guruswami, Håstad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\\varepsilon$ is at least $h_q(ρ)$ for all $q$, along with an upper bound special to $q = 2$ which narrowed $L^*$ to within three consecutive…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-06","reactions":{}}