CS Paper Radar

The list size of random linear and LDPC codes at capacity

Shashwat Silas

cs.IT cs.DMmath.CO ·submitted 2026-09-06 12:31 UTC · v2
theoryhot direction

Abstract

We show that for every prime power $q$ and $ρ\in(0,1-\frac1q)$ there exists $\varepsilon_0(q, ρ) > 0$ such that for all positive $\varepsilon < \varepsilon_0(q, ρ)$, a random linear code over $\mathbb{F}_q$ of rate $1-h_q(ρ)-\varepsilon$ has list size $\lfloor h_q(ρ)/\varepsilon\rfloor$ or $\lfloor h_q(ρ)/\varepsilon\rfloor+1$ with probability $1-o(1)$. Before this work, the list size was known only up to a constant factor for $q\ge3$, and for $q=2$ it was known to be either $\lfloor h_2(ρ)/\varepsilon\rfloor-1$, $\lfloor h_2(ρ)/\varepsilon\rfloor$ or $\lfloor h_2(ρ)/\varepsilon\rfloor+1$. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT ·2026-09-01 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.81
Abstract · 32 pages

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-λ/q$ with fixed $λ>1$, the required leading constant can be as large as $\left(\frac{\logλ}{eλ}+o_q(1)\right)\frac{q}{\log q}.$

0.44

Average-Radius List-Decodability of Random Linear Codes

cs.IT cs.CCmath.CO ·2026-08-23 ·Venkatesan Guruswami, Shilun Li, Mihir Singhal
theoryhot directionhighly cited similarity 0.76
Abstract

We prove that for every prime power $q$ and every $p \in (0, 1-1/q)$, a random $\mathbb{F}_q$-linear code of rate $1 - h_q(p) - ε$ is $(p, C_{p,q}/ε)$-average-radius list-decodable with probability at least $1 - q^{-Ω(n)}$, i.e., for every center $y \in \mathbb{F}_q^n$, the $C_{p,q}/ε$ codewords closest to $y$ have average fractional Hamming distance at least $p$ from $y$. This extends a similar result for (standard) list-decoding due to Guruswami, Håstad, and Kopparty (2010) to the stronger average-radius guarantee, with the same $O(1/ε)$ list size. For average-radius list-decoding, such a result was previously known only for binary linear codes (Guruswami, Li, Mosheiff, Resch, Silas, and Wootters, 2021) and for general (non-linear) random codes over arbitrary alphabets (Elias, 1991).

0.46

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

cs.IT cs.CCcs.DSmath.CO+1 ·2026-09-15 ·Vinayak M. Kumar, Geoffrey Mon
publishedtheoryhighly cited similarity 0.69
Abstract

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) - ε$ are $(p, O(q H_q(p)/ε))$-list decodable with high probability for all values of $p, q, ε$, including the high error regime. This nearly matches the list size lower bound of $H_q(p)/ε$ due to Guruswami, Li, Mosheiff, Resch, Silas, and Wootters [IEEE Trans. Inf. Theory 2022]. Our bound is the first uniform improvement for $q > 2$ since Guruswami, Håstad, and Kopparty [STOC 2010]. 2. Linear hash functions over $\mathbb{F}_q$ hashing $n$ balls to $n$ bins achieve maximum load $O(q \ln \ln q / {\ln q}) \cdot \ln n / {\ln \ln n}$, both in expectation and with probability $1-o(1)$. This nearly matches the lower bound of $\ln n / {\ln \ln n}$. Previously, only a polylogarithmic upper bound was known for $q > 2$, due to Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos [J. ACM 1999]. We reduce list decodability and linear hashing to strong Furstenberg set lower bounds, which we prove using a new polynomial method of multiplicity gaps. While previous polynomial methods analyze a set $S$ by studying polynomials that vanish on it, we consider polynomials that vanish everywhere, but with higher multiplicity inside $S$ than outside.

0.43

Vanishing Relative Distance of Uniformly Random CSS LDPC Codes Built from Permutation Matrices

cs.IT quant-ph ·2026-11-16 ·Kenta Kasai
theory similarity 0.65
Abstract · 17 pages, 1 figure

Classical random regular low-density parity-check codes can have minimum distance growing linearly with block length. We study CSS check matrices formed as full $J\times L$ arrays of arbitrary $P\times P$ permutation matrices, sampled uniformly subject to commutation. For fixed column weight $J\ge3$ and fixed even row weight $L>2J$, we prove that the relative minimum distance converges to zero in probability as $P\to\infty$, with block length $n=LP$. We analyze the weight enumerators that count all nontrivial logical representatives after excluding stabilizers. A coefficientwise lower bound shows that, at every fixed relative weight $0<α<1$ along even-weight sequences, exponentially many such representatives exist with high probability. Their typical and mean counts have exponent lower bound $h_2(α)/2$, where $h_2$ is the binary entropy function. We compare this bound with the classical LDPC and dense CSS mean weight-distribution exponents. The existence, with high probability, of a logical operator below every fixed target weight $δn$ yields the distance conclusion.

0.13

Thresholds for Local Coordinate-Wise Linear Properties of Random One-Point AG Codes

cs.IT ·2026-10-08 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.64
Abstract · 37 pages

Local coordinate-wise linear (LCL) properties provide a unified framework for studying list decoding, list recovery and other local properties of linear codes. We prove that random one-point algebraic geometry (AG) codes have the same LCL threshold rates as random linear codes under explicit alphabet and sampling conditions. More precisely, for a family of local profiles with random linear code threshold $R_{\mathcal P}$, a random one-point AG code avoids all such profiles below $R_{\mathcal P}-\varepsilon$ and contains one above $R_{\mathcal P}+\varepsilon$, with explicit failure bounds on both sides. Our proof also removes an auxiliary lower bound on the number of available rational places that arises in a direct adaptation of the Reed--Solomon argument and requires no additional genus-dependent rate gap. We also observe that the previously claimed above threshold proof for random Reed--Solomon codes does not establish the required probability lower bound. The containment relation used in that argument gives the probability comparison in the opposite direction from what is needed. We give a different above threshold argument, which in particular also yields an alternative proof in the genus zero case. Combining our threshold theorem with recent results for random linear codes gives a collection of new list decoding, average weight list decoding and list recovery guarantees for random one-point AG codes. We further obtain new correlated agreement and proximity gap results for polynomial curves. These results extend the LCL threshold framework from random linear and Reed--Solomon codes to random one-point AG codes.

0.18

Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields

cs.IT cs.CC ·2026-10-11 ·Minshen Zhu
similarity 0.63
Abstract

Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

0.36

Optimal Universal Coding of Integers

cs.IT ·2026-10-01 ·Wei Yan, Yunghsiang S. Han, Leqian Zheng
similarity 0.63
Abstract

Universal coding of integers (UCI) provides prefix codes for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length under $P$ stays within $K$ times $\max\{1,H(P)\}$. For a given UCI $\mathcal{C}$, the smallest such constant $K$ is called the minimum expansion factor of $\mathcal{C}$, denoted $C_{\mathcal{C}}^{*}$. Let $C^{*}\triangleq \inf \{C_{\mathcal{C}}^{*}\}$ over all UCIs. A UCI attaining $C^{*}$, or a family of UCIs attaining $C^{*}$ in the limit, is called optimal. It is currently known that $2\le C^{*}\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every UCI, a distribution in this family attains the worst-case ratio; thus, the family is least favorable for the UCI problem. We further establish an inequality, called the \emph{UCI inequality}, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B\ge 1$, it decides whether $B$ lies below or above $C^*$. The UCI inequality gives an equivalent definition of $C^*$. By numerical computation, we determine $C^* = 2.00012475703610197861701176297579886254\cdots$, the first $38$ decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.

0.19

Quantum List Recovery and Decoding: Achievability and Limitations

cs.IT quant-ph ·2026-09-30 ·Fernando Granha Jeronimo, Xiaojuan Ma
theory similarity 0.63
Abstract

Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the \(X\)- and \(Z\)-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let \(R\in(0,1)\) be the quantum rate and \(R_1=(1+R)/2\) the common component rate. As the radius \(ρ=(1-R)/2-γ\) approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, \[ L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint \(X/Z\) candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.

0.34