Resumo Técnico: Localidade de Decodificação de Curvas e Lacunas de Proximidade Melhoradas

1. Definição do Problema

O artigo aborda o problema de estabelecer lacunas de proximidade (proximity gaps) para conjuntos aleatórios de códigos de correção de erros. As lacunas de proximidade são uma propriedade crucial para Provas Oraculares Interativas (IOPs) e Argumentos Não Interativos de Conhecimento Zero Sucintos (SNARKs). Informalmente, um código $C$ exibe uma lacuna de proximidade em relação a curvas de grau-$\ell$ se, para qualquer curva $u(x)$ de grau-$\ell$, ou cada ponto na curva está próximo de $C$, ou uma fração $(1-\varepsilon)$ dos pontos está longe de $C$.

Trabalhos recentes de Guruswami e Goyal [GG25] estabeleceram lacunas de proximidade quase ótimas para códigos de design de subespaço (incluindo Reed-Solomon Dobrados e códigos de Multiplicidade) com parâmetros onde a tolerância de erro $\delta$ se aproxima de $1-R$ (onde $R$ é a taxa do código). Especificamente, para códigos de design de subespaço, o limite para o número de pontos "próximos" $\varepsilon q$ escala como:
$$\varepsilon q \geq \frac{n\ell}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
No entanto, quando [GG25] estendeu esses resultados para conjuntos aleatórios (Códigos Lineares Aleatórios, Códigos Reed-Solomon Aleatórios com pontos de avaliação aleatórios e o conjunto de LDPC de Gallager) usando um framework de [BCDZ25, LMS25], os parâmetros degradaram. O limite resultante para conjuntos aleatórios incluiu uma dependência exponencial em $\ell$:
$$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + \left(\frac{\ell}{\eta^2}\right)^{O(\ell)}$$
Essa degradação torna-se significativa quando $\ell$ é grande (por exemplo, $\ell = \Omega(\log n)$), tornando os limites impraticáveis. A questão central é se os parâmetros ótimos alcançados para códigos de design de subespaço podem ser correspondidos por esses conjuntos aleatórios.

2. Metodologia: Propriedades LCL com Restrição de Espaço Vetorial de Linhas

A principal inovação técnica dos autores é a extensão do framework Local Coordinate-wise Linear (LCL) para uma versão com restrição de espaço vetorial de linhas (row-span constrained).

O Framework LCL e o Desafio

O framework LCL (introduzido em [LMS25]) caracteriza propriedades "ruins" de códigos pela existência de uma matriz testemunha $M$ cujas colunas são palavras-código e cujas linhas satisfazem restrições lineares específicas definidas por um perfil $V$.

• O Obstáculo: A propriedade de decodificabilidade de curva (que implica lacunas de proximidade) não era obviamente uma propriedade LCL. Trabalhos anteriores [GG25] contornaram isso definindo uma propriedade substituta chamada W-decodificação. Embora a W-decodificação se ajustasse ao framework LCL, a tradução dos resultados de volta para a decodificação de curva incorria na mencionada perda exponencial de parâmetros.

A Solução: Restrições de Espaço Vetorial de Linhas

Os autores observam que a decodificabilidade de curva pode ser capturada diretamente estendendo o framework LCL para incluir restrições no espaço vetorial de linhas (row-span) da matriz testemunha.

1. Perfil Local (Propriedade A): As colunas da matriz testemunha (palavras-código) devem concordar com uma curva ambiente de grau-$\ell$ $u(x)$ em um grande conjunto de coordenadas. Isso é capturado por um perfil local padrão $V$.
2. Restrição de Espaço Vetorial de Linhas (Propriedade B): A "maldade" do exemplo exige que nenhuma sequência de $b$ colunas da matriz esteja sobre uma única curva de palavra-código de grau-$\ell$. Esta é uma restrição global na estrutura da matriz.
   • Os autores definem um subespaço $U$ como sendo $(\ell, A, b)$ livre de curvas se nenhuma sequência de $b$ coordenadas de qualquer vetor em $U$ estiver sobre um polinômio de grau-$\ell$.
   • Eles mostram que a falha da decodificabilidade de curva é equivalente à existência de uma matriz testemunha $M$ onde o espaço vetorial de linhas $U$ é livre de curvas, e as linhas satisfazem o perfil local $V$.

Ao definir uma família LCL $\mathcal{F}$ como uma coleção de pares $(V, U)$ (perfil, espaço vetorial de linhas), os autores formulam a decodificabilidade de curva como uma propriedade LCL com restrição de espaço vetorial de linhas. Isso permite que eles apliquem diretamente a maquinaria de [LMS25] e [BCDZ25] à decodificação de curva sem a etapa intermediária de W-decodificação.

3. Principais Contribuições

1. Transferência Black-Box

O artigo estabelece uma transferência black-box de códigos de design de subespaço para conjuntos aleatórios. Os autores provam que, para qualquer propriedade LCL com restrição de espaço vetorial de linhas, a taxa de limiar na qual códigos lineares aleatórios (e conjuntos relacionados) satisfazem a propriedade é essencialmente idêntica à taxa para códigos de design de subespaço.

• Implicação: Qualquer melhoria futura nos parâmetros para códigos de design de subespaço produzirá automaticamente melhorias análogas para códigos lineares aleatórios, códigos Reed-Solomon aleatórios e códigos LDPC aleatórios.

2. Limites de Lacuna de Proximidade Melhorados

Ao aplicar este framework à decodificação de curva, os autores derivam limites de lacuna de proximidade melhorados para conjuntos aleatórios que correspondem aos limites ótimos anteriormente conhecidos apenas para códigos de design de subespaço.

• Resultado: Para Códigos Lineares Aleatórios, Códigos Reed-Solomon Aleatórios e o conjunto de Gallager de LDPC, os parâmetros da lacuna de proximidade são agora:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
  Isso elimina a dependência exponencial de $\ell$ encontrada em [GG25].

3. Teoremas de Equivalência

O artigo prova teoremas de equivalência para as propriedades LCL com restrição de espaço vetorial de linhas entre diferentes famílias de códigos:

• Códigos Lineares Aleatórios e Códigos Reed-Solomon Aleatórios compartilham os mesmos limiares.
• Códigos LDPC aleatórios (conjunto de Gallager) compartilham os mesmos limiares que Códigos Lineares Aleatórios, desde que o código tenha boa distância (o que ocorre com alta probabilidade).

4. Principais Resultados

O artigo formaliza essas descobertas no Teorema 1.2 (e detalha nos Teoremas 5.3, 5.6 e 5.10). Para um código aleatório $C$ (Linear, Reed-Solomon ou LDPC) de taxa $R$ e grau $\ell$:

• Com alta probabilidade, $C$ exibe lacunas de proximidade $(\ell, 1-R-2\eta, \varepsilon)$.
• A condição sobre $\varepsilon$ é:
  $$\varepsilon q \geq \frac{n\ell(1-R)}{\eta} + O\left(\frac{\ell^2}{\eta^3}\right)$$
• Os resultados também estabelecem noções mais fortes: Acordo Correlacionado (CA) e Acordo Correlacionado Mútuo (MCA) com os mesmos parâmetros melhorados.

Especificamente, para códigos LDPC aleatórios, o resultado é válido para um grau ímpar $s$ suficientemente grande no conjunto de Gallager, com o termo principal no limite ligeiramente ajustado (por exemplo, $2n\ell(1-R)/\eta$ em algumas formulações, embora o fator constante possa ser melhorado).

5. Significância e Alegações

O artigo alega significância em três áreas principais:

1. Otimização de Parâmetros: Ele resolve o problema da degradação de parâmetros para conjuntos aleatórios, correspondendo aos limites quase ótimos de códigos de design de subespaço. Isso é particularmente relevante para aplicações como WHIR (que usa $\ell$ grande) e protocolos como Blaze e Bolt (que usam conjuntos aleatórios).
2. Unificação Teórica: Demonstra que a decodificação de curva é uma propriedade LCL natural com restrição de espaço vetorial de linhas, unificando a análise de códigos explícitos (designs de subespaço) e conjuntos aleatórios sob um único framework.
3. Preparação para o Futuro: A natureza "black-box" da transferência significa que os resultados para conjuntos aleatórios não são estáticos; eles melhorarão automaticamente à medida que a teoria dos códigos de design de subespaço avançar.

Os autores observam explicitamente que, embora seus resultados mostrem que códigos Reed-Solomon aleatórios atingem lacunas de proximidade quase ótimas, permanece um problema aberto identificar códigos Reed-Solomon explícitos (com pontos de avaliação específicos) que alcancem esses mesmos parâmetros ótimos, uma questão ligada ao "Prêmio de Proximidade" e à decodificação de lista explícita.