Utilisation de codes correcteurs d'erreur en théorie

Quelles sont les applications théoriques des codes de correction d'erreur en plus de la correction d'erreur elle-même? Je connais trois applications: le théorème de Goldreich-Levin sur le trépan dur, la construction d’un extracteur par Trevisan et l’ amplification de la dureté de la fonction booléenne (de Sudan-Trevisan-Vadhan).

Quelles sont les autres applications «sérieuses» ou «récréatives» de codes de correction d'erreur?

UPD: une application amusante de décodage de liste de codes de Reed-Solomon est une solution à une variation particulière du jeu de 20 questions (et une autre , plus simple, de variation).

Voici une application simple de la complexité de la communication (que je vois maintenant est également décrite dans un commentaire d'Andy Drucker sur son blog ) en dehors du contexte de la dérandomisation:

Supposons que les chaînes et y soient respectivement attribuées à Alice et à Bob , qui veulent savoir si la distance de Hamming entre x et y est au plus égale à ϵ n (où ϵ est une constante fixe). Nous voulons prouver une complexité inférieure de la communication pour ce problème. L'observation est que tout protocole déterministe pour résoudre ce problème conduit à un protocole déterministe avec le même nombre de tours pour vérifier l' égalité de deux chaînes a et b de longueur c n où c < 1 est une constante en fonction de $x$$y$$x$$y$$\epsilon n$$\epsilon$$a$$b$$cn$$c<1$$\epsilon$. Pourquoi? Pour vérifier l' égalité de et b , Alice et Bob peuvent exécuter le protocole du premier problème sur C ( a ) et C ( b ) où C est un code correcteur d' erreur à distance au moins ε . Puisqu'il existe une limite inférieure linéaire simple pour le problème d'égalité, cela produit également une limite inférieure linéaire déterministe pour le premier problème.$a$$b$$C(a)$$C(b)$$C$$\epsilon$

Il existe un nombre énorme d'applications de codes de correction d'erreur en informatique théorique.

Une application classique [qui, je pense, n’a pas été mentionnée ci-dessus] concerne la construction d’extracteurs / échantillonneurs aléatoires; voir, par exemple, ici: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Il existe également de nombreuses applications en cryptographie, et je suis sûr que l’un des lecteurs avertis serait heureux de vous en parler :)

Voici une nouvelle application, sortie des presses! Or Meir a rédigé un nouveau rapport des CETC dans son résumé:

Le théorème IP, qui affirme que IP = PSPACE (Lund et al., Et Shamir, dans J. ACM 39 (4)), est l'une des réalisations majeures de la théorie de la complexité. Les preuves connues du théorème sont basées sur la technique d'arithmétisation, qui transforme une formule booléenne quantifiée en un polynôme associé. L’intuition qui sous-tend l’utilisation des polynômes s’explique généralement par le fait qu’ils constituent de bons codes correcteurs d’erreur. Cependant, les preuves connues semblent adaptées à l'utilisation de polynômes et ne se généralisent pas aux codes de correction d'erreur arbitraires.

Dans ce travail, nous montrons que le théorème IP peut être prouvé en utilisant des codes de correction d'erreur généraux. Nous pensons que cela établit une base rigoureuse pour l'intuition susmentionnée et jette un éclairage supplémentaire sur le théorème de la propriété intellectuelle.

Il existe une série d'articles sur la stéganographie et le calcul discret (commençant ici ) qui nécessitent fondamentalement des codes de correction d'erreur. Ils modélisent les appels oracle ayant échoué pour tirer d'une distribution arbitraire le bruit d'un canal.

Quelques autres exemples:

• Construction d' -biased k-sages espaces d'échantillons indépendants (par exemple, Naor-Naor, STOC'90 ). En fait, ils utilisent deux fois CEC: d' abord pour construire ε espaces d'échantillons -biased, puis de les convertir en k-sages les indépendants.$\epsilon$$\epsilon$

• Réduction rapide de la dimensionnalité randomisée améliorée (transformation rapide de Johnson-Lindenstrauss), dans Ailon-Liberty, SODA'08 .

Les codes de correction d'erreur sont utilisés en cryptographie pour résoudre le problème de la réconciliation des informations : Alice et Bob veulent s'accorder sur une clé K à partir de chaînes (corrélées) X et Y, respectivement. (Un exemple de cette situation est un protocole qui repose sur un canal bruyant, Alice envoyant X à Bob.) Une solution consiste à faire envoyer à Bob des informations de correction d'erreur C à Bob afin qu'il puisse reconstruire X. Bien sûr, le problème Ce n’est pas si simple: comme C transmet des informations à l’adversaire Eve, nous devons procéder à une amplification de la confidentialité afin d’en extraire la clé secrète. Cela peut être fait avec une fonction de hachage 2-universelle, comme le garantit le lemme de hachage restant.

Récemment, les extracteurs flous ont été introduits en tant que variante des extracteurs tolérants au bruit: ils extraient une chaîne R uniformément aléatoire de son entrée W et produisent également une "empreinte digitale" P telle que si l'entrée change en une chaîne similaire W ', la chaîne aléatoire R peut être récupéré de P et W '. La construction des extracteurs flous repose également sur des codes de correction d'erreur.

Andy Drucker a déjà mentionné le sondage de Trevisan [Tre04] dans un commentaire pour une autre réponse , mais je pense qu'il devrait être mentionné dans une police plus grande!

[Tre04] Luca Trevisan. Quelques applications de la théorie du codage en complexité de calcul. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

En effet, comme Dana l’a mentionné, il existe de nombreux exemples.

Dans le calcul de la tolérance aux pannes, les codes de correction d'erreur sont très importants. Je pense que l'article de 1988 de Ben-Or Goldwasser et Wigderson sur les théorèmes de complétude pour le calcul distribué non cryptographique à tolérance de pannes , sans citer explicitement les résultats des codes de correction d'erreur, a la saveur ECC.

Bien entendu, le "théorème de seuil" permettant un calcul quantique tolérant aux fautes repose de manière cruciale sur des codes de correction d'erreur quantique, analogues quantiques de la CCE ordinaire.
(L' article de Wikipedia sur le théorème de seuil a certainement besoin de travail. Mais l' article sur la correction d'erreur quantique est préférable.)

Consultez la liste des documents ECCC portant la mention "codes de correction d'erreur" .

En parcourant cette liste, vous verrez qu'il existe un lien entre les codes de correction d'erreur et les PCP (je ne sais pas si vous allez considérer cela comme une application "au-delà de la correction d'erreur elle-même."), Ainsi que l' apprentissage par PAC .

Pour un très bon compte-rendu de la façon dont les codes de correction d'erreur sont utilisés dans une situation pratique particulière, regardez:

Les mathématiques du disque compact, de Jack H. Van Lint, dans Mathematics Everywhere, M. Aigner et E. Behrends (rédacteurs), American Mathematical Society, 2010

(Ce livre est une traduction de l'original allemand.)

Une autre application est dans les codes d'authentification. Ce sont essentiellement des encodages conçus pour détecter toute altération du message et reposent fondamentalement sur la correction d'erreur. C'est un peu plus qu'une simple correction d'erreur, qui implique généralement de faire des hypothèses sur la structure du bruit.

Le code correcteur d'erreur avait des applications dans les tests de propriétés:

• Test de propriété fonctionnelle:

  • Montrer les tests tolérants peut être assez difficile: tests tolérants ou intolérants pour les propriétés booléennes , par Fischer et Fortnow
  • Prouver les limites inférieures via la complexité de la communication: Test des propriétés Limites inférieures via la complexité de la communication , de Blais, Brody et Matulef (essentiellement, les CETC constituent un grand pas en avant dans la réduction, permettant de combler l'écart de promesse dans les tests de propriétés). Voir aussi la position d' Oded Goldreich à ce sujet .
  • Affichage des théorèmes de hiérarchie dans les tests de propriétés:
  • en ce qui concerne l' adaptivité : un théorème de la hiérarchie de l'adaptivité pour les tests de propriétés , par Canonne et Gur. Les CETC (en fait les LTC + LDC) sont utilisés pour "élever" la hiérarchie du modèle de requête aux tests de propriété.

• Test de distribution: l'analogue de la méthodologie de la limite inférieure [BBM] mentionnée ci-dessus utilise également des codes de correction d'erreur comme composant clé: Test de distribution, bornes inférieures via des réductions de la complexité de la communication , de Blais, Canonne et Gur.

(Désolé, ceci est un peu biaisé par rapport aux articles que j'ai co-écrit, principalement en raison de ma familiarité avec ceux-ci.)

Nous pensons que la cryptographie à clé publique basée sur du code est post-quantique. En fait, la cryptographie à base de code possède l'historique le plus long parmi les schémas de clé publique post-quantique, mais la taille des clés semble trop grande, comme 1 Mo dans McBits .

Nous utilisons également des codes de correction d'erreur dans la cryptographie à clé publique sur réseau, qui utilise une phase de réconciliation comme celle mentionnée par Felipe Lacerda. En fait, notre meilleur choix actuel pour un échange de clé post-quantique est le schéma Kyber Module-LWE (basé sur le réseau).