AI & ML
List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
arXiv math.IT0 views
arXiv:2609.01070v2 Announce Type: replace Abstract: Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power $q$ and $p\in(0,1-1/q)$, random linear codes of rate $1-h_q(p)-\varepsilon$ have list size $\frac{h_q(p)}{\varepsilon}\cdot(1+o(1))$ as $\varepsilon\to0$, both for list decoding and average-radius list decoding. The conjecture was known for $q=2$ and remained open for larger alphabets. We prove the conjecture for list decoding for every prime power $q$, with the sharper bound $L=\frac{h_q(p)}{\varepsilon}+O_{p,q}(1).$ In contrast, we disprove the conjecture for average-radius list decoding. We show that the required list-size leading constant is at least $p\left(1+\log_q\frac{(q-1)(1-p)}{p}\right)$, which is strictly larger than $h_q(p)$ whenever $q^p(1-p)>1$. Moreover, for $p=1-\lambda/q$ with fixed $\lambda>1$, the required leading constant can be as large as $\left(\frac{\log\lambda}{e\lambda}+o_q(1)\right)\frac{q}{\log q}.$
Source:https://arxiv.org/abs/2609.01070PreviousHermitian Hulls of Cyclic Codes and Exact Dual Distances of Extended Linear CodesNextThe Cross-Correlation Distribution of the Niho-Type Decimation $d=4(2^m-1)+1$
Related posts
Your CI is red because of code you didn't write
0dev.to OpenSource
Summer 2026 Internships: 8 New Openings This Week (Nov 2)
0dev.to Programming
Ruby Receptionist Alternatives: 5 Options Compared (2026)
0dev.to Programming
Why coding agents break prompt caching (and how to fix it)
0dev.to Programming
I Launched My Company Website, Made Task Monitor Free, and Opened Custom Project Requests
0dev.to AI
How I turn Hacker News, GitHub and npm into product ideas every 3 hours
0dev.to AI