Uso de códigos de corrección de errores en teoría

¿Cuáles son las aplicaciones de los códigos de corrección de errores en teoría además de la corrección de errores en sí? Conozco tres aplicaciones: el teorema de Goldreich-Levin sobre el bit de núcleo duro, la construcción del extractor de Trevisan y la amplificación de la dureza de la función booleana (por Sudán-Trevisan-Vadhan).

¿Cuáles son otras aplicaciones 'serias' o 'recreativas' de códigos de corrección de errores?

UPD: una divertida aplicación de decodificación de listas de códigos Reed-Solomon es una solución para una variación particular del juego de 20 preguntas (y otra variación más directa).

Aquí hay una aplicación directa en la complejidad de la comunicación (que veo que ahora también se describe en un comentario de Andy Drucker en su blog ) fuera del contexto de la aleatorización:

$x$$y$$x$$y$$\epsilon n$$\epsilon$$a$$b$$cn$$c<1$$\epsilon$$a$$b$$C(a)$$C(b)$$C$$\epsilon$

Hay una ENORME cantidad de aplicaciones de códigos de corrección de errores en informática teórica.

Una aplicación clásica [que creo que no se mencionó anteriormente] es la construcción de extractores / muestreadores de aleatoriedad; ver, por ejemplo, aquí: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

También hay muchas aplicaciones para la criptografía, y estoy seguro de que uno de los lectores informados estará encantado de elaborar :)

Aquí hay una nueva aplicación, ¡caliente en las prensas! Un nuevo informe de ECCC de Or Meir tiene esto como resumen:

El teorema de IP, que afirma que IP = PSPACE (Lund et. Al., Y Shamir, en J. ACM 39 (4)), es uno de los principales logros de la teoría de la complejidad. Las pruebas conocidas del teorema se basan en la técnica de aritmetización, que transforma una fórmula booleana cuantificada en un polinomio relacionado. La intuición que subyace al uso de polinomios se explica comúnmente por el hecho de que los polinomios constituyen buenos códigos de corrección de errores. Sin embargo, las pruebas conocidas parecen estar adaptadas al uso de polinomios, y no se generalizan a códigos de corrección de errores arbitrarios.

En este trabajo, mostramos que el teorema de IP puede probarse utilizando códigos generales de corrección de errores. Creemos que esto establece una base rigurosa para la intuición antes mencionada, y arroja más luz sobre el teorema de IP.

Hay una serie de documentos sobre esteganografía y computación encubierta (que comienzan aquí ) que requieren fundamentalmente códigos de corrección de errores. Modelan llamadas fallidas del oráculo para extraer de una distribución arbitraria como ruido en un canal.

Algunos otros ejemplos:

• Construcción de $\epsilon$$\epsilon$

• Reducción de la dimensionalidad aleatoria rápida mejorada (Transformación rápida Johnson-Lindenstrauss), en Ailon-Liberty, SODA'08 .

Los códigos de corrección de errores se utilizan en criptografía para resolver el problema de la reconciliación de la información : Alice y Bob quieren acordar una clave K a partir de las cadenas (correlacionadas) X e Y, respectivamente. (Un ejemplo de esta situación es un protocolo que se basa en un canal ruidoso, con Alice enviando X a Bob.) Una solución es hacer que Alice envíe algún error corrigiendo la información C a Bob para que pueda reconstruir X. Por supuesto, el problema no es tan simple: dado que C filtra información al adversario Eve, necesitamos amplificar la privacidad para obtener la clave secreta. Esto se puede hacer con una función hash universal 2, como lo garantiza el lema hash sobrante.

Recientemente, se introdujeron extractores difusos como una variante de extractores tolerantes al ruido: extraen una cadena R aleatoria uniforme de su entrada W y también producen una "huella digital" P de modo que si la entrada cambia a una cadena W 'similar, la cadena aleatoria R puede recuperarse de P y W '. La construcción de extractores difusos también se basa en códigos de corrección de errores.

Andy Drucker ya ha mencionado la encuesta de Trevisan [Tre04] en un comentario a otra respuesta , ¡pero creo que debería mencionarse en una fuente más grande!

[Tre04] Luca Trevisan. Algunas aplicaciones de la teoría de la codificación en la complejidad computacional. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

De hecho, como Dana mencionó, hay muchos ejemplos.

En el cálculo de tolerancia a fallos, los códigos de corrección de errores son muy importantes. Creo que el artículo de 1988 de Ben-Or Goldwasser y Wigderson Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation , aunque no cita explícitamente los resultados de los códigos de corrección de errores, tiene un sabor ECC.

Por supuesto, el "teorema del umbral" que permite el cálculo cuántico tolerante a fallas se basa de manera crucial en los códigos de corrección de errores cuánticos que son análogos cuánticos de la ECC ordinaria.
(El artículo de Wikipedia para el teorema del umbral ciertamente necesita trabajo; pero el artículo sobre corrección cuántica de errores es mejor).

Consulte la lista de documentos ECCC etiquetados con "códigos de corrección de errores" .

Al leer esa lista, verá que hay una conexión entre los códigos de corrección de errores y los PCP (no sé si considerará que esta es una aplicación "más allá de la corrección de errores en sí misma"), y también el aprendizaje de PAC .

Para una explicación muy agradable de cómo se utilizan los códigos de corrección de errores en una situación práctica particular, consulte:

Las Matemáticas del Disco Compacto, por Jack H. Van Lint, en Mathematics Everywhere, M. Aigner y E. Behrends (editores), American Mathematical Society, 2010

(Este libro es una traducción del original alemán).

Otra aplicación está en los códigos de autenticación. Estas son esencialmente codificaciones diseñadas para detectar cualquier alteración del mensaje, y se basan fundamentalmente en la corrección de errores. Esto es algo más que una simple corrección de errores, que tiende a implicar suposiciones sobre la estructura del ruido.

El código de corrección de errores ha tenido aplicaciones en pruebas de propiedades:

• Prueba de propiedad funcional:

  • Mostrar pruebas tolerantes puede ser bastante difícil: pruebas tolerantes versus intolerantes para propiedades booleanas , por Fischer y Fortnow
  • Prueba de límites inferiores a través de la complejidad de la comunicación: Pruebas de propiedad Límites inferiores a través de la complejidad de la comunicación , por Blais, Brody y Matulef (básicamente, los ECCC son un gran paso de la reducción, lo que permite obtener la brecha prometedora en las pruebas de propiedad). Ver también la opinión de Oded Goldreich sobre esto .
  • Mostrando teoremas de jerarquía en pruebas de propiedad:
  • con respecto a la adaptabilidad : un teorema de la jerarquía de adaptabilidad para las pruebas de propiedad , por Canonne y Gur. Los ECCC (en realidad, LTC + LDC) se utilizan para "elevar" la jerarquía del modelo de consulta a las pruebas de propiedad.

• Pruebas de distribución: el análogo de la metodología de límite inferior [BBM] mencionado anteriormente también utiliza códigos de corrección de errores como un componente clave: Pruebas de distribución de límites inferiores a través de reducciones de la complejidad de la comunicación , por Blais, Canonne y Gur.

(Lo siento, esto está un poco sesgado hacia los documentos que he escrito conjuntamente, principalmente debido a mi familiaridad con ellos).

Creemos que la criptografía de clave pública basada en código es post-cuántica. De hecho, la criptografía de base de código tiene el registro histórico más largo entre los esquemas de clave pública post-cuántica, pero los tamaños de las claves parecen poco prácticos, como 1 MB en McBits .

También utilizamos códigos de corrección de errores en la criptografía de clave pública basada en redes, que emplean una fase de reconciliación como mencionó Felipe Lacerda. De hecho, nuestra mejor apuesta actual para un intercambio de claves post-cuántico es el esquema Kyber Módulo-LWE (basado en la red).