技术摘要：曲线解码的局部性与改进的邻近间隙

1. 问题陈述

本文研究了为随机纠错码系综建立**邻近间隙（proximity gaps）**的问题。邻近间隙是交互式预言证明（IOPs）和简洁非交互零知识证明（SNARKs）中至关重要的属性。直观地说，如果一个码 $C$ 对于度数为 $\ell$ 的曲线具有邻近间隙，则意味着对于任何度数为 $\ell$ 的曲线 $u(x)$，要么曲线上所有的点都接近 $C$，要么有 $(1-\varepsilon)$ 比例的点远离 $C$。

Guruswami 和 Goyal [GG25] 最近的研究为子空间设计码（包括折叠 Reed-Solomon 码和多重性码）在误差容限 $\delta$ 趋于 $1-R$（其中 $R$ 是码率）的参数范围内，建立了近乎最优的邻近间隙。具体而言，对于子空间设计码，“接近”点的数量 $\varepsilon q$ 的界限为：
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
然而，当 [GG25] 使用来自 [BCDZ25, LMS25] 的框架将这些结果扩展到随机系综（随机线性码、带有随机求值点的随机 Reed-Solomon 码以及 Gallager 的 LDPC 码系综）时，参数发生了退化。得到的针对随机系综的界限包含了对 $\ell$ 的指数依赖：
$$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$$
当 $\ell$ 较大时（例如 $\ell = \Omega(\log n)$），这种退化变得非常显著，使得这些界限在实际应用中变得不切实际。核心问题在于：子空间设计码所达到的最优参数是否可以被这些随机系综所匹配。

2. 方法论：行跨度受限的 LCL 性质

作者的主要技术创新是将**局部坐标逐行线性（Local Coordinate-wise Linear, LCL）框架扩展到了一个行跨度受限（row-span constrained）**的版本。

LCL 框架与挑战

LCL 框架（由 [LMS25] 引入）通过存在一个“见证”矩阵 $M$ 来刻画码的“坏”属性，该矩阵的列是码字，且其行满足由剖面（profile）$V$ 定义的特定线性约束。

• 障碍： 曲线可解码性（implying proximity gaps）这一属性并不明显是一个 LCL 属性。之前的研究 [GG25] 通过定义一个称为 W-解码 的代理属性来规避这个问题。虽然 W-解码符合 LCL 框架，但将结果转回曲线可解码性时，会产生前述的参数指数级损失。

解决方案：行跨度约束

作者观察到，通过将 LCL 框架扩展到包含对见证矩阵**行跨度（row-span）**约束的形式，可以直接捕捉曲线可解码性。

1. 局部剖面（属性 A）： 见证矩阵的列（码字）必须在大量的坐标上与环境度数为 $\ell$ 的曲线 $u(x)$ 一致。这由标准的局部剖面 $V$ 来捕捉。
2. 行跨度约束（属性 B）： 示例的“坏”特征要求没有任何 $b$ 个列位于单个度数为 $\ell$ 的码字曲线上。这是一个关于矩阵结构的全局约束。
   • 作者定义一个子空间 $U$ 是 $(\ell, A, b)$ 无曲线的（curve-free），如果 $U$ 中任何向量的 $b$ 个坐标都不落在度数为 $\ell$ 的多项式上。
   • 他们证明了曲线可解码性的失效等价于存在一个见证矩阵 $M$，其中行跨度 $U$ 是无曲线的，且行满足局部剖面 $V$。

通过将 LCL 系列 $\mathcal{F}$ 定义为对 $(V, U)$（剖面与行跨度）的集合，作者将曲线可解码性转化为一个行跨度受限的 LCL 属性。这使他们能够直接应用 [LMS25] 和 [BCDZ25] 的理论工具来处理曲线可解码性，而无需经过中间的 W-解码步骤。

3. 核心贡献

1. 黑盒传递（Black-Box Transference）

本文建立了从子空间设计码到随机系综的黑盒传递。作者证明，对于任何行跨度受限的 LCL 属性，随机线性码（及相关系综）满足该属性的阈值速率，本质上与子空间设计码的阈值是一致的。

• 意义： 任何未来对子空间设计码参数的改进，都将自动带来对随机线性码、随机 Reed-Solomon 码和随机 LDPC 码的类似改进。

2. 改进的邻近间隙界限

通过将此框架应用于曲线解码，作者为随机系综推导出了改进的邻近间隙界限，这些界限与此前仅在子空间设计码中已知的最优界限相匹配。

• 结果： 对于随机线性码、随机 Reed-Solomon 码和 Gallager 的 LDPC 系综，其邻近间隙参数现在为：
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  这消除了 [GG25] 中存在的对 $\ell$ 的指数依赖。

3. 等价性定理

论文证明了不同代码族之间行跨度受限 LCL 属性的等价性定理：

• 随机线性码和随机 Reed-Solomon 码具有相同的阈值。
• 随机 LDPC 码（Gallager 系综）在具有良好距离（这会以高概率发生）的前提下，与随机线性码具有相同的阈值。

4. 主要结果

论文在 Theorem 1.2（并在 Theorem 5.3, 5.6, 5.10 中详细阐述）中形式化了这些发现。对于一个率 $R$、度数 $\ell$ 的随机码 $C$（线性、Reed-Solomon 或 LDPC）：

• 以高概率，$C$ 展现出 $(\ell, 1-R-2\eta, \varepsilon)$ 邻近间隙。
• 对 $\varepsilon$ 的条件是：
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
• 这些结果还建立了更强的概念：相关一致性（CA）和相互相关一致性（MCA），并具有相同的改进参数。

具体而言，对于随机 LDPC 码，该结果在 Gallager 系综中对于足够大的奇数度 $s$ 成立，其界限的主项略有调整（例如在某些表述中为 $2n\ell(1-R)/\eta$，尽管常数因子可以进一步优化）。

5. 意义与主张

作者声称其研究在三个领域具有重要意义：

1. 参数优化： 它解决了随机系综的参数退化问题，使其达到了与子空间设计码近乎最优的界限。这对于像 WHIR（使用大 $\ell$）以及像 Blaze 和 Bolt（使用随机系综）这类协议的应用尤为重要。
2. 理论统一： 它证明了曲线解码是一个自然的行跨度受限 LCL 属性，从而将显式码（子空间设计）和随机系综的分析统一在一个框架之下。
3. 面向未来： 这种传递的“黑盒”性质意味着随机系综的结果并非静止不变；随着子空间设计码理论的发展，其结果将自动提升。

作者明确指出，虽然他们的结果表明随机 Reed-Solomon 码达到了近乎最优的邻近间隙，但识别出能达到这些相同最优参数的显式 Reed-Solomon 码（具有特定的求值点）仍然是一个开放问题，这与“邻近奖（Proximity Prize）”和显式列表解码有关。