Résumé technique : Localité du décodage de courbes et amélioration des écarts de proximité

1. Énoncé du problème

Le papier traite du problème de l'établissement d'écarts de proximité (proximity gaps) pour les ensembles aléatoires de codes correcteurs d'erreurs. Les écarts de proximité sont une propriété cruciale pour les preuves à oracle interactives (IOP) et les arguments de connaissance nulle non interactifs succincts (SNARK). Informellement, un code $C$ présente un écart de proximité par rapport à des courbes de degré-$\ell$ si, pour toute courbe $u(x)$ de degré-$\ell$, soit chaque point de la courbe est proche de $C$, soit une fraction $(1-\varepsilon)$ des points est loin de $C$.

Des travaux récents par Guruswami et Goyal [GG25] ont établi des écarts de proximité quasi optimaux pour les codes de conception de sous-espaces (subspace design codes, incluant les codes de Reed-Solomon repliés et les codes de multiplicité) avec des paramètres où la tolérance d'erreur $\delta$ approche $1-R$ (où $R$ est le taux du code). Spécifiquement, pour les codes de conception de sous-espaces, la borne sur le nombre de points « proches » $\varepsilon q$ suit l'échelle :
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
Cependant, lorsque [GG25] a étendu ces résultats aux ensembles aléatoires (Codes Linéaires Aléatoires, codes de Reed-Solomon aléatoires avec points d'évaluation aléatoires, et l'ensemble de Gallager pour les codes LDPC) en utilisant un cadre issu de [BCDZ25, LMS25], les paramètres se sont dégradés. La borne résultante pour les ensembles aléatoires incluait une dépendance exponentielle en $\ell$ :
$$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$$
Cette dégradation devient significative lorsque $\ell$ est grand (par exemple, $\ell = \Omega(\log n)$), rendant les bornes peu pratiques. La question centrale est de savoir si les paramètres optimaux atteints pour les codes de conception de sous-espaces peuvent être égalés par ces ensembles aléatoires.

2. Méthodologie : Propriétés LCL contraintes par l'espace engendré par les lignes

La principale innovation technique des auteurs est l'extension du cadre LCL (Local Coordinate-wise Linear) à une version contrainte par l'espace engendré par les lignes (row-span constrained).

Le cadre LCL et le défi

Le cadre LCL (introduit dans [LMS25]) caractérise les propriétés « mauvaises » des codes par l'existence d'une matrice témoin $M$ dont les colonnes sont des mots de code et dont les lignes satisfont des contraintes linéaires spécifiques définies par un profil $V$.

• L'obstacle : La propriété de décodabilité de courbe (qui implique des écarts de proximité) n'était pas évidemment une propriété LCL. Des travaux précédents [GG25] ont contourné cela en définissant une propriété de substitution appelée décodage-W. Bien que le décodage-W s'insère dans le cadre LCL, la traduction des résultats vers la décodabilité de courbe entraînait la perte exponentielle de paramètres mentionnée précédemment.

La solution : Contraintes sur l'espace engendré par les lignes

Les auteurs observent que la décodabilité de courbe peut être capturée directement en étendant le cadre LCL pour inclure des contraintes sur l'espace engendré par les lignes (row-span) de la matrice témoin.

1. Profil local (Propriété A) : Les colonnes de la matrice témoin (mots de code) doivent concorder avec une courbe ambiante de degré-$\ell$ $u(x)$ sur un grand ensemble de coordonnées. Cela est capturé par un profil local standard $V$.
2. Contrainte de l'espace engendré par les lignes (Propriété B) : La « malpropreté » de l'exemple exige qu'aucune $b$ colonnes de la matrice ne reposent sur une seule courbe de mot de code de degré-$\ell$. Il s'agit d'une contrainte globale sur la structure de la matrice.
   • Les auteurs définissent un sous-espace $U$ comme étant sans courbe $(\ell, A, b)$ si aucune $b$ coordonnées de tout vecteur de $U$ ne reposent sur un polynôme de degré $\ell$.
   • Ils montrent que l'échec de la décodabilité de courbe est équivalent à l'existence d'une matrice témoin $M$ où l'espace engendré par les lignes $U$ est sans courbe, et où les lignes satisfont le profil local $V$.

En définissant une famille LCL $\mathcal{F}$ comme une collection de paires $(V, U)$ (profil, espace engendré par les lignes), les auteurs présentent la décodabilité de courbe comme une propriété LCL contrainte par l'espace engendré par les lignes. Cela leur permet d'appliquer directement la machinerie de [LMS25] et [BCDZ25] à la décodabilité de courbe sans passer par l'étape intermédiaire du décodage-W.

3. Contributions clés

1. Transfert en boîte noire

Le papier établit un transfert en boîte noire (black-box transference) des codes de conception de sous-espaces vers les ensembles aléatoires. Les auteurs prouvent que pour toute propriété LCL contrainte par l'espace engendré par les lignes, le taux seuil auquel les codes linéaires aléatoires (et les ensembles apparentés) satisfont la propriété est essentiellement identique au seuil des codes de conception de sous-espaces.

• Implication : Toute amélioration future des paramètres pour les codes de conception de sous-espaces produira automatiquement des améliorations analogues pour les codes linéaires aléatoires, les codes de Reed-Solomon aléatoires et les codes LDPC aléatoires.

2. Bornes améliorées de l'écart de proximité

En appliquant ce cadre à la décodabilité de courbe, les auteurs dérivent des bornes d'écart de proximité améliorées pour les ensembles aléatoires qui correspondent aux bornes optimales connues auparavant uniquement pour les codes de conception de sous-espaces.

• Résultat : Pour les codes Linéaires Aléatoires, les codes de Reed-Solomon aléatoires et l'ensemble de Gallager pour les codes LDPC, les paramètres de l'écart de proximité sont désormais :
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  Cela élimine la dépendance exponentielle en $\ell$ trouvée dans [GG25].

3. Théorèmes d'équivalence

Le papier prouve des théorèmes d'équivalence pour les propriétés LCL contraintes par l'espace engendré par les lignes à travers différentes familles de codes :

• Les codes Linéaires Aléatoires et les codes de Reed-Solomon Aléatoires partagent les mêmes seuils.
• Les codes LDPC aléatoires (ensemble de Gallager) partagent les mêmes seuils que les codes Linéaires Aléatoires, à condition que le code ait une bonne distance (ce qui arrive avec une probabilité élevée).

4. Résultats principaux

Le papier formalise ces conclusions dans le Théorème 1.2 (et en détail dans les Théorèmes 5.3, 5.6 et 5.10). Pour un code aléatoire $C$ (Linéaire, Reed-Solomon ou LDPC) de taux $R$ et de degré $\ell$ :

• Avec une probabilité élevée, $C$ présente des écarts de proximité $(\ell, 1-R-2\eta, \varepsilon)$.
• La condition sur $\varepsilon$ est :
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
• Les résultats établissent également des notions plus fortes : l'Accord Corrélationnel (CA) et l'Accord Corrélationnel Mutuel (MCA) avec les mêmes paramètres améliorés.

Spécifiquement, pour les codes LDPC aléatoires, le résultat est valable pour un degré impair $s$ suffisamment grand dans l'ensemble de Gallager, avec le terme principal de la borne légèrement ajusté (par exemple, $2n\ell(1-R)/\eta$ dans certaines formulations, bien que le facteur constant puisse être amélioré).

5. Signification et affirmations

Le papier revendique une importance dans trois domaines principaux :

1. Optimisation des paramètres : Il résout le problème de la dégradation des paramètres pour les ensembles aléatoires, égalant les bornes quasi optimales connues uniquement pour les codes de conception de sous-espaces. C'est particulièrement pertinent pour des applications comme WHIR (qui utilise un $\ell$ grand) et des protocoles comme Blaze et Bolt (qui utilisent des ensembles aléatoires).
2. Unification théorique : Il démontre que la décodabilité de courbe est une propriété LCL naturelle contrainte par l'espace engendré par les lignes, unifiant l'analyse des codes explicites (conceptions de sous-espaces) et des ensembles aléatoires sous un cadre unique.
3. Pérennité : La nature « boîte noire » du transfert signifie que les résultats pour les ensembles aléatoires ne sont pas statiques ; ils s'amélioreront automatiquement à mesure que la théorie des codes de conception de sous-espaces progressera.

Les auteurs notent explicitement que bien que leurs résultats montrent que les codes de Reed-Solomon aléatoires atteignent des écarts de proximité quasi optimaux, il reste un problème ouvert d'identifier des codes de Reed-Solomon explicites (avec des points d'évaluation spécifiques) qui atteignent ces mêmes paramètres optimaux, une question liée au « Proximity Prize » et au décodage de liste explicite.