Welcome to the resource topic for 2025/870
Title:
From List-Decodability to Proximity Gaps
Authors: Yiwen Gao, Dongliang Cai, Yang Xu, Haibin Kan
Abstract:Proximity testing for linear codes is a fundamental problem in coding theory with critical applications in cryptographic protocols, blockchain, and distributed storage systems. This work addresses the proximity gaps for linear codes, a crucial aspect for efficiently verifying whether a batch of codewords is close to a given code. We present a general framework for deriving proximity gaps from the list-decodability properties of the underlying linear code.
Our main result shows that if a code C\subseteq \mathbb{F}_q^n is (p,L)-list-decodable, then the probability that a random combination of a batch of t codewords containing a \delta-far codeword (for \delta\le 1-\sqrt{1-p+\varepsilon}) remains \delta-far from C is bounded by O(\frac{tL^2pn}{q}+\frac{t}{\varepsilon q}). This result also establishes a form of (mutual) correlated agreement for linear codes, which can be used to strengthen soundness analyses in protocols that rely on proximity testing, thereby reducing query complexity and enabling practical instantiations over smaller finite fields.
In particular, we apply our main result to randomly punctured Reed–Solomon codes and folded Reed–Solomon codes—both of which are known to achieve list-decodability up to capacity—and derive linear proximity gaps for these families under the Johnson bound.
ePrint: https://eprint.iacr.org/2025/870
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .