Technische Samenvatting: Localiteit van Curve-Decoding en Verbeterde Proximity Gaps

1. Probleemstelling

Het artikel behandelt het probleem van het vaststellen van proximity gaps voor willekeurige ensembles van foutcorrigerende codes. Proximity gaps zijn een eigenschap die cruciaal zijn voor Interactive Oracle Proofs (IOPs) en Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Informeel bezit een code $C$ een proximity gap met betrekking tot een graad-$\ell$ curve $u(x)$ als, voor elke graad-$\ell$ curve $u(x)$, ofwel elk punt op de curve dicht bij $C$ ligt, ofwel een $(1-\varepsilon)$ fractie van de punten ver van $C$ verwijderd is.

Recent werk door Guruswami en Goyal [GG25] heeft bijna optimale proximity gaps vastgesteld voor subspace design codes (inclusclusief Folded Reed-Solomon en Multiplicity codes) met parameters waarbij de fouttolerantie $\delta$ de waarde $1-R$ nadert (waarbij $R$ de coderate is). Specifiek voor subspace design codes schaalt de bovengrens op het aantal "nabije" punten $\varepsilon q$ als:
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
Echter, wanneer [GG25] deze resultaten uitbreidde naar willekeurige ensembles (Random Linear Codes, Random Reed-Solomon codes met willekeurige evaluatiepunten, en Gallagers ensemble van LDPC-codes) met behulp van een framework uit [BCDZ25, LMS25], verslechterden de parameters. De resulterende bovengrens voor willekeurige ensembles bevatte een exponentiële afhankelijkheid van $\ell$:
$$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$$
Deze degradatie wordt significant wanneer $\ell$ groot is (bijv. $\ell = \Omega(\log n)$), wat de bounds onpraktisch maakt. De centrale vraag is of de optimale parameters die bereikt zijn voor subspace design codes, gematcht kunnen worden door deze willekeurige ensembles.

2. Methodologie: Row-Span Constrained LCL Eigenschappen

De belangrijkste technische innovatie van de auteurs is de uitbreiding van het Local Coordinate-wise Linear (LCL) framework naar een row-span constrained versie.

Het LCL Framework en de Uitdaging

Het LCL framework (geïntroduceerd in [LMS25]) karakteriseert "slechte" eigenschappen van codes door de existentie van een "getuige" matrix $M$ waarvan de kolommen codewoorden zijn en waarvan de rijen voldoen aan specifieke lineaire restricties gedefinieerd door een profiel $V$.

• De Obstakel: De eigenschap van curve-decodability (die proximity gaps impliceert) was niet overduidelijk een LCL-eigenschap. Voorgaand werk [GG25] omzeilde dit door een proxy-eigenschap genaamd W-decoding te definiëren. Hoewel W-decoding in het LCL-framework paste, leidde het vertalen van resultaten terug naar curve-decoding tot de eerder genoemde exponentiële verlies in parameters.

De Oplossing: Row-Span Constraints

De auteurs observeren dat curve-decodability direct gevangen kan worden door het LCL-framework uit te breiden met restricties op de row-span van de getuige-matrix.

1. Lokale Profiel (Eigenschap A): De kolommen van de getuige-matrix (codewoorden) moeten overeenstemmen met een ambient graad-$\ell$ curve $u(x)$ op een grote verzameling coördinaten. Dit wordt gevangen door een standaard lokaal profiel $V$.
2. Row-Span Constraint (Eigenschap B): De "slechtheid" van het voorbeeld vereist dat geen $b$ kolommen van de matrix op een enkele graad-$\ell$ codeword curve liggen. Dit is een globale restrictie op de matrixstructuur.
   • De auteurs definiëren een subspace $U$ als $(\ell, A, b)$ curve-free als geen $b$ coördinaten van een vector in $U$ op een graad-$\ell$ polynoom liggen.
   • Zij tonen aan dat het falen van curve-decodability equivalent is aan de existentie van een getuige-matrix $M$ waarbij de row-span $U$ curve-free is, en de rijen voldoen aan het lokale profiel $V$.

Door een LCL-familie $\mathcal{F}$ te definiëren als een collectie paren $(V, U)$ (profiel, row-span), brengen de auteurs curve-decodability onder als een row-span constrained LCL eigenschap. Dit stelt hen in staat om de machinerie van [LMS25] en [BCDZ25] direct toe te passen op curve-decoding zonder de tussenliggende W-decoding stap.

3. Belangrijkste Bijdragen

1. Black-Box Transference

Het artikel vestigt een black-box transference van subspace design codes naar willekeurige ensembles. De auteurs bewijzen dat voor elke row-span constrained LCL eigenschap, de drempelrate waarna willekeurige lineaire codes (en gerelateerde ensembles) de eigenschap voldoen, essentieel identiek is aan de drempel voor subspace design codes.

• Implicatie: Elke toekomstige verbetering in de parameters voor subspace design codes zal automatisch vergelijkbare verbeteringen opleveren voor willekeurige lineaire codes, random Reed-Solomon codes en random LDPC-codes.

2. Verbeterde Proximity Gap Bounds

Door dit framework toe te passen op curve-decoding, leiden de auteurs verbeterde proximity gap bounds af voor willekeurige ensembles die de optimale bounds matchen die voorheen alleen bekend waren voor subspace design codes.

• Resultaat: Voor Random Linear Codes, Random Reed-Solomon codes en Gallagers LDPC-ensemble zijn de proximity gap parameters nu:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  Dit elimineert de exponentiële afhankelijkheid van $\ell$ die aanwezig was in [GG25].

3. Equivalentie Theorems

Het artikel bewijst equivalentie-theorema's voor de row-span constrained LCL eigenschappen over verschillende code-families:

• Random Linear Codes en Random Reed-Solomon codes delen dezelfde drempels.
• Random LDPC codes (Gallagers ensemble) delen dezelfde drempels als Random Linear Codes, mits de code een goede afstand heeft (wat met hoge waarschijnlijkheid voorkomt).

4. Hoofdresultaten

Het artikel formaliseert deze bevindingen in Theorem 1.2 (en gedetailleerd in Theorems 5.3, 5.6, en 5.10). Voor een willekeurige code $C$ (Linear, Reed-Solomon, of LDPC) van rate $R$ en graad $\ell$:

• Met hoge waarschijnlijkheid vertoont $C$ $(\ell, 1-R-2\eta, \varepsilon)$ proximity gaps.
• De conditie op $\varepsilon$ is:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
• De resultaten vestigen ook sterkere begrippen: Correlated Agreement (CA) en Mutual Correlated Agreement (MCA) met dezelfde verbeterde parameters.

Specifiek voor Random LDPC codes geldt het resultaat voor voldoende grote oneven graad $s$ in het Gallager-ensemble, waarbij de leidende term in de bound licht wordt aangepast (bijv. $2n\ell(1-R)/\eta$ in sommige formuleringen, hoewel de constante factor kan worden verbeterd).

5. Betekenis en Claims

De auteurs claimen significantie op drie belangrijke gebieden:

1. Parameter Optimalisatie: Het lost het probleem van de parameter-degradatie voor willekeurige ensembles op, waarbij de bijna optimale bounds van subspace design codes worden geëvenaard. Dit is bijzonder relevant voor toepassingen zoals WHIR (die grote $\ell$ gebruikt) en protocollen zoals Blaze en Bolt (die willekeurige ensembles gebruiken).
2. Theoretische Unificatie: Het demonstreert dat curve-decoding een natuurlijke row-span constrained LCL eigenschap is, waardoor de analyse van expliciete codes (subspace designs) en willekeurige ensembles onder één enkel framework wordt verenigd.
3. Toekomstbestendigheid: De "black-box" aard van de transference betekent dat de resultaten voor willekeurige ensembles niet statisch zijn; ze zullen automatisch verbeteren naarmate de theorie van subspace design codes vordert.

De auteurs merken expliciet op dat hoewel hun resultaten aantonen dat willekeurige Reed-Solomon codes bijna optimale proximity gaps bereiken, het een open probleem blijft om expliciete Reed-Solomon codes (met specifieke evaluatiepunten) te identificeren die deze zelfde optimale parameters bereiken, een vraagstuk dat gelinkt is aan de "Proximity Prize" en expliciete list-decoding.