Utilisation de codes correcteurs d'erreur en théorie

39

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

ilyaraz
la source
1
Peut - être que je serai stupide, mais personne ne speaked sur le théorème PCP
AntonioFa

Réponses:

23

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 nc < 1 est une constante en fonction de εXyXyεnεunebcnc<1ε. 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 )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.unebC(une)C(b)Cε

arnab
la source
Application très soignée!
ilyaraz
1
Mais ... Ne pouvons-nous pas simplement ajouter par zéros et par y ? Xy
Ilyaraz
ilyaraz - si nous faisions cela, alors même si x, y étaient égaux pour commencer, ils auraient une grande distance de Hamming après le rembourrage. L’utilisation de la carte C () a pour objectif de préserver l’égalité tout en "amplifiant" les inégalités.
Andy Drucker
Mais nous voulons distinguer deux situations: petit poids de Hamming vs grand poids de Hamming. Pourquoi voulons-nous nous soucier de préserver l'égalité?
ilyaraz
3
L’utilisation la plus intéressante de cette idée est en fait de prouver une limite supérieure de la complexité de l’égalité de la communication aléatoire: il suffit de comparer un bit aléatoire de C (a) et C (b). Si a = b, vous obtiendrez certainement l'égalité, sinon vous avez la probabilité que epsilon obtienne une inégalité. Cela nécessite O (logn) bits (pour choisir l’indice du bit comparé), et si les parties ont un caractère aléatoire commun, la complexité est tout simplement O (1).
Noam
17

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

Dana Moshkovitz
la source
Je pense que le PO a mentionné la construction de l'extracteur de Trevisan dans la question.
Suresh Venkat
14

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.

Suresh Venkat
la source
J'ai vu votre commentaire, alors que j'avais l'intention de poster le même. Agréable!
ilyaraz
8

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.

Daniel Apon
la source
7

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

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

Piotr
la source
Très belle réponse!
ilyaraz
7

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.

Felipe Lacerda
la source
6

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

Tsuyoshi Ito
la source
6

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

Gil Kalai
la source
5

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 .

Joshua Grochow
la source
2
Plus précisément, les codes connus sous le nom de «codes testables localement» (LTC) présentent des similitudes étroites avec les PCP, et les idées utilisées pour construire des LTC ont également été utiles pour la construction de PCP. De plus, je ne suis pas sûr que l’enquête de Trevisan intitulée "Quelques applications de la théorie du codage à la complexité de calcul" ait été mentionnée, mais c’est une bonne référence pour votre question.
Andy Drucker
4

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

Joseph Malkevitch
la source
3

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.

Joe Fitzsimons
la source
2

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

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

Clément C.
la source
1

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

Jeff Burdges
la source