List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

Resumen Técnico: Los contraejemplos de decodificación de lista producen cotas inferiores en el error de acuerdo correlacionado mutuo

1. Planteamiento del problema

El artículo aborda la cuestión fundamental del Acuerdo Correlacionado Mutuo (MCA) en el contexto de los códigos lineales. El MCA es una propiedad crítica para la solidez de las pruebas de proximidad por lotes (batched proximity testing), un mecanismo utilizado en argumentos de conocimiento no interactivos sucintos (SNARKs) e Interacción de Pruebas de Proximidad (IOPPs).

Específicamente, el MCA investiga si una combinación lineal aleatoria de palabras recibidas puede crear espuriosamente un dominio de acuerdo grande con un código que no es explicado por la estructura de acuerdo correlacionado de las palabras originales. Aunque existen resultados positivos (brechas de proximidad) para varias familias de códigos hasta ciertos límites, existe la necesidad de comprender las limitaciones: específicamente, qué tan grande puede ser la probabilidad de error (la probabilidad de un punto de combinación "malo") cuando un código falla en ser decodificable de lista.

El núcleo del problema es establecer un vínculo constructivo entre los contraejemplos de decodificación de lista (palabras recibidas con más de $L$ palabras de código dentro de una cierta distancia) y las cotas inferiores en el error de MCA. Trabajos previos han mostrado conexiones entre la decodificabilidad de lista y el acuerdo correlacionado, pero este artículo tiene como objetivo proporcionar un método general y constructivo para derivar cotas inferiores explícitas en el error de MCA a partir de los fallos de decodificación de lista, preservando las propiedades estructurales de la familia de códigos.

2. Metodología

Los autores emplean un enfoque constructivo centrado en una técnica de "perforación y anexión" (puncture-and-append). La metodología procede en tres etapas lógicas:

1. Extensión fuera del dominio:
   Partiendo de un código lineal $C$ que no es $(p, L)$-decodificable de lista, los autores identifican una palabra recibida $y$ y $L+1$ palabras de código distintas $c_1, \dots, c_{L+1}$ dentro de la distancia $p$. Construyen un código extendido $C'$ de longitud $n+1$ anexando una nueva coordenada.

   • Se definen dos palabras, $\pi_0$ y $\pi_1$, sobre el dominio extendido. $\pi_0$ transporta la palabra recibida original $y$ (con un cero anexado), mientras que $\pi_1$ es cero en el dominio original y 1 en la nueva coordenada.
   • Los autores utilizan una cota de colisión algebraico-lineal (Lema 1) para seleccionar un vector $a$ (que define la columna anexada de la matriz generadora) tal que los valores $m_i \cdot a^T$ (donde $m_i$ son los vectores de mensaje de las palabras de código cercanas) contengan un gran número de valores distintos.
   • Cada valor distinto corresponde a un punto de combinación "malo" $\alpha$ donde la combinación lineal $\pi_0 + \alpha \pi_1$ concuerda con una palabra de código extendida en un conjunto grande, pero no posee acuerdo correlacionado con el par original.

2. Perforación y anexión (Preservación de la longitud):
   Para asegurar que el código resultante tenga la misma longitud de bloque $n$ que el original, los autores perforan (eliminan) una coordenada del código original antes de anexar la nueva.

   • Demuestran que si el código original no es $(p, L)$-decodificable de lista, existe una coordenada cuya eliminación preserva la dimensión y la propiedad de no ser decodificable de lista (con un ligero ajuste al parámetro de distancia relativa).
   • El procedimiento de "perforar uno, anexar uno" produce un código $C'$ de longitud $n$ que retiene el gran conjunto de puntos de combinación malos derivados en el paso de extensión.

3. Generalización de preservación de estructura:
   Para aplicar esto a familias de códigos específicas (como los códigos de Reed-Solomon o de Geometría Algebraica), los autores generalizan la construcción a familias de códigos indexados.

   • En lugar de elegir un vector arbitrario para la columna anexada, seleccionan un índice de un conjunto finito $\Omega$ mediante un mapa $v: \Omega \to \mathbb{F}_q^k$.
   • Introducen una cota de colisión $\lambda$ sobre el conjunto de índices, asegurando que los mensajes distintos no colisionen con demasiada frecuencia en los índices disponibles. Esto permite que la construcción permanezca dentro de la misma familia de códigos (por ejemplo, cambiando solo un punto de evaluación en un código AG) mientras preserva la cota inferior en el error de MCA.

3. Contribuciones clave y resultados

Teorema 1 (Códigos lineales generales):
El artículo establece que si un código lineal $C$ de dimensión $k$ y longitud $n$ no es $(p, L)$-decodificable de lista (con $p < \Delta(C) - 1/n$), existe un código relacionado $C'$ de la misma longitud y dimensión tal que:
$$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$$
Además, la distancia mínima relativa de $C'$ satisface $\Delta(C') \geq \Delta(C) - 1/n$. Si las palabras de peso mínimo de $C$ no cubren todas las coordenadas, la distancia puede preservarse exactamente ($\Delta(C') \geq \Delta(C)$). La construcción es explícita, produciendo tanto el código $C'$ como un par de palabras que evidencian el error.

Teorema 2 (Versión de preservación de estructura):
Para familias de códigos indexadas por un conjunto $\Omega$ con un mapa de columnas $v$, asumiendo una cota de colisión $\lambda$ (donde cualquier vector no nulo $u$ tiene como máximo $\lambda$ índices $\omega$ tales que $u \cdot v(\omega)^T = 0$), la construcción produce un código $C'$ dentro de la misma familia.

• $C'$ difiere de $C$ en como máximo un índice de coordenada.
• La cota inferior del error de MCA es:
  $$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)N}{N+L\lambda} \right\rceil$$
  donde $N = |\Omega|$.

Corolarios para familias de códigos específicas:

• Códigos de Geometría Algebraica (AG): Al establecer $\Omega$ como el conjunto de lugares racionales y $\lambda = \deg(G)$, los autores muestran que si un código AG no es decodificable de lista, se puede modificar el divisor de evaluación $D$ cambiando a lo sumo un lugar para obtener un código con la cota inferior de error de MCA especificada. El código resultante permanece sobre el mismo campo de funciones y espacio de Riemann-Roch.
• Códigos de Reed-Solomon (RS): Como una especialización donde $\Omega = \mathbb{F}_q$ y $\lambda = k-1$ (grado de los polinomios), el resultado arroja una cota inferior de error de $\frac{1}{q} \lceil \frac{(L+1)q}{q+L(k-1)} \rceil$. Esto confirma que los fallos de decodificación de lista en los códigos RS implican directamente errores de MCA significativos.

4. Significado y afirmaciones

El artículo afirma proporcionar un método constructivo y general para traducir los contraejemplos de decodificación de lista en cotas inferiores sobre el error de acuerdo correlacionado mutuo.

• Contraste con trabajos previos: Los autores señalan que trabajos anteriores (por ejemplo, Ben-Sasson et al., Crites y Stewart) derivaron cotas inferiores similares para los códigos de Reed-Solomon utilizando operaciones específicas como la división por $X-\beta$, lo cual inherentemente desplazaba el grado del código (de $k$ a $k+1$). En contraste, la construcción de este artículo preserva la dimensión del código y la longitud de bloque, y se aplica a códigos lineales arbitrarios sin requerir desplazamientos de grado.
• Integridad estructural: Una contribución significativa es la capacidad de mantener la familia estructural del código (por ejemplo, manteniendo un código AG como un código AG sobre el mismo espacio) modificando únicamente un solo índice de coordenada. Esto es crucial para aplicaciones donde la familia del código está fijada por la estructura algebraica subyacente.
• Implicaciones de solidez: Al construir explícitamente códigos con un alto error de MCA a partir de fallos de decodificación de lista, el artículo cuantifica los límites de la solidez en las pruebas de proximidad por lotes. Demuestra que si un código no es decodificable de lista, no se puede garantizar que las combinaciones lineales aleatorias permanecerán lejos del código con alta probabilidad; específicamente, la probabilidad de error está acotada inferiormente por la fórmula derivada.

El trabajo no propone nuevos protocolos experimentales ni aplicaciones futuras más allá de instanciar el principio para los códigos AG y RS. Su principal contribución es teórica: establecer un puente riguroso y constructivo entre las propiedades de decodificación de lista y las cotas de error de acuerdo correlacionado mutuo.