技術要約：曲線デコードの局所性と改善された近接ギャップ

1. 問題設定

本論文は、ランダム・アンサンブル（random ensembles）の誤り訂正符号における**近接ギャップ（proximity gaps）**を確立するという問題に取り組んでいる。近接ギャップは、対話型オラクル証明（IOP）や簡潔な非対話型ゼロ知識証明（SNARC）において極めて重要な特性である。直感的に言えば、符号 $C$ が次数 $\ell$ の曲線に対して近接ギャップを持つとは、任意の次数 $\ell$ の曲線 $u(x)$ に対して、「曲線上のすべての点が $C$ に近い」か、あるいは「点の $(1-\varepsilon)$ 割合が $C$ から遠い」かのいずれかが成立することを意味する。

Guruswami と Goyal による最近の研究 [GG25] は、エラー許容度 $\delta$ が $1-R$（$R$ は符号率）に近づくパラメータ設定において、部分空間デザイン符号（subspace design codes）（折り畳みリード・ソロモン符号や多重度符号を含む）に対する近最適に近い近接ギャップを確立した。具体的には、部分空間デザイン符号において、「近い」点の数 $\varepsilon q$ は以下のようにスケールする：
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
しかし、[GG25] が [BCDZ25, LMS25] のフレームワークを用いてこれらの結果をランダム・アンサンブル（ランダム線形符号、ランダムな評価点を持つランダム・リード・ソロモン符号、および 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 性質

著者らの主要な技術的革新は、**行スパン制約付き（row-span constrained）のバージョンへと局所座標線形（LCL: Local Coordinate-wise Linear）**フレームワークを拡張したことにある。

LCL フレームワークと課題

LCL フレームワーク（[LMS25] で導入）は、プロファイル $V$ によって定義される特定の線形制約を満たす行を持つ、符号の列をウィットネス行列の列とする「悪い」性質の行列 $M$ の存在によって、符号の「悪い」性質を特徴付ける。

• 障害： 曲線デコード可能性（curve-decodability）（近接ギャップを内包する性質）は、明らかに LCL 性質ではなかった。先行研究 [GG25] は、W-デコーディングと呼ばれる代理の性質を定義することでこれを回避したが、W-デコーディングの結果を曲線デコードに戻す際には、前述のようなパラメータの指数関数的な損失が生じた。

解決策：行スパン制約

著者らは、曲線デコーディングが、ウィットネス行列の**行スパン（row-span）**に対する制約を含むように LCL フレームワークを拡張することで、直接捉えられることを観察した。

1. 局所プロファイル（性質 A）： ウィットネス行列の列（符号語）は、周囲の次数 $\ell$ の曲線 $u(x)$ と、大きな集合上で一致しなければならない。これは標準的な局所プロファイル $V$ によって捉えられる。
2. 行スパン制約（性質 B）： 例の「悪さ」は、行列の $b$ 個の列がいかなる単一の次数 $\ell$ の符号語曲線にも乗らないことを要求する。これは行列構造に関するグローバルな制約である。
   • 著者らは、部分空間 $U$ が $(\ell, A, b)$ 曲線フリー（curve-free） であるとは、任意のベクトル $U$ の $b$ 個の座標がいかなる次数 $\ell$ の多項式上にも存在しないことであると定義する。
   • 彼らは、曲線デコーディングの失敗が、行スパン $U$ が曲線フリーであり、かつ行が局所プロファイル $V$ を満たすようなウィットネス行列 $M$ の存在と等価であることを示す。

LCL ファミリー $\mathcal{F}$ を、（プロファイル、行スパン）のペア $(V, U)$ の集合として定義することで、著者らは曲線デコーディングを行スパン制約付き LCL 性質として定式化した。これにより、中間ステップである W-デコーディングを経ることなく、[LMS25] および [BCDZ25] のメカニズムを直接適用することが可能となった。

3. 主な貢献

1. ブラックボックス転送

本論文は、部分空間デザイン符号からランダム・アンサンブルへの**ブラックボックス転送（black-box transference）**を確立している。著者らは、任意の行スパン制約付き LCL 性質について、ランダム線形符号（および関連するアンサンブル）がその性質を満たす閾値レートは、部分空間デザイン符号の閾値と実質的に同一であることを証明した。

• 含意： 部分空間デザイン符号に対する将来的なパラメータの改善は、自動的にランダム線形符号、ランダム・リード・ソロモン符号、およびランダム LDPC 符号に対する同様の改善をもたらす。

2. 改善された近接ギャップ境界

このフレームワークを曲線デコーディングに適用することで、著者らはランダム・アンサンブルに対して、以前は部分空間デザイン符号にのみ知られていた近最適の境界と一致する、改善された近接ギャップ境界を導出した。

• 結果： ランダム線形符号、ランダム・リード・ソロモン符号、および Gallager の LDPC アンサンブルについて、近接ギャップのパラメータは以下の通りとなる：
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  これにより、[GG25] に見られた $\ell$ に対する指数関数的な依存関係が排除された。

3. 等価定理

本論文は、異なる符号ファミリー間における行スパン制約付き LCL 性質の等価定理を証明している：

• ランダム線形符号とランダム・リード・ソロモン符号は、同じ閾値を共有する。
• ランダム LDPC 符号（Gallager のアンサンブル）は、符号が良好な距離を持つ限り（これは高確率で起こる）、ランダム線形符号と同じ閾値を共有する。

4. 主な結果

本論文は、これらの知見を定理 1.2（および定理 5.3, 5.6, 5.10 で詳述）として定式化している。レート $R$ および次数 $\ell$ のランダム符号 $C$ について：

• 高い確率で、$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)$$
• これらの結果は、より強い概念である**相関一致（Correlated Agreement: CA）および相互相関一致（Mutual Correlated Agreement: MCA）**についても、同じ改善されたパラメータとともに確立している。

具体的には、ランダム LDPC 符号については、Gallager のアンサンブルにおいて十分な大きさの奇数次数 $s$ に対して結果が成立し、境界の主要項はわずかに調整される（例：いくつかの定式化では $2n\ell(1-R)/\eta$ となるが、定数係数は改善可能である）。

5. 意義と主張

著者らは、本論文の意義を以下の 3 つの領域において主張している：

1. パラメータの最適化： ランダム・アンサンブルにおけるパラメータ劣化の問題を解決し、部分空間デザイン符号に対して既知であった近最適の境界と一致させた。これは、大きな $\ell$ を使用する WHIR や、ランダム・アンサンブルを使用する Blaze および Bolt といったプロトコルにとって特に重要である。
2. 理論的統一： 曲線デコーディングが自然な行スパン制約付き LCL 性質であることを示し、明示的な符号（部分空間デザイン）とランダム・アンサンブルの解析を単一のフレームワークの下で統一した。
3. 将来への備え： 「ブラックボックス」的な転送特性により、ランダム・アンサンブルの結果は静的なものではない。部分空間デザイン符号の理論が進展すれば、それに応じて自動的に改善される。

著者らは、ランダム・リード・ソロモン符号が近最適の近接ギャップに達することを示したものの、これらと同じ最適なパラメータを達成する明示的なリード・ソロモン符号（特定の評価点を持つもの）を特定することは依然として未解決問題であると明記している。この問いは、「近接賞（Proximity Prize）」および明示的なリスト復号に関連している。