Locality of Curve-Decoding and Improved Proximity Gaps

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Locality of Curve-Decoding and Improved Proximity Gaps

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Locality of Curve-Decoding and Improved Proximity Gaps Rohan Goyal∗

Venkatesan Guruswami †

Yihang Sun‡

Mary Wootters§

Abstract

arXiv:2607.08516v1 [cs.IT] 9 Jul 2026

Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Informally, we say that a code C ⊂ Σn exhibits a proximity gap (with respect to degree-ℓ curves) if for any degree-ℓ curve u(x) ∈ Σn , either every point on u(x) is close to C, or else most of them are far from C. Recent work [GG25] has established near-optimal proximity gaps for many families of codes, including subspace design codes, as well as random ensembles like random linear codes, ReedSolomon codes with random evaluation points, and Gallager’s ensemble of LDPC codes. However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree ℓ increases. In this work, we obtain improved proximity gaps for random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager’s ensemble. Quantitatively, our results for these random ensembles match the results that [GG25] attained for subspace design codes. In fact, our techniques are a black-box transference from subspace design codes: Any progress on subspace design codes will automatically lead to analogous progress for these random ensembles. To obtain our results, we extend the Local Coordinate-wise Linear (LCL) property framework developed in [LMS25, BCDZ25] to a row-span constrained version. This allows us to cast curvedecodability—a property that implies proximity gaps—directly as an (row-span constrained) LCL property, and make use of that machinery. In contrast, because curve-decodability is not obviously a (vanilla) LCL property, prior work had worked with a proxy property instead, leading to the aforementioned parameter losses. In addition, we extend the framework to also show an equivalence theorem for Gallager’s ensemble of random LDPC codes and random linear codes for our row-span constrained LCL properties.

∗

Massachusetts Institute of Technology. [email protected] University of California, Berkeley. [email protected] ‡ Stanford University. [email protected] § Stanford University. [email protected] †

Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Techniques: Curve-Decoding as a Row-Span Constrained LCL Property . . . . . . . 1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Discussion and Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 5 7 8

2 Preliminaries 2.1 Proximity Gaps and (Mutual) Correlated Agreement . . . . . . . . . . . . . . . . . . 2.2 Subspace-Design Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Notations and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 10 12 13

3 Row-span Constrained Local Properties 13 3.1 Generalizing Local Profiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Behavior Under Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Thresholds for Random Ensembles of Codes . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.1 Random Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 Random Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.3 Random LDPCs (Gallager’s Ensemble) . . . . . . . . . . . . . . . . . . . . . . 21 3.4 Threshold for Subspace Design Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Curve-Decoding as a Row-Span Constrained LCL Property

5 Improved Proximity Gaps 28 5.1 Random Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Random Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3 Random LDPC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 A Appendix: Gallager’s Ensemble

Introduction

Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs), both of which are relevant for blockchains and related technologies. Let F be a finite field, and let Σ be a vector space over F. An F-additive code C (with alphabet Σ and block length n) is an F-linear subspace C ⊂ Σn . Informally, we say that C exhibits a proximity gap (for degree-ℓ P curves, which is the focus of this paper) if the following holds. For any degree-ℓ curve u(x) = ℓi=0 ui xi in Σn given by u0 , . . . , uℓ ∈ Σn and x ∈ F, either every point u(α) on the curve is close to C, or else a 1 − ε fraction of the points on the curve are far from C. Formally, we have the following definition. P Below, ∆(x, y) := n1 ni=1 1[xi ̸= yi ] is the (relative) Hamming distance between x, y ∈ Σn , and ∆(x, C) := miny∈C ∆(x, y) for code C. Definition 1.1 (Proximity Gaps (PG)). An F-additive code C ⊂ Σn is said to have (ℓ, δ, ε, γ) proximity gap if for all u0 , u1 , · · · , uℓ ∈ Σn , and for all δ ′ ≤ δ,       ℓ ℓ X X δ′ Pα∈F ∆ . uj αj , C  ≤ δ ′  > ε =⇒ ∀α ∈ F, ∆ uj αj , C  ≤ 1−γ j=0

j=0

When γ = 0, we say that C has an (ℓ, δ, ε) proximity gap. Proximity gaps, especially for Reed-Solomon (RS) Codes,1 have been a hot topic lately, with the Ethereum Foundation offering $1M in prizes for resolving (or disproving) conjectures related to proximity gaps for RS codes [Eth26]. See [ABF26] for a recent survey on proximity gaps and problems relevant to the proximity prize. √ log |C| is the Until recently, the best proximity gap guarantees required δ < 1− R, where R = |Σ| n rate of the code C ⊂ Σn . In recent work [GG25], Guruswami and Goyal established near-optimal proximity gaps—with δ approaching 1 − R—for several families of codes. For Folded Reed-Solomon Codes, Multiplicity Codes,2 and more generally any Subspace Design Code (Definition 2.12), they established (ℓ, δ, ε) proximity gaps with δ = 1 − R − 2η for any η > 0, provided that 2 nℓ ℓ εq ≥ +O 3 , (1.1) η η where q is the size of the base field. Thus, the left-hand side εq is a bound on the number of points on the curve u(x) that can still be close to C, in the case that not all q points are. We’d like for this bound to be as small as possible. Via a framework from [BCDZ25, LMS25] that establishes a connection between random linear codes and subspace design codes, the work [GG25] extended their results for subspace design codes to several random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager’s ensemble of random LDPC codes. However, some parameters 1

Reed-Solomon codes are a classical family of codes based on low-degree polynomials. Given fixed distinct evaluation points α1 , . . . , αn ∈ Fq =: Σ, the corresponding Reed-Solomon code C ⊂ Σn of length n and dimension k ≤ n is given by C = {(f (α1 ), . . . , f (αn )) : f ∈ Fq [x], deg(f ) < k}. 2 Informally, a folded Reed-Solomon code is obtained by “folding” (aka, bundling symbols together) an RS code ′ m n/m C ∈ Fn . A (univariate) multiplicity code is similar to an RS code, except each symbol q to obtain a code C ∈ (Fq ) contains not just f (αi ), but also f (j) (αi ) for j = 1, 2, . . . , m − 1, where f (j) denotes the j’th (Hasse) derivative. In either case, the alphabet size increases from q to q m . By a result of [GK16], both are special cases of Subspace Design Codes, defined in Definition 2.12.

degraded in this extension: The final result that [GG25] established for these random ensembles was (ℓ, δ, ε) proximity gaps with δ = 1 − R − 2η, provided that nℓ(1 − R) εq ≥ + η

ℓ η2

O(ℓ) .

(1.2)

When ℓ is large, on the order of Ω(log n), the error term (ℓ/η 2 )O(ℓ) in (1.2) swamps the main term, and the requirement on εq quickly becomes large. This leaves us with the question of whether a bound like (1.1) is achievable for these random ensembles of codes. This question has practical as well as theoretical motivations: Larger values of ℓ can occur in practice, for example in WHIR [ACFY25]; random ensembles of codes are also practically interesting, for example in Blaze [BCF+ 25] or Bolt [GNR26];3 and understanding RS codes with random evaluation points may deepen our understanding of explicit RS codes, relevant to the proximity prize [Eth26].

1.1

Our Contributions

Our main contribution is to improve the bound (1.2) for random ensembles of codes to match the bound (1.1) that was already established for subspace design codes. We establish these improved bounds for random linear codes, RS codes with random evaluation points, and Gallager’s ensemble of LDPC codes. See Definitions 2.2 to 2.4 for formal definitions of these code families. Theorem 1.2 (Informal; see Theorems 5.3, 5.6 and 5.10). Fix any ℓ ∈ N and η > 0. Let C ∈ Fnq be a random linear code, random Reed-Solomon code, or random LDPC code4 of rate R ∈ (0, 1). Then, with probability at least 2/3 over the choice of C, C has (ℓ, 1 − R − 2η, ε) proximity gaps (with respect to degree-ℓ curves), provided that 2 nℓ(1 − R) ℓ εq ≥ +O 3 . (1.3) η η In fact, our results establish not just proximity gaps, but also stronger notions known as Correlated Agreement (CA, Definition 2.5) and Mutual Correlated Agreement (MCA, Definition 2.6); see Theorems 5.3, 5.6 and 5.10 for the full statements. Our framework, discussed more below in Section 1.2, is a black-box transference method from subspace design codes. Thus, any future improvements for subspace design codes will immediately lead to an analogous improvement in Theorem 1.2. In order to establish our results, we generalize the Local Coordinate-wise Linear (LCL) framework of [LMS25] to a new “row-constrained” version of the framework, described below. We hope that this generalization may find other applications going forward. Remark 1.3. [LMS25] showed an equivalence for LCL properties between random linear and random Reed-Solomon codes, which we generalize to the row-constrained setting. To extend our results to random LDPC codes, we prove an analogous equivalence theorem of our generalized LCL properties for Gallager’s ensemble of random LDPC codes and random linear codes based on [MRRZ+ 21]. See Section 3.3.3 and Section A for more details. 3 In more detail, Blaze considers a random ensemble of RAA codes, which use random permutations to decide the parity checks. Bolt uses Gallager’s ensemble of LDPC codes, which we also study in this paper. 4 Technically, the result for random LDPC codes requires the leading term nℓ(1 − R)/η to be slightly larger; it is stated in Theorem 5.10 as 2nℓ(1 − R)/η; the factor of two can be improved to any constant larger than one (see Remark 5.8).

c(x)

⇒

u(α)

f (α) ∈ C

f (α) = c(α)

u(x)

Figure 1: Depiction of curve decodability (Definition 2.7). The orange stars represent f (α) ∈ C for α ∈ A, and the blue dots represent u(α) ∈ Σn for α ∈ Fq , where u(x) is a degree-ℓ curve. Informally, a code C ⊆ Σn is (ℓ, δ, a, b)-curve-decodable if the following holds: If there are at least a orange stars δ-close to distinct blue dots, then at least b of those orange stars lie on a degree-ℓ curve c(x). In the picture, a = 5, and b = 4.

1.2

Techniques: Curve-Decoding as a Row-Span Constrained LCL Property

Following [GG25], we study curve-decoding. For the rest of this discussion, assume for simplicity that the alphabet Σ is equal to Fq , so C is a linear subspace of Fnq . P Informally, such a code C is (ℓ, δ, a, b) curve-decodable if, for any degree-ℓ curve u(x) = ℓi=0 ui xi with ui ∈ Σn , the following holds. Suppose that there is a set A ⊂ Fq of size a so that u(α) is δ-close to P some codeword f (α) ∈ C for all α ∈ A. Then, there should be a “codeword curve” c(x) = ℓi=0 ci xi , where ci ∈ C ⊂ Σn , so that f (α) = c(α) for at least b values of α ∈ A. See Definition 2.7 for a formal definition; the property is illustrated in Figure 1. The work [GG25] showed that curve-decodability is a sufficient condition to establish proximity gaps (as well as stronger notions like correlated agreement and mutual correlated agreement); see Theorem 2.9 and Theorem 2.10. They then established that subspace design codes have curvedecodability (Theorem 2.15), which led to their results about subspace design codes. Our work comes in the next step. To obtain their results for random ensembles of codes, [GG25] applied a framework of [BCDZ25, LMS25]. This framework roughly shows that any Local Coordinate-wise Linear (LCL) property that is satisfied by subspace design codes is also satisfied by these random ensembles. We will explain what LCL properties are in a moment, but the main challenge with this approach is that “being curve-decodable” is in fact not (or, not obviously) an W LCL property. To get around this, [GG25] defined another property, which they called -decoding, which is captured byWthe LCL framework. Then existing results imply that the random ensembles of codes are just as -decodable as subspace design codes, W and translating back to curve-decoding gives the final result. Unfortunately, going through -decoding results in a loss in parameters, degrading (1.1) to (1.2). We avoid this loss by extending the LCL framework to apply directly to curve-decoding. The LCL Framework. Before explaining our extension, we first explain the LCL framework of [LMS25]. Intuitively, an r-local LCL property is one defined by the exclusion of r-sized bad sets of codewords. For example, the property of “having good distance” might be defined by the exclusion of all pairs (r = 2) of codewords that agree in too many places. The LCL framework allows for any definition of “bad” that can be captured by a family F of coordinate-wise linear relationships. In more detail, let C ⊂ Fnq be a linear code, and consider a set of r distinct “bad” codewords, stacked together to form the columns of a matrix M ∈ Fn×r . Let F be a family of profiles V = q (V1 , . . . , Vn ), where each Vi ∈ L(Frq ). (Here, L(W ) denotes the collection of subspaces of W .) In the LCL framework, the “badness” of a matrix M is captured by the following criterion: There is 5

some V = (V1 , . . . , Vn ) ∈ F so that for all i ∈ [n], the i’th row of M is contained in Vi . Thus, an LCL property defined by F is the property of avoiding all “bad” matrices M that satisfy the constraints given by some V ∈ F (we say that C avoids M if the column span of M is not contained in C). See Definition 3.2 for a formal definition. Capturing Curve-Decoding and the Approach of [GG25]. The LCL framework captures many familiar properties, for example distance, list-decoding, and list-recovery. Unfortunately, it does not seem to capture curve-decoding. To see why, let us consider two approaches. For the first—and probably most natural—approach, suppose that we have a bad example for (ℓ, δ, a, b) curve-decoding. That is, suppose we have a set A ⊂ Fq of size a, a degree-ℓ curve u(x) ∈ Fnq , and a function f : Fq → C so that ∆(u(α), f (α)) ≤ δ for all α ∈ A; but suppose that P there is no degree-ℓ “codeword curve” c(x) = ℓi=0 ci xi for ci ∈ C that passes through at least b of the f (α). We will attempt to construct a “witness” matrix M ∈ Fn×A whose columns are f (α) for all q α ∈ A. In order to certify this as a bad example, we should be able to come up with some LCL profile V = (V1 , . . . , Vn ) that “explains” the badness of the example. There are two properties that make a “bad example” bad: (A) Each of the f (α) (the columns of M ) agree in many coordinates with some ambient curve u(x) of degree ℓ. (B) No b columns of M themselves lie on the same degree-ℓ curve. Item (A) can be captured with an a-local profile V = (V1 , . . . , Vn ). Indeed, let Ai = {α ∈ A : u(α)i = f (α)i }, and then define Vi to be the subspace of all y ∈ FA q so that y (when viewed as a function y : A → Fq ) agrees with some degree-ℓ polynomial on Ai . Then consider the class F of all profiles V generated this way (over all appropriate choices of Ai ). Item (A) holds if and only if C contains some V ∈ F. However, it is not clear how to capture item (B) with the LCL framework, as (B) is a more global property of the matrix, not easily captured with coordinate-wise constraints. Thus, another approach seems needed. As a second possible approach, we describe what [GG25] did, and briefly explain why it incurs an exponential loss in the parameter ℓ. The idea is to consider first the special case that b = ℓ + 2. Given a bad example for curve-decoding, consider a much larger “witness” matrix M ∈ Fn×r for q a A r = ℓ+1 , as follows. The columns of M now correspond to subsets S ∈ ℓ+1 , and the columns correspond to polynomials gS (x) defined by interpolating through the points (α, f (α)) for all α ∈ S. It turns out that if b = ℓ + 2, then all of these polynomials must be distinct: Otherwise, if gS = gS ′ for some S ̸= S ′ , then this gives a degree-ℓ curve passing through at least |S ∪ S ′ | ≥ ℓ + 2 = b of the codewords f (α), of this example. Then, if Fq is large enough, there n contradicting the badness o A is some β so that gS (β) ∈ C : S ∈ ℓ+1 are also all distinct, and these can be the columns of M . However, this requires us to take ℓ = b + 2; otherwise, we can’t be guaranteed that the columns are distinct, which is required by the LCL framework. The insight of [GG25] W was to essentially transform the general-ℓ case to the ℓ = b + 2 case via a new property called -decoding; but this came at a cost of an exponential dependence on ℓ. (We emphasize that the exponential loss comes from the transformation to the b = ℓ + 2 case, not the larger size of the witness matrix, although we will be able to overcome both issues in this work.) Our Approach: Row-span Constrained LCL Properties. Instead of trying to manipulate curve-decodability to fit into an LCL property, we extend the definition of an LCL property. That 6

is, we return to the first, more straightforward, attempt above. Recall that the first property (A)— that each column of M is close to some degree-ℓ curve u(x) –is easily captured by an a-local LCL profile. The harder part is dealing with item (B), that no b columns of M should themselves lie on a degree-ℓ curve. This is a global constraint on the matrix M , and thus is not immediately amenable to the coordinate-wise framework of [LMS25]. In order to capture item (B), we introduce a row-span constraint. One example of such a constraint was already present in prior works [BCDZ25, LMS25]. Indeed, that framework requires that the columns of the witness matrix M be distinct, which turns out to be equivalent to the property that the row-span U of M does not have any identically equal coordinates (that is, there should not be any i ̸= j so that uj = ui for all u ∈ U ). Thus, [BCDZ25, LMS25] restricted the row-span of their witness matrices M to the set Ldist (Frq ) of distinct subspaces U , those without any identically equal coordinates. Our observation is that item (B) can also be captured in this way. In Lemma 4.2 and Corol lary 4.3, we show that item (B) is equivalent to the following: For any B ∈ Ab , there is some u in the row-span U of M so that u|B does not agree with any degree-ℓ curve p : B → Fq . We define a subspace U with this property to be (ℓ, A, b) curve-free (Definition 4.1). Thus, in addition to an alocal LCL profile V to enforce the condition (A), we also have a condition on the row-span—namely that the row-span U of M should be (ℓ, A, b) curve free—to enforce condition (B). Formally, we implement this by defining the set F to be a set of pairs (V, U ), where V is an r-local profile, and U ⊂ Frq is a subspace. Then a witness matrix M with columns in C is “bad” if there is some (V, U ) ∈ F so that the i-th row of M is contained in Vi for all i; and additionally the row-span of M is contained in U . We say that C avoids F if there is no such witness matrix. Putting it Together. In order to implement the ideas above, we first re-derive the LCL framework and the connections in [BCDZ25, LMS25] in the row-span constrained setting. We do this in Section 3. In Theorem 3.16 and Corollary 3.19, we extend the threshold theorem of [LMS25] to the row-span constrained setting, defining a “threshold rate” RF below which random linear codes are likely to satisfy properties defined by F ⊂ L(Frq )n × L(Frq ) (with the additional row-span constraint) and above which they are not. In Theorem 3.27 and Corollary 3.30, we extend the transfer theorem from [BCDZ25] to the row-span constrained setting, showing that good subspace design codes have essentially the same “threshold rate” as random linear codes. Next, in Section 4, we show that not being (ℓ, δ, a, b) curve-decoding is a row-span constrained a-local LCL property, as described above. The local profile records the agreement of the nearby codewords with an ambient degree-ℓ curve (property (A)), while the row-span constraint records the absence of a degree-ℓ codeword curve through any b nearby codewords (property (B)). This is stated formally in Theorem 4.4 and Corollary 4.5. Finally, we apply our row-span constrained LCL theory to curve-decoding and to three random ensembles of codes—random linear codes, RS codes with random evaluation points, and Gallager’s ensemble of LDPC codes—to prove Theorem 1.2. To recap, we know from [GG25] that subspace design codes satisfy curve-decodability; we have shown in Section 3 that random ensembles of codes behave similarly to subspace design codes for any row-span constrained LCL property; and we have shown in Section 4 that curve-decodability is such a property. Therefore random ensembles of codes exhibit good curve-decodability as well. We put everything together and work out the parameters in Section 5; our main theorem statements are given as Theorem 5.3, Theorem 5.6, and Theorem 5.10.

1.3

Related Works

Proximity Gaps. Proximity gaps (and related notions, including correlated agreement and mutual correlated agreement) arise naturally in the study of interactive protocols. The goal in these 7

settings is to test whether or not every vector in a set—say, a line or a curve—is close to a code C. If that code exhibits a proximity gap, then it suffices to choose a random vector in that set and use its distance from the code as a proxy for the minimum distance to C over the whole set. This connection was observed in [RVW13], and since then a long line of work has been devoted to improving the parameters [AHIV17,BSKS18,BSGKS20,BSCI+ 23,ACFY25,GG25] and establishing limitations [DG25, CS25, BSCH+ 25, KKH26]. See the recent survey [ABF26] for an overview of the work on proximity gaps and √ related notions. Prior to the work of [GG25], the best known proximity gap results required δ < 1 − R, corresponding to the Johnson radius in list-decoding. As discussed above, the work [GG25] improved this to allow δ to approach 1 − R, the best trade-off possible. However, as noted earlier, the results can still be improved, notably in how small the parameter ε can be. The current best results for explicit codes—including folded RS codes, multiplicity codes, and all subspace design codes—follow from [GG25] and work under the condition given by (1.1). In this work we improve their results for random ensembles of codes from (1.2) to (1.1). Local properties and subspace design codes. A recent line of work [MRRZ+ 21, GLM+ 21, GMR+ 21, LMS25] has shown that a wide variety of random ensembles of codes—including random linear codes, random LDPC codes, and Reed-Solomon codes with random evaluation points—all behave similarly with respect to “local” properties: properties that are characterized by the exclusion of small bad sets. The paper [LMS25] introduced the LCL framework discussed above, and [BCDZ25] connected this to another line of work on subspace design codes. The study of subspace design codes implicitly began with the introduction of Folded Reed-Solomon codes [GR08]. Over nearly two decades, it was observed that a key property of these codes, as well as of univariate multiplicity codes, is that they satisfy a subspace design property [GK16], which has been leveraged and generalized in subsequent works [KRZSW18,Tam24,Sri25,AHS26,CZ25,BCDZ25,GGH26]. Notably, [CZ25] showed that any such subspace design codes enjoy optimal list-decodability. The work [BCDZ25] then connected this line of work to the LCL framework discussed above, showing that in fact the same thresholds are achieved by subspace design codes. The work [GG25] leveraged this connection to study curve-decoding, and we do the same in this work.

1.4

Discussion and Open Problems

We conclude this section with a few open questions. • Our approach can automatically turn any improvements for subspace design codes into analogous improvements for random ensembles of codes. Thus, the natural open question is to further improve the trade-offs between ε, q, ℓ and η for subspace design codes. • Our results imply that Reed-Solomon codes with random evaluation points attain near-optimal proximity gaps, even for large ℓ. While it is known that there exist Reed-Solomon codes that do not achieve optimal proximity gaps [BSCH+ 25,DG25,CS25,KKH26], it is not known which choices of evaluation points are “good.” Can we identify explicit Reed-Solomon codes with near-optimal proximity gaps? This question is related to the open problem of identifying explicit Reed-Solomon codes that achieve near-optimal list-decoding. • We hope that our techniques will be useful beyond the present application. Are there other natural properties that can be captured with the row-span constrained LCL framework, but not with the original LCL framework?

Acknowledgements R.G. is supported by (Yael Tauman Kalai’s) grant from Defense Advanced Research Projects Agency (DARPA) under Contract No. HR0011-25-C-0300. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA). V.G. is supported by a Simons Investigator award, NSF grant CCF-2211972, and ONR grant N00014-24-1-2491. Y.S. is funded by the NSF Graduate Research Fellowship and the Stanford Graduate Fellowship. M.W. is partially funded by NSF grants CCF-2231157 and CNS-2321489.

Preliminaries

We begin by introducing the basic coding-theoretic definitions we will be using. For any two vectors x, y in Σn where Σ is some alphabet, we define the fractional Hamming distance ∆(x, y) = n1 |{i ∈ [n] : xi ̸= yi }| to be the fraction of coordinates where they differ. For a set S ⊂ Σn , we define ∆(x, S) = miny∈S ∆(x, y) to be the fractional distance of x to its closest vector in S. Throughout this paper, all distances are taken to be fractional unless stated otherwise. The two fundamental quantities associated with a code are its rate and distance. For a code C ⊂ Σn , we define its (relative) distance as δ(C) = minx,y∈C,x̸=y ∆(x, y). Moreover, its rate R(C) is defined as R(C) = n1 log|Σ| |C|. In this paper, we will focus on additive codes over a finite field, defined as follows: Definition 2.1 (Additive codes). Let F be a finite field and let Σ = Fs for some positive integer s. A code C ⊂ Σn is said to be F-additive (or just additive when the field F is clear from context) if C is an F-linear subspace of Σn . We focus on three families of random codes, defined below. The first is a random linear code. Definition 2.2 (Random Linear Code (RLC) and Random Fq -Additive Code). A random linear code C ⊂ Fnq of rate R is given by taking C = {(Enc1 (x), · · · , Encn (x)) | x ∈ FRn q } where Enci : 5 More generally, a random F -additive → F are independent uniformly random linear maps. FRn q q q } where code C ⊂ (Fsq )n of rate R is given by taking C = {(Enc1 (x), . . . , Encn (x)) | x ∈ FRsn q Rsn s Enci : Fq → Fq are independent uniformly random linear maps. The next family is a random Reed-Solomon code, which is just a Reed-Solomon code where the evaluation points are chosen uniformly at random. Definition 2.3 (Random Reed-Solomon Code (RRS)). A Reed-Solomon code over a field Fq with evaluation points α1 , · · · , αn is defined as follows RSFq (α1 , . . . , αn , k) = {(f (α1 ), . . . , f (αn )) | f ∈ Fq [X], deg f < k} A random Reed-Solomon code of rate R is one in which k = Rn and αi are independent uniformly random elements of Fq . 5

Note that, defined this way, there is some small chance that the rate logq |C|/n of a random linear code may not actually be R, if there are too many linear dependencies between the maps Enci . However, it is more convenient to work with i.i.d. encoding maps, and the probability of the rate not being R is negligible, so anything that holds with high probability for this model also holds with high probability for other models of random linear codes, for example the model where one chooses C to be a uniformly random subspace of dimension Rn, or the model where C is the (1−R)n×n kernel of a random matrix in Fq . See, e.g., [LMS25, Appendix A].

Finally, we introduce our last family of codes, random Low-Density Parity-Check (LDPC) codes. In this paper, by “random LDPC codes” we mean Gallager’s ensemble of random LDPC codes [Gal63]. In general, a rate R, s-sparse LDPC code can be described as follows: Pick a bipartite graph G = (L ⊔ R, E) with |L| = n, |R| = (1 − R)n and right degree s. Each edge e ∈ E has a weight we ∈ Fq , the code C is given as follows: o n X w c = 0 for all v ∈ R . C = c ∈ FL : (u,v) u q u∈N (v)

Above, N (v) denotes the neighborhood of v in G. To define a random LDPC code, we thus just need to describe the underlying bipartite graph and the edge weights we . Gallager’s ensemble [Gal63] defines an ensemble of random graphs (and hence random LDPC codes) as follows.6 Definition 2.4 (Random Low Density Parity Check Code (RLDPC)). Let t = (1 − R)s, and let Gi = (V, Wi , Ei ) for i = 1, · · · , t be uniformly random (1, s) regular bipartite graphs with a shared F left vertex set and disjoint right vertex sets W of size n/s. The graph G is then defined as i i Gi ; F F that is, G = (V, W, E), where W = i Wi and E = i Ei . The edge weights we are sampled as independent uniformly random elements of F∗q . A Random LDPC Code C of rate R is then the LDPC code derived from G and the weights {we }, as described above.

2.1

Proximity Gaps and (Mutual) Correlated Agreement

Proximity Gaps are related to two stronger notions, Correlated Agreement (CA) and Mutual Correlated Agreement (MCA). Our results actually establish both CA and MCA as well as proximity gaps. Informally, we say that a code C has (ℓ, δ, ε, γ)-correlated agreement if, for all degree-ℓ curves Pℓ u(x) = i=0 ui xi with ui ∈ Σn , the following holds: Either at most an ε fraction of the points on P u(x) are δ-close to C; or there is some “codeword curve” c(x) = ℓi=0 ci xi with ci ∈ C so that u(x) agrees identically with c(x) on a set S ⊂ [n] of at least δn/(1 − γ) coordinates. Formally, we have the following definition. Definition 2.5 (Correlated Agreement (CA)). An F-additive code C ⊂ Σn is said to have (ℓ, δ, ε, γ) correlated agreement if for all u0 , u1 , · · · , uℓ ∈ Σn and δ ′ ≤ δ ℓ ℓ n _ h X i o δ′n Pα∈F ∆ uj αj , C ≤ δ ′ > ε =⇒ ∃c0 , c1 , · · · cℓ ∈ C : i : cj,i ̸= uj,i ≤ . 1−γ j=0

j=0

P Pℓ ℓ j, j In particular, CA implies that for all α ∈ F, we have that ∆ u α c α ≤ j j j=0 j=0 δ ′ /(1 − γ). Thus, (ℓ, δ, ε, γ) correlated agreement implies an (ℓ, δ, ε, γ)proximity gap. Next, we define Mutual Correlated Agreement (MCA). Informally, we say that an F-additive code C has (ℓ, δ, ε) MCA if for all degree-ℓ curves u(x) in Σn , the following holds. For all sets S ⊂ [n] of size at least (1 − δ)n, and for at least an 1 − ε fraction of α P ∈ F, if there is some c ∈ C that agrees with u(α) on S, then there is some “codeword curve” c(x) = ℓi=0 ci xi for ci ∈ C so that c(x) and u(x) agree identically on S. Formally, we have the following definition, which captures the contrapositive of the intuition above. 6

Technically, this way of generalizing to larger alphabets is slightly different than [Gal63]. Our definition coincides with [Gal63] for q = 2; for larger q, [Gal63] chooses weights we to all be 1, while we choose them uniformly in F∗q ; this matches the ensemble studied in [MRRZ+ 21].

Definition 2.6 (Mutual Correlated Agreement (MCA)). An F-additive code C ⊂ Σn is said to have (ℓ, δ, ε) mutual correlated agreement if for all u0 , u1 , · · · , uℓ ∈ Σn and δ ′ ≤ δ   ℓ X Pα∈F ∃S ⊂ [n], c ∈ C, j ∈ {0, 1, . . . , ℓ} : |S| ≥ (1 − δ ′ )n, c|S = αj uj|S , c′|S ̸= uj|S ∀c′ ∈ C  ≤ ε. j=0

We note that (ℓ, δ, ε) MCA implies (ℓ, δ, ε, γ = 0) CA and hence (ℓ, δ, ε, γ = 0) PG. Indeed, suppose that C satisfies MCA, and suppose there is some codeword c ∈ C that is δ ′ -close to u(x) on at least εq points, call them A ⊂ F. MCA implies that there is a set B ⊂ F of size at least (1 − ε)q so that the event inside the Pα [·] statement holds. Then there must be at least one point α ∈ A ∩ B. Letting S ⊂ [n] be the set of coordinates (of size at least (1 − δ ′ )n) on which u(α) agrees with c, we conclude from the definition of MCA that there is some “codeword curve” c(x) so that c(x) and u(x) identically agree on S, establishing CA. Finally, we formally define curve-decodability, which we informally defined in Section 1 (see Figure 1). The following definition was given in [GG25], and the case of ℓ = 1 was independently defined in [Hab24] as collinearity of proximates. We adopt the convention from [GG25]. Definition 2.7 (Curve-Decodability). An additive code C ⊂ Σn is (ℓ, δ, a, b) curve-decodable if for every u0 , u1 , · · · , uℓ ∈ Σn , all functions f : Fq → C, whenever the set ℓ n o X j A= α∈F:∆ uj α , f (α) ≤ δ j=0

has at least a elements, there exist c0 , c1 , · · · , cℓ ∈ C such that ℓ o n X α ∈ A : f (α) = cj αj ≥ b . j=0

[GG25] showed a transformation to boost results about the curve-decodability of a code assuming that the underlying code is also list-decodable. Theorem 2.8 ([GG25, Theorem 3.6]). Suppose an Fq -additive code C ⊂ (Fsq )n is δ 1+

ℓ , L list-decodable b−ℓ

and

(ℓ, δ, a, b) curve-decodable.

(2.1)

Then C is also (ℓ, δ, (T − 1)L + a, T ) curve-decodable for any T . The key motivation to define curve-decodability is due to the following implication for correlated and mutual correlated agreement. Theorem 2.9 (Correlated agreement from curve-decodability, [GG25, Theorem 3.4]). Let C ⊂ Σn be an Fq -additive code. Let ℓ, t > ℓ, a ∈ N and δ ∈ (0, 1). Suppose that C is (ℓ, δ, a, t) curve-decodable. Then C has (ℓ, δ, a/q, ℓ/t) correlated agreement. Theorem 2.10 (Mutual correlated agreement from curve-decodability, [GG25, Theorem 3.5]). Let C ⊂ Σn be an Fq -additive code. Let ℓ, a ∈ N and δ ∈ (0, 1). Suppose that C is (ℓ, δ, a, ℓn + 1) curve-decodable. Then C has (ℓ, δ, a/q) mutual correlated agreement.

Corollary 2.11. If an Fq -additive code C ⊂ (Fsq )n is ℓ , L list-decodable and δ 1+ b−ℓ

(ℓ, δ, a, b) curve-decodable

(2.2)

then C has: 1. for any t ≥ 1, (ℓ, δ, (t − 1)L + a, t) curve-decodability, 1 2. for any m > 1, ℓ, δ, ℓmL+a , q m correlated agreement and proximity gap, 3. (ℓ, δ, ℓnL+a ) mutual correlated agreement. q Proof. The first statement is simply Theorem 2.8. For the second, we set T = ℓm and apply Theorem 2.9. For the third, we set T = ℓn + 1 and apply Theorem 2.10. Enabled by the above reductions, to prove an additive code C has correlated agreement, it suffices to prove list-decodability and curve-decodability of the code. In this work, and related works, we always work in the regimes where the codes in consideration are already known to be list-decodable with good parameters. Thus, the key innovation lies in establishing curve-decodability.

2.2

Subspace-Design Codes

We introduce notation and results from [GG25] that we will use. Definition 2.12 (Subspace-Design Code). For any function τ : N → R≤1 , an Fq -additive code C ⊂ (Fsq )n is said to be a τ -subspace design code if for every r ∈ N, and every Fq -linear subspace A of C of dimension at most r, the following holds: n

1X dim Ai ≤ dim(A) · τ (r) n i=1

where Ai = {a ∈ A | ai = 0}. n Definition 2.13. For an additive code C ⊂ Fsq and dimension r, let dim Vi σ(r) := max Ei∈[n] : V ⊂ C, dim V = r dim V

(2.3)

where Vi = {x ∈ V : xi = 0}. In the message space with encoding maps Enci : Fkq → Fsq , we have dim(A ∩ ker(Enci )) : A ⊂ Fkq , dim A = r (2.4) σ(r) := max Ei∈[n] dim A Following the notation of [GG25], we can define the monotone envelope τ (r) := max{σ(1), . . . , σ(r)}. Observe that with this choice, C is by definition a τ -subspace design code. Remark 2.14 (Comparison to [BCDZ25]). The paper [BCDZ25] uses slightly different language; they say that C is r-subspace designable if, for every d ∈ [r] σ(d) ≤ R +

1 . nd

(2.5)

We recall that σ(r) ≥ R − r/sn always. Thus, having the subspace design property with “good” parameters means that we should have τ (d) ≤ R + η for some “small” η > 0. [BCDZ25] proved that random Fq -additive codes C ⊂ (Fsq )n are r-subspace designable whenever s = Ω(rn). 12

Finally, we state a theorem from [GG25] which shows that any subspace-design code is curvedecodable. Theorem 2.15 ([GG25, Theorem 4.7]). Fix any integers a, ℓ and η > 0, and let d = ⌈(ℓ + 1)/η⌉. Then for any τ -subspace design code C ⊂ (Fsq )n , C is ηa ℓ, 1 − τ (d) − η, a, curve-decodable. (2.6) d+η

2.3

Notations and Conventions

n n We let [n] := {1, . . . , n} with the convention [0] = ∅. Let ≤k and ≥k denote the sum of binomial n S coefficients i for i ≤ k and i ≥ k, respectively. Let k denote the set of k-element subsets of S. S S and ≥k denote the set of subsets of S with size at most k, and at least k, respectively. For a ≤k finite set S, let Es∈S denote the expectation over a uniform random element s of S. For a matrix A ∈ Fm×n , let Ai⋆ ∈ Fn be the i-th row of A and let A⋆j ∈ Fm be the j-th column of A. Given a vector space V , let L(V ) be the set of (linear) subspaces of V . We also adopt standard notation from asymptotic analysis: as x → ∞, we write f (x) = o(g(x)) if f (x)/g(x) → 0; f (x) = O(g(x)) or g(x) = Ω(f (x)) if there exists a finite, positive constant C such that f (x) ≤ Cg(x) for all sufficiently large x. We use hq : [0, 1] → [0, 1] and h−1 q to denote the q-ary entropy function and its inverse, i.e. 1 1 hq (x) := x logq (q − 1) + x logq + (1 − x) logq . x 1−x

Row-span Constrained Local Properties

3.1

Generalizing Local Profiles

We begin by introducing some notation from [LMS25, BCDZ25], and explaining how we generalize it to our row-span constrained versions. As described in Section 1.2, a local profile gives a set of coordinate-wise linear constraints that a “bad” witness matrix M might satisfy. Definition 3.1 (r-Local Profile, [LMS25]). Let Fq be a finite field of q elements and let n and r be positive integers. A tuple V = (V1 , · · · , Vn ) ∈ L(Frq )n is called a r-local profile. Next, we define what it means for a code to contain a local profile (with a particular row-span). Definition 3.2 (Containing a local profile, [LMS25]). A code C ⊂ Fnq is said to contain a local profile V with span U ∈ L(Frq ) (often written “C contains (V, U )”) if there exists an M ∈ Fn×r q such that: • each column of M is contained in C; • the i-th row of M is contained in Vi ; and • the row-span of M is U . We call such an M a witness matrix, and columns of M witness columns. In [LMS25], an LCL property is given by a collection F of r-local profiles V. Our key generalization is to also record the corresponding row-spans in the family. That is, F is no longer a collection of profiles V; now it is a collection of pairs (V, U ), where U constrains the row-span of a witness matrix. 13

Definition 3.3 (Row-span Constrained LCL Property). A row-span constrained r-local LCL family F is a collection of r-local pairs (V, U ) where V = (V1 , . . . , Vn ) ∈ L(Frq )n is an r-local profile and U ∈ L(Frq ) is the row-span constraint of the witness matrix. A code C contains F if it contains some pair (V, U ) ∈ F. It avoids F otherwise. We say that the row-span constrained r-local property given by F is the property of avoiding F.7 Remark 3.4. Definition 3.3 generalizes the definition of an LCL property in [LMS25], in the sense that they restrict the columns of their witness matrices M to be distinct; as they observe, this is the same as restricting the row-span of the witness matrices to lie in Ldist (Frq ), where Ldist (Frq ) denotes all subspaces U of Frq so that no two distinct coordinates i, j ∈ [r] are identically equal on U . Next, we define what it means for an Fq -additive code with alphabet Σ = Fsq to contain (V, U ). Definition 3.5 (Folded containment). Let C ⊂ (Fsq )n be an Fq -additive code. For an r-local profile V = (V1 , . . . , Vn ) ∈ (L(Fq ))n , define the duplicated profile V⊗s ∈ (L(Fq ))sn by ⊗s V(i,j) = Vi

(3.1)

for any i ∈ [n] and j ∈ [s]. We say that C contains (V, U ) if the “unfolded” version C ⊂ Fsn q contains (V⊗s , U ). Here, by the “unfolded code,” we mean to embed (Fsq )n in Fsn in the natural way. q For a family F of pairs, define F ⊗s = {(V⊗s , U ) : (V, U ) ∈ F }. Thus Fq -additive code C ⊂ (Fsq )n contains F if and only if the “unfolded” version C ⊂ Fsn q contains F ⊗s . Remark 3.6. Note that F ⊗s does not encode the same property as F applied to unfolded codes. For example, proximity is not preserved: being far as an Fq -additive code over Σ = Fsq does not mean it is far when we unfold, since we can change one coordinate per block of s. The onus is on the property proving step, to show for any additive code, the desired property profiles take the form (3.1) for every s. Now, we define the potential function and the threshold of row-span constrained r-local LCL properties identically as [LMS25], up to slightly modified notational conventions and normalization by n. We emphasize that these definitions are code-independent. Definition 3.7 (Potential and Threshold, [LMS25]). For an r-local pair (V, U ), and a real number R, define the potential function ϕV (U, R) := (R − 1) dim U + Ei∈[n] dim(U ∩ Vi ).

(3.2)

For W ⊊ U , define

dim(U ∩ Vi ) − dim(W ∩ Vi ) RV (U, W ) := 1 − Ei∈[n] . dim U − dim W

(3.3)

Define threshold of the r-local pair (V, U ) as RV (U ) := max RV (U, W ). W ⊊U

(3.4)

For a row-span constrained r-local LCL property, define RF :=

min RV (U ).

(V,U )∈F

(3.5)

We note that other sources, like [LMS25], define an r-local property to be the property of containing F. Since we are concerned with the property of avoiding a family F, we define it this way.

The only difference between the definition above and that in [LMS25] is the fact that the minimum in (3.5) is over profile-subspace pairs (V, U ) ∈ F rather than over profiles V ∈ F. Next, we unpack the definitions to interpret the threshold as a root of the potential function. Lemma 3.8 (Threshold interpretation). For every r-local profile V, W ⊊ U ∈ L(Frq ), and R ∈ R, ϕV (U, R) − ϕV (W, R) = (dim U − dim W )(R − RV (U, W )).

(3.6)

Let F be a row-span constrained r-local LCL family and let η ≥ 0. We observe that 1. If R ≤ RF − η, then for every (V, U ) ∈ F there exists W ⊊ U such that ϕV (U, R) − ϕV (W, R) ≤ −η.

(3.7)

2. If R ≥ RF + η, then there exists (V, U ) ∈ F such that for every W ⊊ U , ϕV (U, R) − ϕV (W, R) ≥ η.

(3.8)

Proof. To prove (3.6), we expand the left-hand side to obtain ϕV (U, R) − ϕV (W, R) = (R − 1)(dim U − dim W ) + Ei∈[n] [dim(U ∩ Vi ) − dim(W ∩ Vi )] (3.9) dim(U ∩ Vi ) − dim(W ∩ Vi ) = (dim U − dim W ) R − 1 + Ei∈[n] dim U − dim W = (dim U − dim W )(R − RV (U, W )). For (1), fix (V, U ) ∈ F. Since RF ≤ RV (U ) = max RV (U, W ), W ⊊U

(3.10)

there exists W ⊊ U such that R ≤ RV (U, W ) − η. Hence ϕV (U, R) − ϕV (W, R) = (dim U − dim W )(R − RV (U, W )) ≤ −η(dim U − dim W ) ≤ −η. (3.11) For (2), choose (V, U ) ∈ F with RV (U ) = RF . Then for every W ⊊ U , R ≥ RF + η = RV (U ) + η ≥ RV (U, W ) + η.

(3.12)

Therefore ϕV (U, R) − ϕV (W, R) = (dim U − dim W )(R − RV (U, W )) ≥ η(dim U − dim W ) ≥ η,

(3.13)

as desired. We also see that by our definition of profile containment for additive (rather than linear) codes, the threshold rate RV is preserved for profiles taking tensor form in (3.1) as s changes. Intuitively, this is because (U, V, W ) are all independent of s, so potential function ϕV⊗s (U, R) = ϕV (U, R). Then, RV⊗s (U, W ) is simply its root. We verify this directly. Proposition 3.9. Let (V, U ) be any r-local pair on plain codes in Fnq and let W ⊊ U . Then, for every s ∈ N RV ⊗s (U, W ) = RV (U, W ). (3.14) Consequently, for any row-span constrained local LCL family, RF = RF ⊗s is independent of s. 15

⊗s := Vi and indexed Proof. Fix any W ⊊ U . By definition, the length-sn profile V⊗s is given by V(i,j) by (i, j) ∈ [n] × [s]. Then, we see that " ⊗s ⊗s # dim(U ∩ V(i,j) ) − dim(W ∩ V(i,j) ) . RV⊗s (U, W ) = 1 − E(i,j)∈[n]×[s] dim U − dim W dim(U ∩ Vi ) − dim(W ∩ Vi ) = 1 − Ei∈[n] dim U − dim W = RV (U, W ).

Maximizing over U on both sides gives maxW ⊊U RV⊗s (U, W ) = maxW ⊊U RV (U, W ), as desired.

3.2

Behavior Under Quotients

We next record how local profile containment behaves under quotient maps. Remark 3.10 (Comparison to [GGH26]). In [GGH26], the spaces Vi , U can lie in an arbitrary vector space over Fq . In contrast, our definition of r-local pairs require Vi , U ⊂ Frq and is thus more concrete. However, this is at the expense of a less elegant quotient behavior: since our profiles are coordinate-dependent, a quotient by W ⊊ U is implemented by choosing a surjective linear map π : Frq → Frq

′

where

ker π = W.

(3.15)

This is the same as quotienting by W and choosing coordinates on the quotient. Definition 3.11 (Quotient profile). Let V = (V1 , . . . , Vn ) be an r-local pair and let π : Frq → Frq be a surjective linear map, so r′ ≤ r. Define the r′ -local profile πV := (πV1 , . . . , πVn ).

′

(3.16)

For an r-local pair (V, U ) and surjective linear map π, if W = ker π ⊊ U ⊂ Frq , then we say (πV, πU ) is a quotient pair of (V, U ). Then, the condition W ⊊ U is equivalent to πU ̸= 0. While the locality is changed in a quotient pair which in particular means it is no longer in F , we will see next that the potential, threshold, and code-containment are well-behaved. Lemma 3.12 (Quotient Containment). Suppose code C contains r-local pair (V, U ) and π : Frq → ′ Frq is a surjective linear map such that πU ̸= 0. Then, C contains (πV, πU ). Proof. Let M ∈ Fn×r witness that C contains (V, U ). Write π as an r′ × r matrix, and define q ′

M ′ := M π T ∈ Fn×r . q

(3.17)

Every column of M ′ is a linear combination of the columns of M , hence lies in C. For every i ∈ [n], ′ Mi⋆ = π(Mi⋆ ) ∈ πVi .

(3.18)

Finally, the row-span of M ′ is πU , so M ′ witnesses that C contains (πV, πU ). We remark that this definition of code containment works for all folding s. ′

Lemma 3.13 (Quotient Potential). Let π : Frq → Frq be a surjective linear map with kernel W ⊊ U ∈ L(Frq ). Then, for any R ∈ R, ϕπV (πU, R) = ϕV (U, R) − ϕV (W, R). 16

(3.19)

Proof. As W ⊂ U , dim(πU ) = dim U − dim W . For any i ∈ [n], we compute via rank-nullity that dim(πU ∩ πVi ) = dim(π(U ∩ (Vi + W ))) = dim(U ∩ Vi + W ) − dim W = dim(U ∩ Vi ) − dim(W ∩ Vi ) (3.20) by repeatedly noting ker π = W ⊂ U . Now, substituting into the definition of the potential gives ϕπV (πU, R) = (R − 1) dim(πU ) + Ei∈[n] dim(πU ∩ πVi ) = (R − 1)(dim U − dim W ) + Ei∈[n] [dim(U ∩ Vi ) − dim(W ∩ Vi )]

(3.21)

= ϕV (U, R) − ϕV (W, R), as desired. Finally, we present a useful corollary of the low-rate code profile containment via the quotient characterization. We emphasize that this is code-independent, and reduces the low-rate directions of the threshold proofs of various codes into simple code-specific counting. Lemma 3.14 (Maximal Quotient). If a code C contains an r-local pair (V, U ) and R ≤ RV (U ) − η ′ for some R, η ≥ 0, then there exists a surjective linear map π : Frq → Frq such that • W := ker π ⊊ U , • C contains r′ -local pair (πV, πU ), • ϕπV (πU, R) ≤ −η dim πU . Moreover, we can choose π such that ϕπV (U ′ , R) ≤ −η dim U ′ for all nonzero subspaces U ′ ⊂ πU . Proof. From assumption, we know that there exists subspace W ⊊ U such that R ≤ RV (U, W ) − η. By Lemma 3.8, we know that ϕV (U, R) − ϕV (W, R) = (dim U − dim W )(R − RV (U, W )) ≤ ϕV (U, R) − ϕV (W, R) ≤ −η. (3.22) Choose W ⊊ U maximal under inclusion among those satisfying ϕV (W, R) ≥ ϕV (U, R) + η.

(3.23)

′

Let π : Frq → Frq be any surjective linear map with kernel W ⊊ U . Because C contains (V, U ), Lemma 3.12 implies that C contains (πV, πU ). By Lemma 3.13, ϕπV (πU, R) = ϕV (U, R) − ϕV (W, R) ≤ −η dim(πU ).

(3.24)

This proves the three bullet points. e := π −1 (U ′ ) ∩ U . Then For the last conclusion, pick any nonzero subspace U ′ of πU . Let U e ⊊ U. W ⊊U

(3.25)

The containment is strict on the left because U ′ ̸= 0, and strict on the right because U ′ ⊊ πU . By e whose image under π is U ′ , we have that Lemma 3.13 applied to U e , R) − ϕV (W, R) = ϕV (U e , R + η) − ϕV (W, R + η) − η(dim(Ũ ) − dim W ). (3.26) ϕπV (U ′ , R) = ϕV (U e must satisfy By maximality of W , the strictly larger subspace U e , R + η) ≤ ϕV (W, R + η) ϕV (U

(3.27)

and dim Ũ −dim W = dim U ′ . Therefore, (3.26) is at most −η dim U ′ , proving the last statement. 17

3.3

Thresholds for Random Ensembles of Codes

In this section, we prove that RV (U ) is the threshold rate for various random ensembles of codes C to contain (V, U ). Then, we can lift it to row-span constrained local LCL families F via a union bound over all pairs in F . 3.3.1

Random Linear Codes

Lemma 3.15. Let (V, U ) be an r-local pair, let MV (U ) be the set of matrices M ∈ Fn×r with q ⋆ row-span U that satisfy V, and let MV (U ) be those with row-span contained in U . For any R ∈ R, |MV (U )| ≤ |M⋆V (U )| = q n((1−R)·dim U +ϕV (U,R)) .

(3.28)

Proof. Let V = (V1 , · · · , Vn ). Now, the i-th row of any such matrix in M⋆V (U ) is Vi ∩ U . There are q dim(Vi ∩U ) choices for the row, so |M⋆V (U )| = q

i=1 dim(Vi ∩U )

= q n((1−R)·dim U +ϕV (U,R)) .

Trivially, |MV (U )| ≤ |M⋆V (U )|. Theorem 3.16 (Fixed-Pair Random Linear Code Threshold). Let (V, U ) be an r-local pair and let C ⊂ Fnq be a random linear code of rate R. 1. If R ≤ RV (U ) − η for some η > 0, then P(C contains (V, U )) ≤ q −ηn

(3.29)

2. If R ≥ RV (U ) + η for some η > 0, then 2

P(C contains (V, U )) ≥ 1 − q r −ηn

(3.30)

The low-rate direction (1) will essentially follow from Lemma 3.14 and a few simple lemmas that we state first. Lemma 3.17 ([LMS25, Lemma 4.1]). If C ⊂ Fnq is an RLC of rate R, then for any M ∈ Fn×r q P(M⋆j ⊂ C ∀ j ∈ [r]) = q (R−1)n·rank(M )

(3.31)

The idea behind Lemma 3.17 is to view C as the kernel of (1 − R)n many linear constraints in

Fnq which column-span of M needs to satisfy. Each of rank(M ) basis vectors satisfies them with probability q −(1−R)n . We note that this is the only RLC-specific ingredient we use. Combining with Lemma 3.15, we obtain the following corollary, which intuitively explains why ϕV (U, R) characterizes the containment of (V, U ) in a random linear code of rate C.

Corollary 3.18. The expected number of witnesses matrices M for the containment of an r-local pair (V, U ) in a random linear code C with rate R ∈ [0, 1] is at most q nϕV (U,R) . Proof. By Lemma 3.15, the number of matrices with row-span U that satisfy V is at most q n((1−R)·dim U +ϕV (U,R))

(3.32)

For any such matrix, it is contained in C with probability at most q (R−1)n dim U by Lemma 3.17. Combining with (3.32) gives the desired bound. 18

With these lemmas, we deduce Theorem 3.16. Proof of Theorem 3.16. For the low-rate case (1), if C contains (V, U ), then by Lemma 3.14, there is ′ a surjective linear map π = π(V,U ) : Frq → Frq such that C contains (πV, πU ) and ϕπV (πU, R) ≤ −η. By a union bound and Corollary 3.18, P(C contains (V, U )) ≤ P(C contains (πV, πU )) ≤ q nϕπV (πU,R) ≤ q −ηn .

(3.33)

For the high-rate case (2), we know that R ≥ RV (U, W )+η for every W ⊊ U . Then, ϕV (U, R) ≥ ϕV (W, R) + η for all W ⊊ U . Let random variable XW be the number of witnesses matrices M for the containment by C of an r-local pair (V, W ). By Corollary 3.18, we know that (3.34)

E[XW ] ≤ q nϕV (W,R)

Now, let us fix any code C of rate R ∈ [0, 1] and consider matrices M⋆V (U ) that satisfies V and has row-span contained in U . By Lemma 3.15, we know that (3.35)

|M⋆V (U )| = q n((1−R)·dim U +ϕV (U,R)) .

Now, for any realization of C, requiring each column of M to lie in C imposes at most (1−R)n dim U independent constraints, since C has codimension (1 − R)n and the row-span is contained in U . Therefore, the number of M ∈ M⋆V (U ) contained in C is X XW ≥ |M⋆V (U )|q (R−1)n dim U = q nϕV (U,R) (3.36) W ∈L(U )

deterministically for every realization C. Now, C contains (V, U ) if and only if XU > 0, so P(C does not contain (V, U )) = P(XU = 0)   X ≤ P XW ≥ q nϕV (U,R)  W ⊊U

P ≤ ≤

(3.37)

W ⊊U E[XW ] q nϕV (U,R)

q nϕV (W,R)−nϕV (U,R)

W ⊊U

≤ |L(U )|q −ηn 2

where we apply Markov’s inequality and (3.34). Now, the conclusion follows |L(U )| ≤ q r . We now lift Theorem 3.16 to the whole row-span constrained LCL family F. Corollary 3.19 (Random Linear Code Threshold). Let F be a row-span constrained r-local property and let C ⊂ Fnq be a random linear code of rate R. 1. If R ≤ RF − η for some η > 0, then P(C contains F) ≤ |F|q −ηn

(3.38)

2. If R ≥ RF + η for some η > 0, then 2

P(C contains F) ≥ 1 − q r −ηn 19

(3.39)

Proof. For (1), note that by a union bound and Theorem 3.16(1), we have that X P(C contains (V, U )) ≤ |F|q −ηn P(C contains F) ≤

(3.40)

(V,U )∈F

as R ≤ RF ≤ RV (U ) for any (V, U ) ∈ F. This proves (1). For (2), let (V, U ) be the minimizing pair such that RF = RV (U ). Then, R ≥ RV (U ) + η, so 2

P(C contains (V, U )) ≥ 1 − q r −ηn

(3.41)

by Theorem 3.16(2). If C contains (V, U ), then C contains F by definition, which establishes the corollary. Therefore, when |F| = q o(n)8 , we know that RF is the threshold for RLCs for large n and q: RLCs of rate less than RF avoid F with high probability; RLCs of rate greater than RF contain F with high probability. 3.3.2

Random Reed-Solomon Codes

We next record the analogue of the low-rate local threshold Corollary 3.19(1) for random ReedSolomon code: if the rate is below the threshold of a row-span constrained LCL family, the random Reed-Solomon code is unlikely to contain the family. We use the following result from [LMS25] as a black box. Lemma 3.20 ([LMS25, Proposition 6.1]). Let n ≤ q with q a prime power, and let r ∈ N. Let V = (V1 , · · · , Vn ) be an r-local profile, U ∈ L(Frq ), and let 0 ≤ R ≤ 1 such that for all U ′ ∈ L(U ), ϕV (U ′ , R) ≤ −ε · dim U ′ . Then, with probability taken over uniformly random α1 , . . . , αn ∈ Fq , we have εn/2r (4r)4r k r P C = RSFq (α1 , . . . , αn , k) contains V with span U ̸= {0} ≤ (2 − 1) . εq Corollary 3.21 (Random Reed-Solomon Code Threshold: Low Rate Direction). Let F be a rowspan constrained r-local property and let C ⊂ Fnq be a random Reed-Solomon code of rate R. If R ≤ RF − η for some η > 0, then (4r)4r Rn P(C contains F) ≤ |F|(2 − 1) ηq r

ηn/2r

(3.42)

Proof. We first assume that due to Lemma 3.14, for every (V, U ) ∈ F , there exists a surjective ′ linear map π : Frq 7→ Frq such that if C contains (V, U ), then it also contains (πV, πU ), and for all subspaces U ′ ⊂ πU ϕπV (U ′ , R) < −η dim U ′ . Now, (3.42) follows directly from Lemma 3.20. 8

Some previous literature, e.g. [LMS25], call such F reasonable

3.3.3

Random LDPCs (Gallager’s Ensemble)

We next record the analogue of the low-rate local threshold Corollary 3.19(1) and Corollary 3.21 for random LDPC codes drawn from Gallager’s Ensemble (Definition 2.4). There is one important difference from random linear codes. For RLCs, the probability that a fixed matrix M is contained in the code is exactly q (R−1)n rank(M ) by Lemma 3.17. For LDPC codes C, this exact identity is false. Instead, [MRRZ+ 21] proves that, after conditioning on the usual good-distance event defined for C = RLDPC(n, q, s, R) as 1 −1 Good := ∆(C) ≥ hq (1 − R) , (3.43) 2 then C contains any fixed matrix with essentially the same probability as a random linear code, up to a factor q εn . This is the only LDPC-specific input we need. We first recall the lemma from [MRRZ+ 21] saying that Good happens with high probability. Lemma 3.22 ([MRRZ+ 21, Theorem 2.14]). For any finite field Fq and R ∈ [0, 1 − 1/q), there exists s0 = s0 (R, q) such that for every s > s0 , with probability over C = RLDPC(n, q, s, R) 1 P(Good) := P ∆(C) ≥ h−1 (1 − R) ≥ 1 − on→∞ (1). (3.44) 2 q The next lemma is the fixed-pair containment estimate for row-span constrained local profiles. This lemma follows [MRRZ+ 21], but we restate it in our framework and provide a proof in Section A for completeness. Lemma 3.23 (RLDPCs containing local profiles). For any ε, R ∈ (0, 1), positive integer r, finite field Fq , there exists an s0 = s0 (ε, r, R, q) such that the following holds for all odd s > s0 and sufficiently large n. Let V = (V1 , . . . , Vn ) be an r-local profile and let U ∈ L(Frq ). For C = RLDPC(n, q, s, R), 1 P(C contains (V, U )|Good) ≤ q nϕV (U,R)+εn where Good := ∆(C) ≥ h−1 (1 − R) . (3.45) 2 q We next obtain the thresholds for RLPDC codes. The changes from the RLC counterparts are: • We need to condition on the good-distance event Good and then account for the error term P(Goodc ) = on→∞ (1) from Lemma 3.22. • We apply the LDPC-specific replacement Lemma 3.23 instead of the RLC first moment bound Lemma 3.17, with an additional q ηn/2 slack in the exponent. Other than these changes, we follow Theorem 3.16: the low-rate direction again uses the quotient lemma to reduce containment below threshold to containment of a quotient pair with negative potential; the high-rate direction again uses the deterministic lower bound on the number of contained matrices with row-span contained in U , followed by Markov’s inequality to show that lower-dimensional row-spans cannot account for all such matrices. Theorem 3.24 (Fixed-Pair Random LDPC Threshold). Let (V, U ) be an r-local pair and let C = RLDPC(n, q, s, R) be a random LDPC code from Gallager’s ensemble. Define the event 1 (1 − R) . (3.46) Good := ∆(C) ≥ h−1 2 q For every R, η ∈ (0, 1), positive integer r, and finite field Fq , there exists s0 = s0 (η, r, R, q) such that for every odd s > s0 , the following holds for all sufficiently large n: 21

1. If R ≤ RV (U ) − η, then P(C contains (V, U )|Good) ≤ q −ηn/2 , and so P(C contains (V, U )) ≤ q −ηn/2 + on→∞ (1).

(3.47)

2. If R ≥ RV (U ) + η, then P(C contains (V, U )|Good) ≥ 1 − q r −ηn/2 , and so 2

P(C contains (V, U )) ≥ 1 − q r −ηn/2 − on→∞ (1). Proof. By Lemma 3.22, after increasing s0 if necessary, P(Good) ≥ 1 − on→∞ (1), where 1 −1 Good := ∆(C) ≥ hq (1 − R) . 2

(3.48)

(3.49)

We first prove the low-rate case (1). Suppose R ≤ RV (U ) − η. By Lemma 3.14, there exists a ′ surjective linear map π : Frq → Frq such that if C contains (V, U ), then C contains (πV, πU ), and ϕπV (πU, R) ≤ −η. Therefore, by Lemma 3.23 with parameter η/2, P(C contains (V, U )|Good) ≤ P(C contains (πV, πU )|Good) ≤ q nϕπV (πU,R)+ηn/2 ≤ q −ηn/2 . (3.50) Adding P(Goodc ) = on→∞ (1) gives the low-rate case (1). For the high-rate case (2), we know that R ≥ RV (U, W ) + η for every W ⊊ U . By Lemma 3.8, ϕV (U, R) ≥ ϕV (W, R) + η. Let random variable XW be the number of witnesses matrices M for the containment by C of an r-local pair (V, W ). By Lemma 3.23 with parameter ε = η/2, E[XW | Good] ≤ q nϕV (W,R)+ηn/2 ,

(3.51)

for every W ∈ L(U ). Next, as in the RLC case, we let M⋆V (U ) be the vector space of matrices satisfying V and having row-span contained in U . By Lemma 3.15, M ∈ Fn×r q |M⋆V (U )| = q n((1−R) dim U +ϕV (U,R)) .

(3.52)

deterministically for every realization C. Now, C contains (V, U ) if and only if XU > 0. Therefore, conditioned on Good, we apply Markov’s inequality and (3.51) as before to obtain P(C does not contain (V, U )|Good) = P(XU = 0|Good)   X ≤ P XW ≥ q nϕV (U,R) Good W ⊊U

P ≤ ≤

W ⊊U E[XW | Good] q nϕV (U,R)

q n(ϕV (W,R)−ϕV (U,R))+ηn/2

W ⊊U

≤ |L(U )|q −ηn/2 2

≤ q r −ηn/2 . 2

as |L(U )| ≤ q r . Adding P(Goodc ) = on→∞ (1) gives the high-rate case (2). 22

(3.54)

Remark 3.25. We will only use the statement (1) from Theorem 3.24 later in this paper, but we include the statement and proof of (2) for completeness. This should not be confused with a converse to the local-property transfer theorem for RLDPC codes ([MRRZ+ 21, Theorem 1.9]), which is false at that level of generality, as observed in [MRRZ+ 21]; our argument uses the additional linear coordinate-wise profile structure of row-span constrained LCL properties. As before, we now lift Theorem 3.24 to the whole row-span constrained LCL family F . Corollary 3.26 (Random LDPC Code Threshold). Let F be a row-span constrained r-local property and let C = RLDPC(n, q, s, R) be a random LDPC code from Gallager’s ensemble (Definition 2.4). For every R, η ∈ (0, 1), positive integer r, and finite field Fq , there exists s0 = s0 (η, r, R, q) such that for every odd s > s0 , the following holds for all sufficiently large n: 1. If R ≤ RF − η, then

P(C contains F) ≤ |F|q −ηn/2 + on→∞ (1)

(3.55)

2. If R ≥ RF + η, then 2

P(C contains F) ≥ 1 − q r −ηn/2 − on→∞ (1)

(3.56)

Proof. For (1), note that by a union bound and Theorem 3.24(1), we have that X P(C contains F) ≤ P(Goodc )+ P(C contains (V, U )|Good) ≤ on→∞ (1)+|F |q −ηn/2 , (3.57) (V,U )∈F

as R ≤ RF ≤ RV (U ) for any (V, U ) ∈ F. This proves (1). For (2), let (V, U ) be the minimizing pair such that RF = RV (U ). Then, R ≥ RV (U ) + η, so 2

P(C contains (V, U )) ≥ 1 − q r −ηn/2 − on→∞ (1)

(3.58)

by Theorem 3.24(2). If C contains (V, U ), then C contains F by definition, which establishes the corollary.

3.4

Threshold for Subspace Design Codes

Informally, for ordinary r-local properties where every row-span U ∈ Ldist (Frq ) is permitted for each profile V, [BCDZ25, Theorems 3.1, 4.2] shows that the threshold of containing V is dictated by τ (r) versus RV . For good subspace design codes, like folded Reed-Solomon codes, we have τ (r) ≈ R, which means that good subspace design codes and random linear codes share the same threshold. We generalize these results to row-span constrained local properties. We emphasize that the transfer works at the level of any pair (V, U ) via the following theorem. Theorem 3.27 (Fixed-Pair Subspace Design Code Threshold). Let (V, U ) be an r-local pair. Then 1. Let C ⊂ (Fsq )n be an additive τ -subspace design code. If τ (r) < RV (U ), then C does not contain (V, U ). 2. For any η > 0, there exists a τ -subspace design additive code C ⊂ (Fsq )n with τ (r) ≤ RV (U )+η that contains (V, U ). The statement (1) in Theorem 3.27 essentially follows from Lemma 3.14 and the subspace design condition. 23

Proof of Theorem 3.27(1). Suppose τ (r) ≤ RV (U ) − η, then by Lemma 3.14 there exists surjective ′ linear map π : Frq → Frq such that ϕπV (πU, τ (r)) < 0 and C contains (πV, πU ). The latter implies the existence of a witness matrix M . Let the columns of the witness matrix M for (πV, πU ) be cj = Enc(aj ) and define the message subspace A := span(aj ). Since the encoder is injective and the witness matrix has row-span πU , d := dim A = dim(πU ). For each coordinate i ∈ [n], the image Enci (A) ⊂ Fsq is the column span of the i-th “block” of the witness matrix. The rows of that block lie in πU ∩ πVi , hence dim(πU ∩ πVi ) ≥ dim Enci (A) = dim A − dim(A ∩ ker(Enci )).

(3.59)

where the equality follows from rank-nullity. Averaging over i and applying the subspace design condition Definition 2.12 with d = dim A ≤ r, we obtain that d − Ei∈[n] dim(πU ∩ πVi ) ≤ Ei∈[n] dim(A ∩ ker(Enci )) ≤ τ (r)d.

(3.60)

Rearranging gives ϕπV (πU, τ (r)) ≥ 0, a contradiction. Thus, C does not contain (V, U ). For the statement (2) in Theorem 3.27, we use the following theorem from [BCDZ25] that shows RLCs are good subspace design codes when viewed as an Fq -additive code with alphabet Fsq . Theorem 3.28 ([BCDZ25, Theorem 4.1]). Fix any η > 0. A random Fq -additive code C ⊂ (Fsq )n with rate R = k/sn satisfies 2

P(τ (r) ≤ R + η) ≥ 1 − rq −ηsrn+3(r +1)n .

(3.61)

Proof of Theorem 3.27(2). Fix η > 0 and let R = RV (U ) + η/2. For sufficiently large s, we know by Theorem 3.28 that, for a random Fq -additive code C ⊂ (Fsq )n of rate R, η P τ (r) ≤ RV (U ) + η = R + ≥ 1 − os→∞ (1), (3.62) 2 On the other hand, R = RV (U ) + η/2 = RV⊗s (U ) + η/2 by Proposition 3.9. By Theorem 3.16, 2

P(C contains (V, U )) = P(unfolded C contains (V⊗s , U )) ≥ 1 − q r −ηsn/2 = 1 − os→∞ (1). (3.63) Therefore, we can pick sufficiently large s such that with probability 2/3, C contains (V, U ) and is a τ -subspace design code with τ (r) ≤ RV (U ) + η. This proves (2). Remark 3.29. Compared to [BCDZ25, Theorem 4.2], we take the subspace design parameter d in τ (d) to be d = r for simplicity. We can obtain analogous threshold statements for RF by taking the minimum over F. Corollary 3.30 (Subspace Design Code Threshold). Let F be any row-span constrained r-local LCL family. Then 1. Let C ⊂ (Fsq )n be an additive τ -subspace design code. If τ (r) < RF , then C avoids F. 2. For any η > 0, there exists a τ -subspace design additive code C ⊂ (Fsq )n with τ (r) ≤ RF + η that contains F . Proof. For (1), note that for any (V, U ) ∈ F , we have that τ (r) < RF ≤ RV (U ), so C does not contain (V, U ) by Theorem 3.27. This holds for any pair in F, so C avoids F . For (2), choose a pair (V, U ) ∈ F attaining the minimum, so RF = RV (U ). By Theorem 3.27(2), for any η > 0, there exists a τ -subspace design additive code C ⊂ (Fsq )n such that τ (r) ≤ RV (U ) + η = RF + η and C contains (V, U ). Since (V, U ) ∈ F , this means that C contains F . 24

(3.64)

Curve-Decoding as a Row-Span Constrained LCL Property

Recall the definition of curve-decoding: Definition 2.7 (Curve-Decodability). An additive code C ⊂ Σn is (ℓ, δ, a, b) curve-decodable if for every u0 , u1 , · · · , uℓ ∈ Σn , all functions f : Fq → C, whenever the set ℓ n o X A= α∈F:∆ uj αj , f (α) ≤ δ j=0

has at least a elements, there exist c0 , c1 , · · · , cℓ ∈ C such that ℓ n o X α ∈ A : f (α) = cj αj ≥ b . j=0

As observed in [GG25] and discussed in Section 1.2, curve-decoding does not seem to fit immediately into the LCL framework. However, we will show that it does fit into a row-span constrained LCL framework, via Definition 3.3. Before we describe the correct row-span constraint, we define the degree-ℓ Reed-Solomon evaluation subspace on B by RSℓ (B) := {(p(α))α∈B : p ∈ Fq [x], deg p ≤ ℓ} ⊂ FB q . Thus RSℓ (B) is the space of scalar degree-ℓ evaluation patterns on the parameter set B. Definition 4.1 (Curve-free Subspaces). Let A ⊂ Fq . A subspace U ∈ L(FA q ) is (ℓ, A, b) curve-free B denote coordinate restriction to B. → F if πB (U ) ̸⊂ RSℓ (B) for every B ∈ Ab , where πB : FA q q For this definition to be non-trivial, we assume ℓ + 1 ≤ b ≤ |A|. Now, we observe the following lemma, which translates (ℓ, A, b) curve-freeness of the row-span of a matrix to the condition that no b columns lie on a degree-ℓ curve. ×A with rowLemma 4.2. Let B ⊂ A ⊂ Fq and let N be a positive integer.9 Fix a matrix M ∈ FN q A span U ∈ L(Fq ). Then, πB (U ) ⊂ RSℓ (B) if and only if there exists a degree-ℓ curve g : Fq → FN q such that g(α) = M⋆α for every α ∈ B.

Proof. Suppose such a curve g exists. For each i ∈ [N ], the restricted row (Miα )α∈B = (g(α)m )α∈B . Since any v ∈ πB (U ) is a linear combination of these restricted rows, we observe that v ∈ RSℓ (B) as witnessed by the corresponding linear combination of degree-ℓ polynomials gi . Conversely, suppose πB (U ) ⊂ RSℓ (B). Then, for each i ∈ [N ], the restricted row (Miα )α∈B ∈ RSℓ (B). Hence there exists a scalar polynomial gi (x) of degree at most ℓ such that gi (α) = Miα for every α ∈ B. Collecting these scalar polynomials gives a degree-ℓ curve g(x) = (g1 (x), . . . , gN (x)) ∈ FN q gives g(α) = M⋆α for every α ∈ B, proving the second condition. Observe that latter condition is exactly the kind of codeword condition we wish to impose on columns of witness matrices for the failure of (ℓ, δ, a, b) curve-decoding. Lemma 4.2 gives an equivalent row-span constraint. We make this more formal below. 9

Think of N as either the block length N = n of a linear code C ⊂ Fn q ; or the block length N = sn of an “unfolded” Fq -additive code C ⊂ (Fsq )n , thought of as C ⊂ Fsn q .

×A be a matrix with row-span U whose columns lie in Corollary 4.3. Let A ⊂ Fq and let M ∈ FN q a linear code C ⊂ FN q . If ℓ < b ≤ |A|, then U is (ℓ, A, b) curve-free if and only if no b columns of P M lie on a degree-ℓ “codeword curve.” (That is, if and only if there is no curve c(x) = ℓi=0 ci xi for ci ∈ C and no set B ∈ Ab so that c(α) = M⋆α for all α ∈ B.) Proof. By Lemma 4.2, for each B ∈ Ab , the condition πB (U ) ⊂ RSℓ (B) is equivalent to the existence of a degree-ℓ curve through the columns indexed by B. If such a curve exists, then it must agree with the unique interpolation curve of degree at most ℓ, through some fixed ℓ + 1 ≤ b columns of M among those indexed by B. Since these columns lie in linear code C and interpolation is linear, this curve can be taken to have coefficients in C, i.e. a degree-ℓ codeword curve.

We now W cast curve-decoding as a row-span constrained LCL property, thereby bypassing the notion of -decodability from [GG25], and the parameter losses that arose from it. Theorem 4.4 (Locality of curve-decoding). Let ℓ, a, b ∈ N with ℓ + 1 ≤ b ≤ a ≤ q and let δ ∈ (0, 1). Then there exists a row-span constrained a-LCL family F with 2

|F| ≤ q a+a 2an such that every Fq -additive code C is not (ℓ, δ, a, b) curve-decodable if and only if C contains F. Proof. Fix indexing sets A ∈ Faq and Iα ⊂ [n] with |Iα | ≥ (1 − δ)n for each α ∈ A. For each choice of A, {Iα }α∈A , we will define an r-local profile V = V(A, {Iα }α∈A ) = (V1 , . . . , Vn ) as follows. For each i ∈ [n], let Ai := {α ∈ A : i ∈ Iα }. Define Vi := y ∈ FA (4.1) q : (yα )α∈Ai ∈ RSℓ (Ai ) . Equivalently, y ∈ Vi if there exists a polynomial p ∈ Fq [x] of degree at most ℓ such that p(α) = yα for every α ∈ Ai . This is clearly a linear subspace of FA q . Now define

Fq [n] A F := (V(A, {Iα }α∈A ), U ) : A ∈ , Iα ∈ , U ∈ L(Fq ) is (ℓ, A, b) curve-free . a ≥ (1 − δ)n (4.2) We show the bound on the size of F: There are aq ≤ q a choices for A, at most 2n choices for 2 each Iα ⊂ [n], and the number of choices of U is at most |L(Faq )| ≤ q a . Next, we prove that not being curve-decodable is equivalent to containing F . Not curve-decodable ⇒ Contains F : If C ⊂ (Fsq )n is not (ℓ, δ, a, b) curve-decodable, then there exists A ∈ Faq , a degree-ℓ curve u : Fq → (Fsq )n , and codewords f (α) ∈ C such that ∆(u(α), f (α)) ≤ δ for every α ∈ A, but no degree-ℓ codeword curve passes through f (α) for b-many of α. For α ∈ A, define the agreement set Iα := {i ∈ [n] : u(α)i = f (α)i }, so |Iα | ≥ (1 − δ)n. Form the matrix M ∈ Fsn×A with columns M⋆α = f (α) ∈ C. Index the rows by [n] × [s] and let U be q the row-span of M . We check the local profile constraints. For any (i, j) ∈ [n] × [s], the corresponding row Mij,⋆ = (f (α)ij )α∈A . Since f (α)ij = u(α)ij whenever i ∈ Iα , we observe that Mij,⋆ agrees with a polynomial x 7→ u(x)ij of degree at most ℓ on Ai , so Mij,⋆ ∈ Vi by the definition of Vi in (4.1). By assumption, no b of the columns f (α) lie on a degree-ℓ codeword curve. By Corollary 4.3, the row-span U is (A, ℓ, b) curve-free. Hence M witnesses that C contains (V(A, {Iα }α∈A ), U ) ∈ F.

Contains F ⇒ Not curve-decodable: Suppose C contains the a-local pair (V(A, {Iα }α∈A ), U ) via witness matrix M ∈ Fsn×A . Let the columns of M be f (α) ∈ C for α ∈ A. q We construct a degree-ℓ curve close to these codewords. For (i, j) ∈ [n] × [s] the row Mij,⋆ lies in Vi , so by definition (4.1) of Vi , there exists a polynomial uij of degree at most ℓ such that uij (α) = f (α)ij for every α ∈ Ai := {α ∈ A : i ∈ Iα }. Collecting these polynomials over all (i, j) defines a degree-ℓ curve u : Fq → (Fsq )n . For each α ∈ A, if i ∈ Iα so α ∈ Ai , then uij (α) = f (α)ij for every j ∈ [s]. Hence, u(α)i = f (α)i for all i ∈ Iα . For every α ∈ A, |Iα | ≥ (1 − δ)n, so ∆(u(α), f (α)) ≤ δ. Finally, since U is (A, ℓ, b) curve-free, Corollary 4.3 implies that no b of the columns f (α) lie on a degree-ℓ codeword curve. Together, u and f (α) witness that C is not (ℓ, δ, a, b) curve-decodable. We now plug in specific choices of parameters from Theorem 2.15 for which subspace design codes are curve-decodable, thereby obtaining a lower bound on the threshold rate via Corollary 3.30. Corollary 4.5. Let δ, η ∈ (0, 1) and integers ℓ, a, b ∈ N such that ℓ+1 ηa d := ≤ a and b ≤ . η d+η

(4.3)

Let F be the row-span constrained a-local LCL family from Theorem 4.4, so avoiding F is equivalent 2 to being (ℓ, δ, a, b) curve-decodable. Then, RF ≥ 1 − δ − η. Additionally, |F| ≤ q a+a 2an . Proof. We claim that every τ -subspace design code C with τ (a) ≤ 1 − δ − η must avoid F. Indeed, as d ≤ a and τ is monotone, we know that τ (d) ≤ τ (a) ≤ 1 − δ − η.

(4.4)

By Theorem 2.15, C is (ℓ, 1 − τ (d) − η, a, ηa/(d + η)) curve-decodable. As b ≤ ηa/(d + η) and δ ≤ 1 − τ (d) − η by (4.4), C is (ℓ, δ, a, b) curve-decodable, so it avoids F . Suppose RF < 1 − δ − η, then there exists constant γ > 0 such that RF + γ ≤ 1 − δ − η. By Corollary 3.30, there exists a τ -subspace design code with τ (a) ≤ RF + γ ≤ 1 − δ − η that contains F. This contradicts the claim above, so it must be RF ≥ 1 − δ − η, as desired. We conclude with a final specialization for the common choice of curve-decoding parameters. Corollary 4.6. Let ℓ ∈ N and δ, η ∈ (0, 1). Define a, b, d ∈ N by ℓ+1 4ℓ 100ℓ2 d := , b := +ℓ , a := . η η η3

(4.5)

Let F be the row-span constrained a-local LCL family from Theorem 4.4, so avoiding F is equivalent 2 to being (ℓ, δ, a, b) curve-decodable. Then, RF ≥ 1 − δ − η. Additionally, |F| ≤ q a+a 2an . Proof. It suffices to verify (4.3) to apply Corollary 4.5. Clearly, d ≤ a. We check that d+η ≤

ℓ+1 4ℓ ηa 100ℓ2 /η 2 25ℓ 4ℓ +1+η ≤ =⇒ ≥ = ≥ + ℓ + 1 ≥ b. η η d+η 4ℓ/η η η

Therefore, Corollary 4.5 applies to give the conclusion.

(4.6)

Improved Proximity Gaps

In this section we combine the result from Section 4 that curve-decoding is a row-span constrained LCL property with list-decoding results for random linear codes, random Reed–Solomon codes, and Gallager’s ensemble of random LDPC codes, in order to establish proximity gaps (as well as correlated agreement and mutual correlated agreement) for these ensembles. For each ensemble of codes, we use Corollary 4.6 to prove curve-decodability, then we combine this with list-decodability via Corollary 2.11.

5.1

Random Linear Codes

We begin by citing the list-decoding fact we use for random linear codes. This is immediate from [AGG+ 25] up to plugging in some parameters. Theorem 5.1 ([AGG+ 25, Theorem 1.3]). For every η ∈ (0, 1) and random linear code C ⊂ Fnq of 2 rate R, if q ≥ 2Ω(1/η ) and n ≥ Ω(1/η), then with high probability C is 3η 1 − R 1−R− , list-decodable. (5.1) 2 η Next, we put together the list-decoding and curve-decoding results required to apply Corollary 2.11 for random linear codes. Theorem 5.2. Let ℓ ∈ N and η, δ ∈ (0, 1). Let C ⊂ Fnq be a random linear code of rate R ≤ 1−δ−2η. If q ≥ exp(Ω(ℓ2 /η 4 )) and n ≥ Ω(ℓ4 /η 7 ), then with high probability C is both 100ℓ2 4ℓ η 1 − R , list-decodable and ℓ, δ, , +ℓ curve-decodable. (5.2) δ 1+ 2 η η3 η Proof. Let a, b, d be as in Corollary 4.6, and let F be the a-LCL property whose avoidance encodes (ℓ, δ, a, b) curve-decoding constructed in Theorem 4.4. By Corollary 4.6, RF ≥ 1 − δ − η, so R ≤ 1 − δ − 2η ≤ RF − η.

(5.3)

Therefore, by Corollary 3.19, 2

P(C contains F) ≤ |F|q −ηn ≤ q a +a−ηn 2an .

(5.4)

Since a = O(ℓ2 /η 3 ), the right-hand side is o(1) whenever q is sufficiently large, as assumed in the theorem. Hence, with high probability, C avoids F, so it is (ℓ, δ, a, b) curve-decodable. For list-decoding, observe that as R ≤ 1 − δ − 2η, η η 3η δ 1+ ≤δ+ ≤1−R− . 2 2 2

(5.5)

For q sufficiently large per the assumption in the theorem, Theorem 5.1 implies that, with high probability, C is (δ(1 + η/2), ⌈(1 − R)/η⌉) list-decodable. Taking a union bound over the list-decoding and curve-decoding events completes the proof. We are now ready to prove our main theorem on proximity gaps, correlated agreement, mutual correlated agreement of random linear codes.

Theorem 5.3 (PG, CA, and MCA for Random Linear Codes). Let ℓ ∈ N and η, δ ∈ (0, 1). Let C ⊂ Fnq be a random linear code of rate R ≤ 1 − δ − 2η. If q ≥ exp(Ω(ℓ2 /η 4 )) and n ≥ Ω(ℓ4 /η 7 ), then with high probability: 1. For every T ≥ 1, C is curve-decodable with parameters 2 1−R ℓ ℓ, δ, (T − 1) + O 3 ,T . η η

(5.6)

2. For every m > 1, C has correlated agreement, and hence proximity gap, with parameters ℓm⌈(1 − R)/η⌉ + O(ℓ2 /η 3 ) 1 ℓ, δ, . (5.7) , q m 3. C has mutual correlated agreement with parameters ℓn⌈(1 − R)/η⌉ + O(ℓ2 /η 3 ) ℓ, δ, . q

(5.8)

Proof. Let a, b be as in Corollary 4.6, and let L = ⌈(1 − R)/η⌉. By Theorem 5.2, C is (δ(1 + η/2), L) list-decodable and (ℓ, δ, a, b) curve-decodable with high probability. By Corollary 4.6, we observe that δ(1 + ℓ/(b − ℓ)) ≤ δ(1 + η/2), and therefore the hypotheses of Corollary 2.11 hold with this value of L. Since a = O(ℓ2 /η 3 ), the three conclusions follow directly from Corollary 2.11.

5.2

Random Reed-Solomon Codes

Our results naturally generalize to Reed-Solomon codes with random evaluation points (Definition 2.3). The proof is parallel to the random-linear-code case, except that the low-rate local threshold uses Corollary 3.21 and the list-decoding input is the following result from [AGG+ 25]. Theorem 5.4 ([AGG+ 25, Theorem 1.1]). For every η ∈ (0, 1) and random Reed-Solomon code 2 C ⊂ Fnq of rate R, if q ≥ n · 2Ω(1/η ) , then with high probability C is 3η 1 − R 1−R− , list-decodable. (5.9) 2 η Next, we put together the list-decoding and curve-decoding results required to apply Corollary 2.11 for random Reed-Solomon codes. Theorem 5.5. Let ℓ ∈ N and η, δ ∈ (0, 1). Let C ⊂ Fnq be a random Reed-Solomon code of rate R ≤ 1 − δ − 2η. If q ≥ n · exp(Ω(ℓ4 /η 7 )) and n ≥ Ω(ℓ4 /η 7 ), then with high probability C is both 100ℓ2 η 1 − R 4ℓ δ 1+ , list-decodable and ℓ, δ, , +ℓ curve-decodable. (5.10) 2 η η3 η Proof. Let a, b, d be as in Corollary 4.6, and let F be the a-LCL property whose avoidance encodes (ℓ, δ, a, b) curve-decoding constructed in Theorem 4.4. By Corollary 4.6, RF ≥ 1 − δ − η, so (5.11)

R ≤ 1 − δ − 2η ≤ RF − η. 2

Therefore, by Corollary 3.21 and that |F| ≤ q a +a 2an , (4a)4a Rn P(C contains F) ≤ |F|(2 − 1) ηq a

ηn/2a .

(5.12)

Since a = O(ℓ2 /η 3 ), the right-hand side is o(1) whenever q is sufficiently large per the assumption in the theorem. Hence, with high probability, C avoids F, so it is (ℓ, δ, a, b) curve-decodable. For list-decoding, observe that as R ≤ 1 − δ − 2η, η η 3η δ 1+ ≤δ+ ≤1−R− . (5.13) 2 2 2 For q sufficiently large as assumed in the theorem, Theorem 5.4 implies that, with high probability, C is (δ(1 + η/2), ⌈(1 − R)/η⌉) list-decodable. Taking a union bound over the list-decoding and curve-decoding events completes the proof. We are now ready to prove our main theorem on proximity gaps, correlated agreement, mutual correlated agreement of random Reed-Solomon codes. Theorem 5.6 (PG, CA, and MCA for Random Reed-Solomon Codes). Let ℓ ∈ N and η, δ ∈ (0, 1). Let C ⊂ Fnq be a random Reed-Solomon code of rate R ≤ 1 − δ − 2η. If q ≥ n · exp(Ω(ℓ4 /η 7 )) and n ≥ Ω(ℓ4 /η 7 ), then with high probability: 1. For every T ≥ 1, C is curve-decodable with parameters 2 1−R ℓ ℓ, δ, (T − 1) + O 3 ,T . η η

(5.14)

2. For every m > 1, C has correlated agreement, and hence proximity gap, with parameters ℓm⌈(1 − R)/η⌉ + O(ℓ2 /η 3 ) 1 , . (5.15) ℓ, δ, q m 3. C has mutual correlated agreement with parameters ℓn⌈(1 − R)/η⌉ + O(ℓ2 /η 3 ) ℓ, δ, . q

(5.16)

Proof. The proof is identical to that of Theorem 5.3, using Theorem 5.5 in place of Theorem 5.2.

5.3

Random LDPC Codes

Our results also naturally generalize to random LDPC codes from Gallager’s ensemble (Definition 2.4). The proof is parallel to the random-linear-code case: the low-rate local threshold is supplied by Corollary 3.26, and the list-decoding input follows from [MRRZ+ 21, Theorem 1.2], which transfers list-decodability of random linear codes (Theorem 5.1) to sufficiently sparse random LDPC codes. We begin by recording the list-decoding fact we use. Theorem 5.7. For every η, R ∈ (0, 1), there exists s0 = s0 (η, q, R) such that the following holds for every odd s > s0 . Let C = RLDPC(n, q, s, R) be a random LDPC code from Gallager’s ensemble 2 with rate R. If q ≥ 2Ω(1/η ) and n is sufficiently large, then with high probability C is 3η 2(1 − R) 1−R− , list-decodable. (5.17) 2 η This is an immediate consequence of [MRRZ+ 21, Theorem 1.2] and Theorem 5.1, which is exactly [AGG+ 25, Theorem 1.3]. 30

Remark 5.8. The factor of two loss in the list size of Theorem 5.7 compared to Theorem 5.1 comes from the small slack in the rate in [MRRZ+ 21, Theorem 1.2], and can be made arbitrarily small. Next, we put together the list-decoding and curve-decoding results required to apply Corollary 2.11 for random LDPC codes. Theorem 5.9. Let ℓ ∈ N and η, δ ∈ (0, 1), and let R ≤ 1 − δ − 2η. There exists s0 = s0 (ℓ, η, δ, q, R) such that the following holds for every odd s > s0 . Let C = RLDPC(n, q, s, R) be a random LDPC code from Gallager’s ensemble with rate R. If q ≥ exp(Ω(ℓ2 /η 4 )) and n is sufficiently large, then with high probability C is both η 2(1 − R) 100ℓ2 4ℓ δ 1+ list-decodable and ℓ, δ, , , +ℓ curve-decodable. 2 η η3 η (5.18) Proof. Let a, b, d be as in Corollary 4.6, and let F be the a-LCL property whose avoidance encodes (ℓ, δ, a, b) curve-decoding constructed in Theorem 4.4. By Corollary 4.6, RF ≥ 1 − δ − η, so R ≤ 1 − δ − 2η ≤ RF − η.

(5.19)

By Corollary 3.26, for sufficiently large odd s, we get 2

P(C contains F) ≤ |F|q −ηn/2 + on→∞ (1) ≤ q a +a−ηn/2 2an + on→∞ (1).

(5.20)

Since a = O(ℓ2 /η 3 ), the right-hand side is o(1) whenever q is sufficiently large, as assumed in the

theorem. Hence, with high probability, C avoids F, so it is (ℓ, δ, a, b) curve-decodable. For list-decoding, observe that as R ≤ 1 − δ − 2η, η η 3η δ 1+ ≤δ+ ≤1−R− . (5.21) 2 2 2 For q sufficiently large per the assumption in the theorem, Theorem 5.7 implies that, with high probability, C is (δ(1 + η/2), ⌈2(1 − R)/η⌉) list-decodable. Taking a union bound over the list-decoding and curve-decoding events completes the proof. We are now ready to prove our main theorem on proximity gaps, correlated agreement, mutual correlated agreement of random LDPC codes. Theorem 5.10 (PG, CA, and MCA for Random LDPC Codes). Let ℓ ∈ N and η, δ ∈ (0, 1). There exists s0 = s0 (ℓ, η, δ, q) such that the following holds for every odd s > s0 . Let C = RLDPC(n, q, s, R) be a random LDPC code from Gallager’s ensemble with rate R ≤ 1 − δ − 2η. If q ≥ exp(Ω(ℓ2 /η 4 )) and n is sufficiently large, then with high probability: 1. For every T ≥ 1, C is curve-decodable with parameters 2 2(1 − R) ℓ ℓ, δ, (T − 1) + O 3 ,T . η η

(5.22)

2. For every m > 1, C has correlated agreement, and hence proximity gap, with parameters ℓm⌈2(1 − R)/η⌉ + O(ℓ2 /η 3 ) 1 ℓ, δ, , . (5.23) q m 3. C has mutual correlated agreement with parameters ℓn⌈2(1 − R)/η⌉ + O(ℓ2 /η 3 ) ℓ, δ, . q

(5.24)

Proof. The proof is identical to that of Theorem 5.3, using Theorem 5.9 in place of Theorem 5.2. 31

References [ABF26]

Gal Arnon, Dan Boneh, and Giacomo Fenzi. Open problems in list decoding and correlated agreement. Cryptology ePrint Archive, Paper 2026/680, 2026. 3, 8

[ACFY25]

Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. Whir: Reedsolomon proximity testing with super-fast verification. In Advances in Cryptology– EUROCRYPT 2025-44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2025, Proceedings, pages 214–243. Springer Science and Business Media Deutschland GmbH, 2025. 4, 8

[AGG+ 25]

Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Ray Li, and Zihan Zhang. Random reed-solomon codes achieve list-decoding capacity with linear-sized alphabets. Advances in Combinatorics, 2025. 28, 29, 30

[AHIV17]

Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Proceedings of the 2017 acm sigsac conference on computer and communications security, pages 2087–2104, 2017. 8

[AHS26]

Vikrant Ashvinkumar, Mursalin Habib, and Shashank Srivastava. Algorithmic improvements to list decoding of folded reed-solomon codes. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 880–898. SIAM, 2026. 8

[BCDZ25]

Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. From random to explicit via subspace designs with applications to local properties and matroids. arXiv preprint arXiv:2510.13777, 2025. 1, 3, 5, 7, 8, 12, 13, 23, 24

[BCF+ 25]

Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D Rothblum, and Hadas Zeilberger. Blaze: fast snarks from interleaved raa codes. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 123– 152. Springer, 2025. 4

[BSCH+ 25] Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf. On proximity gaps for reed–solomon codes. Cryptology ePrint Archive, Paper 2025/2055, 2025. 8 [BSCI+ 23]

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for reed–solomon codes. Journal of the ACM, 70(5):1–57, 2023. 8

[BSGKS20] Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. Deep-fri: Sampling outside the box improves soundness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pages 5–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. 8 [BSKS18]

Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-case to average case reductions for the distance to a code. In 33rd Computational Complexity Conference (CCC 2018), pages 24–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. 8

[CS25]

Elizabeth Crites and Alistair Stewart. On Reed–Solomon proximity gaps conjectures. Cryptology ePrint Archive, 2025. 8 32

[CZ25]

Yeyuan Chen and Zihan Zhang. Explicit folded reed-solomon and multiplicity codes achieve relaxed generalized singleton bounds. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1–12, 2025. 8

[DG25]

Benjamin E Diamond and Angus Gruen. On the distribution of the distances of random words. Cryptology ePrint Archive, 2025. 8

[Eth26]

Ethereum Foundation. The proximity prize: Reed–solomon challenge, 2026. Accessed: 2026-04-29. 3, 4

[Gal63]

Robert G Gallager. Low-density parity-check codes. Low Density Parity Check Codes, 1963. 10

[GG25]

Rohan Goyal and Venkatesan Guruswami. Optimal proximity gaps for subspace-design codes and (random) reed-solomon codes. Cryptology ePrint Archive, 2025. 1, 3, 4, 5, 6, 7, 8, 11, 12, 13, 25, 26

[GGH26]

Rohan Goyal, Venkatesan Guruswami, and Jun-Ting Hsieh. Explicit constant-alphabet subspace design codes. arXiv preprint arXiv:2604.15218, 2026. 8, 16

[GK16]

Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161–185, 2016. 3, 8

[GLM+ 21]

Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. IEEE Transactions on Information Theory, 68(2):923–939, 2021. 8

[GMR+ 21]

Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Threshold rates for properties of random codes. IEEE Transactions on Information Theory, 68(2):905–922, 2021. 8

[GNR26]

Kobi Gurkan, Andrija Novakovic, and Ron D Rothblum. Bolt: Faster snarks from sketched codes. Cryptology ePrint Archive, 2026. 4

[GR08]

Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on information theory, 54(1):135–150, 2008. 8

[Hab24]

Ulrich Haböck. Basefold in the list decoding regime. Cryptology ePrint Archive, Paper 2024/1571, 2024. 11

[KKH26]

Dmitry Krachun, Stepan Kazanin, and Ulrich Haböck. Failure of proximity gaps close to capacity. Cryptology ePrint Archive, Paper 2026/782, 2026. 8

[KRZSW18] Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters. Improved decoding of folded reed-solomon and multiplicity codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 212–223. IEEE, 2018. 8 [LMS25]

Matan Levi, Jonathan Mosheiff, and Nikhil Shagrithaya. Random reed-solomon codes and random linear codes are locally equivalent. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2097–2131. IEEE, 2025. 1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 18, 20 33

[MRRZ+ 21] Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. Low-density parity-check codes achieve list-decoding capacity. SIAM Journal on Computing, 53(6):FOCS20–38–FOCS20–73, November 2021. 4, 8, 10, 21, 23, 30, 31, 34 [RVW13]

Guy N Rothblum, Salil Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 793–802, 2013. 8

[Sri25]

Shashank Srivastava. Improved list size for folded reed-solomon codes. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2040–2050. SIAM, 2025. 8

[Tam24]

Itzhak Tamo. Tighter list-size bounds for list-decoding and recovery of folded reed-solomon and multiplicity codes. IEEE Transactions on Information Theory, 70(12):8659–8668, 2024. 8

Appendix: Gallager’s Ensemble

In this appendix we prove Lemma 3.23, the fixed-pair containment estimate for row-span constrained local profiles in Gallager’s ensemble. The proof follows the same philosophy as [MRRZ+ 21]. 1. [MRRZ+ 21] proves that a fixed smooth matrix is contained in a random LDPC code with essentially the same probability as in a random linear code. 2. Random LDPC codes have good distance with high probability ([MRRZ+ 21, Theorem 2.14], stated as Lemma 3.22 earlier), so non-smooth matrices will not be contained after conditioning on the event 1 −1 Good := ∆(C) ≥ hq (1 − R) . 2 Combining these two facts gives the matrix-containment estimate that we aim to prove. We begin with the notion of smoothness used in [MRRZ+ 21]. is δ-smooth if for every nonzero x ∈ Frq , Definition A.1 (δ-smooth matrices). M ∈ Fn×r q ∆(M x, 0) ≥ δ.

(A.1)

Equivalently, the linear code generated by the columns of M has relative distance at least δ. In particular, a δ-smooth matrix has full column rank. The next input is the fixed smooth matrix containment estimate from [MRRZ+ 21]. Here M ⊂ C means that every column of M is contained in C. Lemma A.2 ([MRRZ+ 21, Lemma 2.13]). For every δ, ξ > 0 and r ∈ N, there exists s0 = s0 (δ, ξ, q, r) such that the following holds for every odd s > s0 and all sufficiently large n. Let M ∈ Fn×r be a δ-smooth matrix. If C = RLDPC(n, q, s, R), then q P(M ⊂ C) ≤ q (1−ξ)(R−1)rn .

(A.2)

We now upgrade the smooth-matrix estimate to an arbitrary fixed matrix, conditioned on Good. 34

Lemma A.3 (Fixed matrix containment under good distance). For every ε, R ∈ (0, 1), prime power q, and positive integer r, there exists s0 = s0 (ε, r, R, q) such that for every odd s > s0 , the following holds for all sufficiently large n. If C = RLDPC(n, q, s, R), then for every matrix M ∈ Fn×r , q P(M ⊂ C|Good) ≤ q

(R−1)n rank(M )+εn

Good :=

where

1 −1 ∆(C) ≥ hq (1 − R) . 2

(A.3) ′

Proof. Let r′ = rank(M ). Choose r′ linearly independent columns of M and let N ∈ Fn×r be the q −1 := corresponding submatrix. Since C is linear, M ⊂ C if and only if N ⊂ C. Fix δ hq (1 − R)/2. ′ If N is not δ-smooth, then there exists a nonzero x ∈ Frq such that ∆(N x, 0) < δ. If N ⊂ C, then N x is a nonzero codeword of C of relative weight less than δ, contradicting Good. Thus in this case P(N ⊂ C|Good) = 0, which trivially satisfies the lemma as M ⊂ C if and only if N ⊂ C. If N is δ-smooth, then by Lemma A.2 with ξ = ε/(2r) and that r′ ≤ r, we bound ′

′

P(N ⊂ C) ≤ q −(1−ξ)(1−R)r n ≤ q (R−1)r n+εn/2 .

(A.4)

By Lemma 3.22, after increasing s0 if necessary, P(Good) ≥ 1 − on→∞ (1). Hence, P(N ⊂ C|Good) ≤

P(N ⊂ C) ′ ≤ q (R−1)r n+εn P(Good)

(A.5)

for sufficiently large n. Since M ⊂ C if and only if N ⊂ C, the lemma follows. We now prove Lemma 3.23, restated below for the reader’s convenience. Lemma 3.23 (RLDPCs containing local profiles). For any ε, R ∈ (0, 1), positive integer r, finite field Fq , there exists an s0 = s0 (ε, r, R, q) such that the following holds for all odd s > s0 and sufficiently large n. Let V = (V1 , . . . , Vn ) be an r-local profile and let U ∈ L(Frq ). For C = RLDPC(n, q, s, R), 1 −1 nϕV (U,R)+εn P(C contains (V, U )|Good) ≤ q where Good := ∆(C) ≥ hq (1 − R) . (3.45) 2 Proof. Let MV (U ) be the set of matrices M ∈ Fn×r with row-span exactly U such that Mi⋆ ∈ Vi q for every i ∈ [n]. If C contains (V, U ), then it contains some matrix M ∈ MV (U ). Every matrix M ∈ MV (U ) has rank r′ = dim U . Therefore, by Lemma A.3, ′

By Lemma 3.15, we have

P(M ⊂ C|Good) ≤ q (R−1)nr +εn .

(A.6)

|MV (U )| ≤ q n((1−R) dim U +ϕV (U,R)) .

(A.7)

Union bounding over all M ∈ MV (U ) and combining (A.6) and (A.7) gives ′

′

P(C contains (V, U )|Good) ≤ q n((1−R)r +ϕV (U,R)) q (R−1)nr +εn = q nϕV (U,R)+εn . This proves the lemma.

(A.8)

Record · ID 352980 · SHA-256 78913b740abb3757
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.