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).
co.combinatorics
big-list
coding-theory
ilyaraz
fonte
fonte
Respostas:
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 ε umx y x y ϵ n ϵ uma b c n c < 1 ϵ uma e , 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 ϵb C( Um ) C( B ) C ϵ
fonte
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 :)
fonte
Aqui está uma nova aplicação, muito quente! Um novo relatório do ECCC de Or Meir tem esse resumo:
fonte
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.
fonte
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 .
fonte
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.
fonte
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
fonte
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.)
fonte
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 .
fonte
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.)
fonte
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.
fonte
O código de correção de erros teve aplicativos no teste de propriedades:
Teste de propriedades funcionais:
Teste de distribuição: O análogo da metodologia de limite inferior do [BBM] mencionado acima também usa códigos de correção de erros como um componente-chave: Teste de distribuição de limites inferiores por meio de reduções da complexidade da comunicação , por Blais, Canonne e Gur.
(Desculpe, isso é um pouco tendencioso em relação aos trabalhos que co-autor, principalmente devido à minha familiaridade com eles.)
fonte
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).
fonte