Theoretisch fehlerkorrigierende Codes verwenden

Was sind theoretische Anwendungen von Fehlerkorrekturcodes neben der eigentlichen Fehlerkorrektur? Ich kenne drei Anwendungen: das Goldreich-Levin-Theorem über den harten Kern, Trevisans Konstruktion des Extraktors und die Verstärkung der Härte der Booleschen Funktion (von Sudan-Trevisan-Vadhan).

Was sind andere "ernsthafte" oder "entspannende" Anwendungen von Fehlerkorrekturcodes?

UPD: Eine amüsante Anwendung der Listendecodierung von Reed-Solomon-Codes ist eine Lösung für eine bestimmte Variante des Spiels mit 20 Fragen (und eine andere , einfachere Variante).

Hier ist eine einfache Anwendung zur Komplexität der Kommunikation (die ich jetzt auch in einem Kommentar von Andy Drucker auf seinem Blog sehe ) außerhalb des Kontextes der Derandomisierung:

Angenommen, Alice und Bob erhalten die Zeichenfolgen und y und sie möchten herausfinden, ob der Hamming-Abstand zwischen x und y höchstens ϵ n beträgt (wobei ϵ eine feste Konstante ist). Wir wollen eine untere Grenze der Kommunikationskomplexität für dieses Problem nachweisen. Die Beobachtung ist, dass jedes deterministische Protokoll für dieses Problem ein deterministisches Protokoll mit der gleichen Anzahl von Runden ergibt, um die Gleichheit von zwei Ketten a und b der Länge c n zu prüfen, wobei c < 1 in Abhängigkeit von ϵ eine gewisse Konstante ist$x$$y$$x$$y$$\epsilon n$$\epsilon$$a$$b$$cn$$c<1$$\epsilon$. Warum? Um die Gleichheit von und b zu überprüfen , können Alice und Bob das Protokoll für das erste Problem auf C ( a ) und C ( b ) ausführen, wobei C ein Fehlerkorrekturcode mit einem Abstand von mindestens ϵ ist . Da es eine einfache lineare Untergrenze für das Gleichheitsproblem gibt, ergibt sich auch eine deterministische lineare Untergrenze für das erste Problem.$a$$b$$C(a)$$C(b)$$C$$\epsilon$

In der theoretischen Informatik gibt es eine GROSSE Anzahl von Anwendungen von Fehlerkorrekturcodes.

Eine klassische Anwendung [von der ich glaube, dass sie oben nicht erwähnt wurde] ist die Konstruktion von Zufallsextraktoren / Samplern. siehe zB hier: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Es gibt auch viele Anwendungen für die Kryptografie, und ich bin sicher, einer der informierten Leser würde sich freuen, darauf einzugehen :)

Hier ist eine neue Anwendung, druckfrisch! Ein neuer ECCC-Bericht von Or Meir hat dies als Zusammenfassung:

Das IP-Theorem, das IP = PSPACE (Lund et al. Und Shamir in J. ACM 39 (4)) behauptet, ist eine der wichtigsten Errungenschaften der Komplexitätstheorie. Die bekannten Beweise des Theorems basieren auf der Arithmetisierungstechnik, die eine quantifizierte Boolesche Formel in ein verwandtes Polynom umwandelt. Die Intuition, die der Verwendung von Polynomen zugrunde liegt, wird im Allgemeinen durch die Tatsache erklärt, dass Polynome gute Fehlerkorrekturcodes darstellen. Die bekannten Beweise scheinen jedoch auf die Verwendung von Polynomen zugeschnitten zu sein und verallgemeinern sich nicht auf willkürliche Fehlerkorrekturcodes.

In dieser Arbeit zeigen wir, dass das IP-Theorem mit allgemeinen Fehlerkorrekturcodes bewiesen werden kann. Wir glauben, dass dies eine strenge Grundlage für die oben genannte Intuition darstellt und das IP-Theorem weiter beleuchtet.

Es gibt eine Reihe von Artikeln über Steganographie und verdecktes Rechnen (beginnend hier ), die grundsätzlich fehlerkorrigierende Codes erfordern. Sie modellieren fehlgeschlagene Orakelaufrufe, um von einer beliebigen Verteilung als Rauschen in einem Kanal zu zeichnen.

Einige andere Beispiele:

• $\epsilon$$\epsilon$

• Verbesserte schnelle randomisierte Dimensionsreduktion (Fast Johnson-Lindenstrauss Transform) in Ailon-Liberty, SODA'08 .

Fehlerkorrekturcodes werden in der Kryptographie verwendet, um das Problem der Informationsabstimmung zu lösen : Alice und Bob möchten sich auf einen Schlüssel K einigen, der mit (korrelierten) Zeichenfolgen X bzw. Y beginnt. (Ein Beispiel für diese Situation ist ein Protokoll, das sich auf einen verrauschten Kanal stützt, wobei Alice X an Bob sendet.) Eine Lösung besteht darin, Alice dazu zu bringen, einige fehlerkorrigierende Informationen C an Bob zu senden, damit er X rekonstruieren kann ist nicht so einfach: Da C einige Informationen an die gegnerische Eva weiterleitet, müssen wir die Privatsphäre erweitern, um den geheimen Schlüssel abzuleiten. Dies kann mit einer 2-universellen Hash-Funktion erfolgen, wie dies durch das übrig gebliebene Hash-Lemma garantiert wird.

Kürzlich wurden Fuzzy-Extraktoren als eine rauschtolerante Variante von Extraktoren eingeführt: Sie extrahieren eine gleichmäßig zufällige Zeichenfolge R aus ihrer Eingabe W und erzeugen auch einen "Fingerabdruck" P, so dass, wenn sich die Eingabe in eine ähnliche Zeichenfolge W 'ändert, die zufällige Zeichenfolge R kann aus P und W 'gewonnen werden. Die Konstruktion von Fuzzy-Extraktoren beruht auch auf Fehlerkorrekturcodes.

Andy Drucker hat die Umfrage von Trevisan [Tre04] bereits in einem Kommentar zu einer anderen Antwort erwähnt , aber ich denke, dass es in einer größeren Schrift erwähnt werden sollte!

[Tre04] Luca Trevisan. Einige Anwendungen der Codierungstheorie in der rechnerischen Komplexität. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

In der Tat gibt es, wie Dana sagte, viele Beispiele.

Bei der Fehlertoleranzberechnung sind Fehlerkorrekturcodes sehr wichtig. Ich denke, der 1988 erschienene Artikel von Ben-Or Goldwasser und Wigderson über Vollständigkeitstheoreme für nicht kryptografische fehlertolerante verteilte Berechnungen hat ECC -Charakter , obwohl die Ergebnisse der Fehlerkorrekturcodes nicht explizit zitiert werden.

Natürlich beruht der "Schwellenwertsatz", der eine fehlertolerante Quantenberechnung ermöglicht, in entscheidender Weise auf Quantenfehlerkorrekturcodes, die Quantenanaloga der gewöhnlichen ECC sind.
(Der Wikipedia-Artikel zum Schwellenwertsatz benötigt sicherlich Arbeit; der Artikel zur Quantenfehlerkorrektur ist jedoch besser.)

Schauen Sie sich die Liste der ECCC-Papiere an, die mit "Fehlerkorrekturcodes" gekennzeichnet sind .

Wenn Sie diese Liste durchsehen, werden Sie feststellen, dass es einen Zusammenhang zwischen Fehlerkorrekturcodes und PCPs gibt (ich weiß nicht, ob Sie dies als eine Anwendung betrachten, die "über die eigentliche Fehlerkorrektur hinausgeht") und auch PAC-Lernen .

Um einen guten Überblick über die Verwendung von Fehlerkorrekturcodes in einer bestimmten praktischen Situation zu erhalten, schauen Sie sich Folgendes an:

Die Mathematik der Compact Disc von Jack H. Van Lint in Mathematics Everywhere, M. Aigner und E. Behrends (Herausgeber), American Mathematical Society, 2010

(Dieses Buch ist eine Übersetzung aus dem deutschen Original.)

Eine andere Anwendung ist in Authentifizierungscodes. Hierbei handelt es sich im Wesentlichen um Codierungen, die dazu dienen, Manipulationen an der Nachricht zu erkennen, und die im Wesentlichen auf einer Fehlerkorrektur beruhen. Dies ist etwas mehr als eine einfache Fehlerkorrektur, die dazu neigt, Annahmen über die Rauschstruktur zu treffen.

Fehlerkorrekturcode hatte Anwendungen beim Testen von Eigenschaften:

• Funktionsprüfung:

  • Das Zeigen von Toleranztests kann ziemlich schwierig sein: Toleranz- versus Intoleranztests für Boolesche Eigenschaften von Fischer und Fortnow
  • Niedrigere Grenzen durch Komplexität der Kommunikation nachweisen: Testen von Eigenschaften Niedrigere Grenzen durch Komplexität der Kommunikation von Blais, Brody und Matulef (im Grunde genommen sind ECCCs ein großer Schritt bei der Reduzierung, um die vielversprechende Lücke beim Testen von Eigenschaften zu schließen). Siehe dazu auch Oded Goldreichs Einstellung .
  • Hierachietheoreme beim Testen von Eigenschaften anzeigen:
  • in Bezug auf Adaptivität : Ein Adaptivitätshierarchiesatz zum Testen von Eigenschaften von Canonne und Gur. ECCCs (eigentlich LTC + LDCs) werden verwendet, um die Abfragemodellhierarchie zum Testen von Eigenschaften zu "heben".

• Verteilungstest: Das oben erwähnte Analogon der [BBM] -Methode für untere Schranken verwendet auch fehlerkorrigierende Codes als Schlüsselkomponente: Verteilungstest für untere Schranken durch Reduzierung der Kommunikationskomplexität von Blais, Canonne und Gur.

(Entschuldigung, dies ist ein bisschen voreingenommen in Bezug auf Artikel, die ich mitverfasst habe, hauptsächlich aufgrund meiner Vertrautheit mit diesen.)

Wir glauben , dass die codebasierte Kryptographie mit öffentlichen Schlüsseln postquant ist . Tatsächlich weist die Codebasis-Kryptographie den längsten Verlaufsnachweis unter den Post-Quantum-Public-Key-Schemata auf, aber die Schlüsselgrößen scheinen unpraktisch groß zu sein, wie 1 MB in McBits .

Wir verwenden Fehlerkorrekturcodes auch in der gitterbasierten Public-Key-Kryptographie, die eine Abstimmungsphase wie Felipe Lacerda verwenden. Tatsächlich ist das Modul-LWE-Schema Kyber (gitterbasiert) unsere derzeit beste Wahl für einen Austausch nach dem Quantenschlüssel.