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

39

¿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).

ilyaraz
fuente
1
Tal vez seré tonto, pero nadie habló sobre el teorema de PCP
AntonioFa

Respuestas:

23

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:

xyxyϵnϵabcnc<1ϵabC(a)C(b)Cϵ

arnab
fuente
Muy buena aplicación!
ilyaraz
1
xy
ilyaraz: si hiciéramos eso, incluso si x, y fueran iguales para comenzar, tendrían una gran distancia de Hamming después del relleno. El punto de usar el mapa C () es preservar la igualdad y al mismo tiempo 'amplificar' la desigualdad.
Andy Drucker
Pero queremos distinguir dos situaciones: peso de Hamming pequeño versus peso de Hamming grande. ¿Por qué queremos preocuparnos por preservar la igualdad?
ilyaraz
3
El uso más interesante de esta idea es probar un límite superior en la complejidad de la comunicación aleatorizada de la igualdad: simplemente compare un bit aleatorio de C (a) y C (b). Si a = b, entonces ciertamente obtendrá igualdad, de lo contrario tiene probabilidad de épsilon para obtener desigualdad. Esto requiere O (logn) bits (para elegir el índice del bit comparado), y si las partes tienen aleatoriedad común, entonces la complejidad es solo O (1).
Noam
17

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 :)

Dana Moshkovitz
fuente
Creo que el OP mencionó la construcción del extractor de Trevisan en la pregunta.
Suresh Venkat
14

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.

Suresh Venkat
fuente
Vi tu comentario, cuando tenía la intención de publicar el mismo. ¡Agradable!
ilyaraz
8

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.

Daniel Apon
fuente
7

Algunos otros ejemplos:

  • Construcción de ϵϵ

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

Piotr
fuente
Muy buena respuesta!
ilyaraz
7

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.

Felipe Lacerda
fuente
6

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

Tsuyoshi Ito
fuente
6

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).

Gil Kalai
fuente
5

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 .

Joshua Grochow
fuente
2
Específicamente, los códigos conocidos como 'códigos comprobables localmente' (LTC) tienen similitudes cercanas con los PCP, y las ideas utilizadas en la construcción de LTC también han sido útiles para construir PCP. Además, no estoy seguro de si se ha mencionado la encuesta de Trevisan "Algunas aplicaciones de la teoría de la codificación en la complejidad computacional", pero esa es una buena referencia para su pregunta.
Andy Drucker
4

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).

Joseph Malkevitch
fuente
3

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.

Joe Fitzsimons
fuente
2

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

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

Clemente C.
fuente
1

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).

Jeff Burdges
fuente