CS Paper Radar

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

Kenta Kasai

cs.IT quant-ph ·submitted 2026-11-16 16:48 UTC · v1
theory

Abstract

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.

Comment
17 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

CPM-LDPC Codes Attaining the Minimum-Distance Bound

cs.IT ·2026-09-15 ·Kenta Kasai
theorycode/data similarity 0.79
Abstract · 13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.

0.35

Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes

cs.IT ·2026-10-04 ·Jianshen Zhu
similarity 0.70
Abstract

We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.

0.11

Hardness and Inapproximability of the Covering Radius for LDPC Codes

cs.IT ·2026-11-17 ·Massimo Battaglioni, Fabrizio Marinelli
theory similarity 0.69
Abstract

Given a binary parity-check matrix $H$ and an integer $r$, the covering-radius decision problem asks whether every attainable syndrome can be represented by an error vector of Hamming weight at most $r$. We study this problem for sparse parity-check matrices with bounded row and column weights. Using a bounded-occurrence quantified-SAT reduction, we prove that the problem is $Π_2^{\mathrm P}$-complete for matrices with maximum row and column weight three, and remains $Π_2^{\mathrm P}$-hard under a constant multiplicative gap. Starting from Vertex Cover on 3-regular graphs, we also obtain an explicit NP-hard approximation factor under the same weight constraints. We remark that weight three is the exact threshold for hardness: if either the maximum row weight or the maximum column weight is at most two, the covering radius can be computed in polynomial time.

0.12

Quantum LDPC and High-Rate CSS Codes from Fair-Density Parity-Check Codes

cs.IT ·2026-09-01 ·Hessam Mahdavifar
similarity 0.68
Abstract

We construct quantum LDPC (qLDPC) and high-rate CSS codes from our recently introduced classical fair-density parity-check (FDPC) codes. To this end, we introduce a structured sparsification of FDPC parity-check matrices, which reduces their check weights while preserving the underlying combinatorial structure and distance guarantees. Combined with the hypergraph-product construction, this yields finite-length qLDPC codes with analytically controlled blocklength, dimension, certified distance, and stabilizer weight. For quantum blocklengths $N<10^5$, the constructions introduced here span guaranteed rates from approximately $0.35\%$ to $25.8\%$ and certified quantum distances from $12$ to $69$, with stabilizer weights between $8$ and $16$. In the large-blocklength regime, allowing the FDPC order and sparsified check weight to scale moderately with blocklength yields a family of high-rate CSS codes, which we refer to as quantum FDPC (qFDPC) codes, with rate $R_Q$ and minimum distance $D$ satisfying \[ R_Q = 1-O\left(\frac{1}{\log\log N}\right), \ \ D=Ω(N^{1/4}), \] and stabilizer weight $O(\log N\log\log N)$. Finally, the analytically available FDPC weight distribution provides explicit information about the logical operators of the resulting hypergraph-product codes. Over the quantum erasure channel, this structure yields rigorous first-order maximum likelihood (ML) expressions and a higher-order weight-distribution approximation to the ML logical block error probability. This enables estimation of finite-length operating points and the onset of the error-floor regime. To the best of our knowledge, beyond surface-code-type constructions, this is the first finite-rate qLDPC framework to provide both finite-length certified minimum-distance information and an analytical characterization of low-weight logical multiplicities.

0.08

The list size of random linear and LDPC codes at capacity

cs.IT cs.DMmath.CO ·2026-09-06 ·Shashwat Silas
theoryhot direction similarity 0.65
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.

0.46

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.63
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

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
highly cited similarity 0.63
Abstract

We show that for any $R,ε>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_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.44

Quadratic bounds for uncompletable words and matrix mortality

cs.FL math.CO ·2026-09-25 ·Rahul Chandelkar, Samrath Singh Chadha
similarity 0.63
Abstract · Lean formalization and implementation pilot included as ancillary material

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

0.33