Usando códigos de correção de erros em teoria

39

Quais são as aplicações dos códigos de correção de erros na teoria, além da própria correção de erros? Estou ciente de três aplicações: o teorema de Goldreich-Levin sobre bit de núcleo duro, a construção do extrator por Trevisan e a amplificação da dureza da função booleana (Sudão-Trevisan-Vadhan).

Quais são outras aplicações 'sérias' ou 'recreativas' de códigos de correção de erros?

UPD: uma aplicação divertida de decodificação de lista de códigos de Reed-Solomon é uma solução para uma variação específica do jogo de 20 perguntas (e outra variação mais direta).

ilyaraz
fonte
1
Talvez eu seja tola, mas ninguém speaked sobre o PCP Teorema
AntonioFa

Respostas:

23

Aqui está um aplicativo direto na complexidade da comunicação (que eu vejo agora também é descrito em um comentário de Andy Drucker em seu blog ) fora do contexto da des randomização:

Suponha que Alice e Bob são dadas cordas e respectivamente, e eles querem descobrir se a distância de Hamming entre e é, no máximo (onde é uma constante fixa). Queremos provar um limite inferior da complexidade da comunicação para esse problema. A observação é que qualquer protocolo determinística para este problema resulta um protocolo determinista, com o mesmo número de ciclos para verificar a igualdade de duas cadeias de e de comprimento onde é uma constante dependendo . Por quê? Para verificar a igualdade dey x y ε n ε uma b c n c < 1 ε umxyxyϵnϵabcnc<1ϵae , Alice e Bob podem executar o protocolo para o primeiro problema em e que é um erro ao corrigir o código com distância pelo menos . Como existe um limite inferior linear fácil para o problema de igualdade, isso também gera um limite inferior linear determinístico para o primeiro problema.C ( a ) C ( b ) C ϵbC(a)C(b)Cϵ

arnab
fonte
Aplicação muito elegante!
Ilyaraz 17/08
1
Mas ... Não podemos simplesmente preencher por quantidade suficiente de zeros e -por uns? yxy
Ilyaraz 17/08
ilyaraz - se fizéssemos isso, mesmo que x, y fosse igual ao início, eles teriam uma grande distância de Hamming após o preenchimento. O objetivo de usar o mapa C () é preservar a igualdade enquanto também 'amplifica' a desigualdade.
Andy Drucker
Mas queremos distinguir duas situações: peso de Hamming pequeno versus peso de Hamming grande. Por que queremos nos preocupar em preservar a igualdade?
Ilyaraz 17/08
3
O uso mais interessante dessa idéia é, na verdade, provar um limite superior na complexidade da comunicação aleatória da igualdade: basta comparar um bit aleatório de C (a) e C (b). Se a = b, você certamente obterá igualdade; caso contrário, terá probabilidade epsilon para obter desigualdade. Isso requer O (logn) bits (para escolher o índice do bit comparado), e se as partes possuem aleatoriedade comum, a complexidade é apenas O (1).
Noam
17

Existe um número enorme de aplicações de códigos de correção de erros na ciência da computação teórica.

Uma aplicação clássica [que eu acho que não foi mencionada acima] é para a construção de extratores / amostradores de aleatoriedade; veja, por exemplo, aqui: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Também existem muitos aplicativos para criptografia, e tenho certeza de que um dos leitores informados ficaria feliz em elaborar :)

Dana Moshkovitz
fonte
Acho que o OP mencionou a construção do extrator de Trevisan na questão.
Suresh Venkat
14

Aqui está uma nova aplicação, muito quente! Um novo relatório do ECCC de Or Meir tem esse resumo:

O teorema da PI, que afirma que IP = PSPACE (Lund et. Al. E Shamir, em J. ACM 39 (4)), é uma das principais realizações da teoria da complexidade. As provas conhecidas do teorema são baseadas na técnica de aritmetização, que transforma uma fórmula booleana quantificada em um polinômio relacionado. A intuição subjacente ao uso de polinômios é geralmente explicada pelo fato de os polinômios constituírem bons códigos de correção de erros. No entanto, as provas conhecidas parecem adaptadas ao uso de polinômios e não generalizam para códigos arbitrários de correção de erros.

Neste trabalho, mostramos que o teorema do IP pode ser provado usando códigos gerais de correção de erros. Acreditamos que isso estabelece uma base rigorosa para a intuição acima mencionada e lança mais luz sobre o teorema da PI.

Suresh Venkat
fonte
Vi seu comentário, quando pretendia postar o mesmo. Agradável!
Ilyaraz
8

Há uma série de artigos sobre esteganografia e computação secreta (começando aqui ) que exigem fundamentalmente códigos de correção de erros. Eles modelam chamadas oracle com falha para extrair de uma distribuição arbitrária como ruído em um canal.

Daniel Apon
fonte
7

Alguns outros exemplos:

  • Construção de espaços de amostra independentes em sentido k com base em (por exemplo, Naor-Naor, STOC'90 ). Na verdade, eles usam ECCs duas vezes: primeiro para construir espaços de amostra com viés de e depois convertê-los em espaços independentes do tipo k.ϵϵϵ

  • Melhoria rápida da redução da dimensionalidade aleatória (Fast Johnson-Lindenstrauss Transform), em Ailon-Liberty, SODA'08 .

Piotr
fonte
Resposta muito boa!
Ilyaraz
7

Os códigos de correção de erros são usados ​​na criptografia para resolver o problema da reconciliação de informações : Alice e Bob querem concordar com uma chave K iniciando nas seqüências (correlacionadas) X e Y, respectivamente. (Um exemplo dessa situação é um protocolo que depende de um canal barulhento, com Alice enviando X para Bob.) Uma solução é fazer com que Alice envie algum erro ao corrigir as informações C para Bob para que ele possa reconstruir X. É claro que o problema não é tão simples: como C vaza algumas informações para o adversário Eva, precisamos fazer amplificação de privacidade para obter a chave secreta. Isso pode ser feito com uma função hash 2-universal, conforme garantido pelo restante do hash lema.

Recentemente, os extratores nebulosos foram introduzidos como uma variante tolerante a ruído dos extratores: eles extraem uma sequência aleatória uniformemente R de sua entrada W e também produzem uma "impressão digital" P tal que, se a entrada mudar para uma sequência semelhante W ', a sequência aleatória R pode ser recuperado de P e W '. A construção de extratores difusos também depende de códigos de correção de erros.

Felipe Lacerda
fonte
6

Andy Drucker já mencionou a pesquisa de Trevisan [Tre04] em um comentário para outra resposta , mas acho que deve ser mencionada em uma fonte maior!

[Tre04] Luca Trevisan. Algumas aplicações da teoria de codificação na complexidade computacional. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

Tsuyoshi Ito
fonte
6

De fato, como Dana mencionou, existem muitos exemplos.

No cálculo da tolerância a falhas, os códigos de correção de erros são muito importantes. Penso que o artigo de 1988 dos Teoremas de Completude de Ben-Or Goldwasser e Wigderson para Computação Distribuída Tolerante a Falhas Não Criptográfica , embora não cite explicitamente os resultados dos códigos de correção de erros, possui um sabor ECC.

Obviamente, o "teorema do limiar", que permite o cálculo quântico tolerante a falhas, depende de maneira crucial dos códigos de correção de erros quânticos, que são análogos quânticos do ECC comum.
(O artigo da Wikipedia para o teorema do limiar certamente precisa de trabalho; mas o artigo sobre correção quântica de erros é melhor.)

Gil Kalai
fonte
5

Confira a lista de documentos do ECCC marcados com "códigos de correção de erros" .

Examinando essa lista, você verá que há uma conexão entre códigos de correção de erros e PCPs (não sei se você considerará isso um aplicativo "além da própria correção de erros".) E também o aprendizado do PAC .

Joshua Grochow
fonte
2
Especificamente, os códigos conhecidos como 'códigos localmente testáveis' (LTCs) têm semelhanças estreitas com os PCPs, e as idéias usadas na criação de LTCs também foram úteis na criação de PCPs. Além disso, não tenho certeza se a pesquisa de Trevisan "Algumas aplicações da teoria de codificação na complexidade computacional" foi mencionada, mas essa é uma boa referência para sua pergunta.
Andy Drucker
4

Para uma boa descrição de como os códigos de correção de erros são usados ​​em uma situação prática específica, veja:

The Mathematics of the Compact Disc, de Jack H. Van Lint, em Mathematics Everywhere, M. Aigner e E. Behrends (editores), American Mathematics Society, 2010

(Este livro é uma tradução do original em alemão.)

Joseph Malkevitch
fonte
3

Outro aplicativo está nos códigos de autenticação. Essas são essencialmente codificações projetadas para detectar qualquer violação da mensagem e, fundamentalmente, dependem da correção de erros. Isso é um pouco mais do que simples correção de erros, o que tende a fazer suposições sobre a estrutura do ruído.

Joe Fitzsimons
fonte
2

O código de correção de erros teve aplicativos no teste de propriedades:

(Desculpe, isso é um pouco tendencioso em relação aos trabalhos que co-autor, principalmente devido à minha familiaridade com eles.)

Clemente C.
fonte
1

Acreditamos que a criptografia de chave pública baseada em código seja pós-quântica. De fato, a criptografia baseada em código tem o maior registro histórico entre os esquemas de chave pública pós-quantum, mas o tamanho das chaves parece impraticávelmente grande, como 1 MB no McBits .

Também usamos códigos de correção de erros na criptografia de chave pública com base em treliça, que emprega uma fase de reconciliação como Felipe Lacerda mencionou. De fato, nossa melhor aposta atual para uma troca de chaves pós-quantum é o esquema Módulo-LWE Kyber (baseado em treliça).

Jeff Burdges
fonte