Teoretycznie stosowanie kodów korygujących błędy

Jakie są zastosowania kodów korekcji błędów w teorii oprócz samej korekcji błędów? Jestem świadomy trzech zastosowań: twierdzenia Goldreicha-Levina o twardym rdzeniu, konstrukcji ekstraktora Trevisana i wzmocnienia twardości funkcji boolowskiej (autor: Sudan-Trevisan-Vadhan).

Jakie są inne „poważne” lub „rekreacyjne” zastosowania kodów korygujących błędy?

UPD: jedna zabawna aplikacja do dekodowania list kodów Reeda-Solomona jest rozwiązaniem dla konkretnej odmiany gry złożonej z 20 pytań (i innej , prostszej odmiany).

Oto prosta aplikacja w złożoności komunikacyjnej (którą widzę teraz jest również opisana w komentarzu Andy Druckera na swoim blogu ) poza kontekstem derandomizacji:

Załóżmy, Alicja i Bob danych napisów i y odpowiednio i chcą, aby dowiedzieć się, czy odległość Hamminga pomiędzy X i Y jest maksymalnie ε n (gdzie ε jest pewne stałe stałe). Chcemy udowodnić złożoność komunikacji w dolnej granicy tego problemu. Zaobserwowano, że każdy protokół deterministyczny dla tego problemu daje protokół deterministyczny z taką samą liczbą rund do sprawdzania równości dwóch łańcuchów a i b długości c n, gdzie c < 1 jest pewną stałą zależną od $x$$y$$x$$y$$\epsilon n$$\epsilon$$a$$b$$cn$$c<1$$\epsilon$. Czemu? Aby sprawdzić równość i b , Alicja i Bob można uruchomić protokół pierwszego problemu na C ( a ) i C ( b ) , gdzie C jest błąd korygowania kodu z odległości co najmniej ε . Ponieważ istnieje problem liniowej dolnej granicy dla problemu równości, daje to również deterministyczną liniową dolną granicę dla pierwszego problemu.$a$$b$$C(a)$$C(b)$$C$$\epsilon$

Istnieje ogromna liczba zastosowań kodów korygujących błędy w informatyce teoretycznej.

Klasyczną aplikacją [o której myślę, że nie wspomniano powyżej] jest konstrukcja ekstraktorów / samplerów losowości; patrz np. tutaj: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Istnieje również wiele aplikacji do kryptografii i jestem pewien, że jeden z dobrze poinformowanych czytelników chętnie by to rozwinął :)

Oto nowa aplikacja, gorąco na prasie! Nowy raport ECCC autorstwa Or Meir ma to jako streszczenie:

Twierdzenie IP, które potwierdza, że ​​IP = PSPACE (Lund i in. I Shamir, w J. ACM 39 (4)), jest jednym z głównych osiągnięć teorii złożoności. Znane dowody twierdzenia opierają się na technice arytmetycznej, która przekształca skwantyfikowaną formułę logiczną w pokrewny wielomian. Intuicyję leżącą u podstaw zastosowania wielomianów tłumaczy się często tym, że wielomiani stanowią dobre kody korygujące błędy. Jednak znane dowody wydają się dostosowane do zastosowania wielomianów i nie generalizują się do kodów korekcji błędów.

W tej pracy pokazujemy, że twierdzenie IP można udowodnić za pomocą ogólnych kodów korekcji błędów. Uważamy, że stanowi to ścisłą podstawę wspomnianej intuicji i rzuca dalsze światło na twierdzenie IP.

Istnieje szereg artykułów na temat steganografii i tajnych obliczeń (zaczynając tutaj ), które zasadniczo wymagają kodów korygujących błędy. Modelują nieudane wywołania wyroczni, aby czerpać z dowolnej dystrybucji jako szum w kanale.

Kilka innych przykładów:

• $\epsilon$$\epsilon$

• Ulepszona szybka losowa redukcja wymiarów (Fast Johnson-Lindenstrauss Transform), w Ailon-Liberty, SODA'08 .

Kody korekcji błędów są używane w kryptografii do rozwiązania problemu uzgadniania informacji : Alice i Bob chcą uzgodnić klucz K, zaczynając od (skorelowanych) ciągów odpowiednio X i Y. (Przykładem takiej sytuacji jest protokół oparty na hałaśliwym kanale, w którym Alicja wysyła X do Boba.) Rozwiązaniem jest spowodowanie, że Alicja wyśle ​​trochę korekty informacji C do Boba, aby mógł zrekonstruować X. Oczywiście problem nie jest takie proste: skoro C wycieka jakieś informacje do przeciwnika Ewy, musimy zrobić wzmocnienie prywatności, aby uzyskać tajny klucz. Można to zrobić za pomocą 2-uniwersalnej funkcji skrótu, co gwarantuje pozostały lemat hash.

Ostatnio wprowadzono rozmyte ekstraktory jako odporny na hałas wariant ekstraktorów: wydobywają one jednolicie losowy ciąg R z jego wejścia W, a także wytwarzają „odcisk palca” P, tak że jeśli wejście zmienia się na jakiś podobny ciąg W ', ciąg losowy R można odzyskać z P i W '. Konstrukcja rozmytych ekstraktorów również opiera się na kodach korygujących błędy.

Andy Drucker wspomniał już o badaniu przeprowadzonym przez Trevisana [Tre04] w komentarzu do innej odpowiedzi , ale myślę, że należy o tym wspomnieć większą czcionką!

[Tre04] Luca Trevisan. Niektóre zastosowania teorii kodowania w złożoności obliczeniowej. Quaderni di Matematica , 13: 347–424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

Rzeczywiście, jak wspomniała Dana, istnieje wiele przykładów.

W obliczeniach tolerancji na błędy kody korekcji błędów są bardzo ważne. Wydaje mi się, że artykuł Ben-Or Goldwassera i Wigdersona o kompletności twierdzeń z 1988 r. Dla niekryptograficznych obliczeń rozproszonych tolerujących błędy, choć nie cytując wyraźnie wyników kodów korygujących błędy, ma smak ECC.

Oczywiście „twierdzenie progowe” pozwalające na obliczenia kwantowe odporne na uszkodzenia opiera się w decydujący sposób na kodach korygujących błędy kwantowe, które są kwantowymi analogami zwykłego ECC.
(Artykuł Wikipedii dotyczący twierdzenia o progu z pewnością wymaga pracy; ale artykuł na temat kwantowej korekcji błędów jest lepszy.)

Sprawdź listę dokumentów ECCC oznaczonych „kodami korygującymi błędy” .

Przeglądając tę ​​listę, zobaczysz, że istnieje związek między kodami korygującymi błędy a PCP (nie wiem, czy uważasz, że jest to aplikacja „poza samą korekcją błędów”), a także uczeniem się PAC .

Aby uzyskać bardzo ładny opis tego, jak kody korygujące błędy są używane w konkretnej praktycznej sytuacji, zobacz:

The Mathematics of the Compact Disc, autor: Jack H. Van Lint, w Mathematics Everywhere, M. Aigner i E. Behrends (redaktorzy), American Mathematical Society, 2010

(Ta książka jest tłumaczeniem z niemieckiego oryginału).

Inna aplikacja zawiera kody uwierzytelniające. Są to zasadniczo kodowania zaprojektowane do wykrywania wszelkich manipulacji przy wiadomości i zasadniczo polegają na korekcji błędów. Jest to coś więcej niż prosta korekcja błędów, która zwykle pociąga za sobą założenia dotyczące struktury szumu.

Kod korygujący błędy miał aplikacje w testowaniu właściwości:

• Testowanie właściwości funkcjonalnych:

  • Pokazywanie testów tolerancyjnych może być dość trudne: testy tolerancji w porównaniu z testami nietolerancji dla właściwości logicznych Fischera i Fortnowa
  • Zapewnienie niższych granic dzięki złożoności komunikacji: Testowanie właściwości Dolne granice poprzez złożoność komunikacji , autorstwa Blais, Brody i Matulef (w zasadzie, ECCC są dużym krokiem redukcji, pozwalającym uzyskać lukę obiecaną w testowaniu właściwości). Zobacz także stanowisko Odeda Goldreicha na ten temat .
  • Pokazywanie twierdzeń hierachy w testach własności:
  • w odniesieniu do adaptacji : Twierdzenie o hierarchii adaptacji do testowania własności , autorstwa Canonne i Gur. ECCC (a właściwie LTC + LDC) są używane do „podnoszenia” hierarchii modelu zapytań do testowania właściwości.

• Testowanie dystrybucji: W analogii wyżej wymienionej metodologii [BBM] wykorzystano również kody korekcji błędów jako kluczowy element: Testowanie dystrybucji niższych granic poprzez redukcję złożoności komunikacyjnej , autorstwa Blais, Canonne i Gur.

(Przepraszam, to jest trochę stronnicze w stosunku do artykułów, których jestem współautorem, głównie z powodu mojej znajomości z nimi.)

Uważamy, że kryptografia klucza publicznego oparta na kodzie jest post kwantowa. W rzeczywistości kryptografia oparta na kodzie ma najdłuższy rekord historii wśród post-kwantowych schematów kluczy publicznych, ale rozmiary kluczy wydają się niepraktycznie duże, jak 1 MB w McBits .

Używamy kodów korygujących błędy również w kryptografii klucza publicznego opartej na sieci, która wykorzystuje fazę uzgadniania, jak wspomniał Felipe Lacerda. W rzeczywistości naszym obecnie najlepszym wyborem na postkwantową wymianę kluczy jest schemat moduł-LWE Kyber (oparty na sieci).