CS Paper Radar

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

Yota Maeda, Ruho Kondo

cs.IT ·submitted 2026-11-12 02:10 UTC · v1
theory

Abstract

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

Comment
25 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.74
Abstract · 13 pages, 5 figures,

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. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

0.23

Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size

cs.IT cs.DSmath.CO ·2026-09-04 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.73
Abstract

We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero function in the underlying function space. Our proof generalizes the results of Con, Guo, Li, and Zhang (ICALP 2025), and simultaneously simplifies their arguments by avoiding an in-depth analysis of longest common subsequences. We demonstrate the applicability of our core theorem by instantiating it with random puncturings of Reed--Muller codes. We then recover the result that random Reed--Solomon codes approach the half-Singleton bound over linear-sized fields while also improving the dependence on the additive gap $\varepsilon$ from $2^{O(1/\varepsilon^2)}$ to $2^{O(1/\varepsilon)}$. Finally, by applying the framework to algebraic geometry codes arising from asymptotically good towers of function fields, we show that there exist randomized families of structured linear codes over constant-sized fields that approach the half-Singleton bound.

0.34

Random Algebraic Geometry Codes Approach the Half-Singleton Bound for Insertions and Deletions

cs.IT ·2026-09-06 ·Zhihao Guan, Hengjia Wei
theory similarity 0.71
Abstract · 25 pages

In this paper, we study the performance of algebraic geometry (AG) codes against adversarial insertion-deletion (insdel) errors. The half-Singleton bound states that an $[n,k]_q$ linear code can correct at most $n-2k+1$ insdel errors. It was recently proven that random Reed-Solomon codes approach this bound. However, these constructions require the field size $q$ to grow linearly with the code length $n$. We overcome this barrier by extending the probabilistic analysis of general linear insdel codes to AG codes. We demonstrate that curves with many rational points allow for nearly optimal codes over significantly smaller alphabets. We prove the following main asymptotic results: (1) For general smooth complete curves of fixed genus, random AG codes are nearly optimal, that is, they can correct $(1-\varepsilon)n-2k$ insdel errors with high probability over linear-sized fields ($q=Θ(n)$). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size $q=Θ(n^{2/3})$, breaking the linear field size barrier. (3) Using asymptotically optimal García-Stichtenoth towers, we prove the existence of random AG codes that approach the half-Singleton bound with high probability over fields of size $q=2^{O_R(1/\varepsilon^2)}$, independent of $n$.

0.39

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.71
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.70
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.51

New Results on the Subfield Metric

cs.IT ·2026-11-13 ·Ana Kosovac, Jeanette Plechinger, Nikola Spirovski, Violetta Weger
similarity 0.70
Abstract

In this paper, we further develop the theory of the recently introduced $λ$-subfield metric. We investigate extremal codes, classical bounds and asymptotic densities in this setting. We first study codes attaining a Singleton-type bound, called Maximum $λ$-subfield Distance (M$λ$D) codes. We establish structural restrictions on their parameters and extend the theory to sublinear codes. We then investigate the asymptotic density of M$λ$D codes in several parameter regimes and compare their behavior with that of MDS and MRD codes. We then turn to a Plotkin-like bound, where we construct a family of constant-weight codes attaining the bound and classify all non-degenerate linear constant-weight codes for $λ>1$. Finally, we complement the collection of classical coding-theoretic bounds available for the $λ$-subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds.

0.11

On Proximity Gaps for One-Point Algebraic Geometric Codes

cs.IT ·2026-10-29 ·Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu
theory similarity 0.69
Abstract · 43 pages

Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over $\mathbb F_q$ with designed distance $n-m$, write $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrtρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $σ<1$, with positive limiting rate and relative error radius.

0.22