CS Paper Radar

Affine Combiners for Reed-Solomon Proximity Gaps

Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, Kai Zhe Zheng

cs.IT cs.CCcs.CR ·submitted 2026-11-11 07:13 UTC · v2
theory

Abstract

Reed-Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius. We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(α+βx)g(x)$, where $α,β$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=ρn$, fixed $ρ\in(0,1)$ and $0<η<1-\sqrtρ$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrtρ+η)n\rceil$, with error $O_{ρ,η}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding. For $q\ge n^2$, our error is $O_{ρ,η}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $Ω_{ρ,η}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $Ω_{ρ,η}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed-Muller codes on subfield grids, obtaining MCA error $O_{ρ,η,k}(q^{-k})$ for fixed $ρ,η,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes

cs.IT ·2026-09-05 ·Fernando Granha Jeronimo
publishedhighly cited similarity 0.71
Abstract

We give a unified hidden-derivative framework for list decoding and mutual correlated agreement of ordinary Reed--Solomon codes over prime fields, on arbitrary prescribed evaluation sets. For every fixed slack $γ>0$, every sufficiently large block length $n$, every prime $q\ge n$, and every dimension $1\le k\le(1-γ)n$, a deterministic algorithm finds all codewords within relative distance $1-k/n-γ$ in $q^{O_γ(1)}$ time. The final list has size $n^{O_γ(1)}$, independently of $q$. Both statements extend to bounded-input-list recovery, with constants depending additionally on the input-list bound. For every fixed curve degree $\ell$, at most $n^{O_{γ,\ell}(1)}$ parameters on a curve $f_0+zf_1+\cdots+z^\ell f_\ell$ admit a nearby codeword whose exact agreement support is not a maximal jointly explained support of the coefficient words. For lines this gives MCA error $n^{O_γ(1)}/q$, with no proximity loss. The interpolation stage reparameterizes and optimizes the hidden-derivative construction of Brakensiek, Chen, Putterman, Zhang, and Zheng; differential root enumeration uses Kopparty's algorithm. We then prove that a specialization-safe differential equation has a cover by constant-dimensional varieties of polynomial cumulative degree, outside polynomially many parameter values. Intersecting these varieties with equations from the full agreement support yields both the field-size-independent list bound and exact-support MCA.

0.57

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

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

cs.IT ·2026-10-28 ·Ruho Kondo, Yota Maeda
similarity 0.65
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

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

The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound

cs.IT ·2026-10-27 ·Weijun Fang, Jing Qiu, Shu-Tao Xia, Fang-Wei Fu
surveytheory similarity 0.63
Abstract · 33 pages

In this paper, we study the minimum subpacketization of $(n,k)$ Reed-Solomon (RS) codes over $\mathbb{F}_{q^\ell}$ admitting cut-set-optimal exact $\mathbb{F}_q$-linear repair of every coordinate from any $d$ helpers. For $3\le k<d\le n-1$, write $s=d+1-k$ and denote this minimum by $\ell_{min}(n,k,d;q)$. Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish $\ell_{min}(n,k,d;q)\ge sG_s(d+1)$, where $G_s(m)$ is the minimum product of $m$ pairwise coprime integers, each at least $s$. Let $Δ_s(n,d)$ be the minimum of $lcm(a_1,\ldots,a_n)$ over positive integers $a_1,\ldots,a_n$ satisfying $lcm(a_j:j\in J\cup\{i\})\ge s~lcm(a_j:j\in J)$ for every $d$-subset $J\subseteq[n]$ and every $i\in[n]\setminus J$. We construct RS codes with subpacketization $sΔ_s(n,d)$ and further prove that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)=sG_s(n)$ whenever $d(d+2)\geq 4(n+1)$, for every prime power $q$. In particular, this determines the minimum subpacketization in the full-helper case $d=n-1$, resolving the corresponding exact linear-repair case of Open Problem 20 posed by Ramkumar et al. in their survey on codes for distributed storage. We further give a finite formula for $G_s(n)$ and determine the exact threshold for its closed-form expression in terms of the first $n$ primes. For fixed $k$ and $d$, we prove $\log\ell_{min}(n,k,d;q)= Θ_{k,d}(\log n\log\log n)$ as $n\to\infty$, using divisor-function estimates and cover-free families. An affine-plane construction shows that $Δ_s(n,d)<G_s(n)$ for some parameters, so $sG_s(n)$ is not a universal formula. We conjecture that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)$ for every prime power $q$ and all $3\le k<d\le n-1$.

0.43

Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls

cs.DC ·2026-09-01 ·Darya Melnyk
theory similarity 0.63
Abstract

This work considers the multidimensional approximate agreement problem. In this problem, $n$ parties in a distributed system, up to $t$ of which may be corrupted by a Byzantine adversary, need to output vectors that are close to each other and that lie inside the convex hull of all non-corrupted input vectors. We assume that nodes communicate in a fully-connected authenticated network and analyze synchronous and asynchronous communication models. The focus of this work is on the contraction factor of approximate agreement protocols. The first multidimensional approximate agreement protocols had a contraction rate of $1-1/n$(VG, PODC'13) and $\sqrt[d]{1/2}$(MH, STOC'13). While a rate below $1$ is sufficient for convergence, it is not sufficient for practical applications. To date, the best known convergence rate of approximate agreement algorithms is $\sqrt{7/8}\approx0.935$ (FN, DISC'18), which is achieved through the MidExtremes protocol. This stands in contrast to the lower bound on the convergence rate in the $1$-dimensional setting, which is $1/2$. In this work, we propose BallMidpoint - a novel approximate agreement protocol with a contraction rate of $1/\sqrt{2}\approx 0.707$ in the synchronous and the asynchronous communication models. This algorithm satisfies the optimal resilience under convex validity. The presented contraction rate is achieved by choosing the midpoint of the smallest enclosing ball of the so-called local safe areas, and it is tight for the presented algorithms. Similar to (FN, DISC'18), our algorithm is coordinate-free, and the point inside the safe area can be computed efficiently. This work presents the first multidimensional approximate agreement protocol where the convergence rate is closer to the best known lower bound rather than the upper bound of $1$.

0.39

An Optimal Gap-Majority Lemma for Bounded-Round Communication

cs.CC ·2026-10-15 ·Pachara Sawettamalya
similarity 0.62
Abstract

Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing whether $\sum_{i=1}^n f(X_i,Y_i)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we show that a minor adaptation of their approach, together with a more refined analysis, achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

0.25