Skip to content
Preprint

List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding

Sep 2026 · 3 citations · 18 references
Computer Science Mathematics

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}.$

View source

Similar papers

Preprint Sep 2026

List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$

We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field $\mathbb{F}_q$. 1. Random linear codes over $\mathbb{F}_q$ with rate $1 - H_q(p) - \epsilon$ are $(p, O(q H_q(p)/\epsilon))$-list decodable with high probability for al...

Vinayak M. Kumar, Geoffrey Mon · 0 citations
Oct 2026

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon>0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optim...

Omar Alrabiah, Rohan Goyal, V. Guruswami · 3 citations · ⚡1
Preprint Oct 2026

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

We show that for any $R,\epsilon>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_\epsilon(1)$, and normalized distance at least $\delta_{\mathrm{GV}}(p,R)-\epsilon$. Here, $\delta_{\mathrm{GV}}(p,R)$ denotes the quantum...

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani et al. · 2 citations · ⚡1
Preprint Oct 2026

On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate

In this work, we investigate the hardness of computing minimum distance, as well as the hardness of syndrome decoding, for rank-metric codes. It is known (Gaborit and Z\'emor, IEEE TIT 2016) that for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$, minimum distance when $m=O(N)$ and syndrome decoding when $m=...

V. Gandikota, Vatsal Jha, S. Venkitesh · 0 citations
Preprint Oct 2026

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs....

R. Kondo, Yota Maeda · 0 citations
Preprint Nov 2026

The probabilistic bound for perfect hashing is sharp only for binary alphabets

We investigate the optimal asymptotic rate $R_q$ of perfect $q$-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let $B_q=-\log_2(1-q!/q^q)/(q-1)$ denote the classical probabilistic lower bound. We prove that $R_q=B_q$ if and only if $q=2$, establishing an explicit...

Shi-Tao Li, Min-Jia Shi · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.