Menggunakan kode koreksi kesalahan dalam teori

Apa saja aplikasi kode koreksi kesalahan dalam teori selain koreksi kesalahan itu sendiri? Saya mengetahui tiga aplikasi: Teorema Goldreich-Levin tentang bit inti keras, konstruksi ekstraktor Trevisan dan penguatan kekerasan fungsi boolean (oleh Sudan-Trevisan-Vadhan).

Apa aplikasi 'serius' atau 'rekreasi' lainnya dari kode koreksi kesalahan?

UPD: satu aplikasi lucu dari decoding daftar kode Reed-Solomon adalah solusi untuk variasi tertentu dari 20 pertanyaan permainan (dan yang lain , lebih mudah, variasi).

Berikut ini adalah aplikasi langsung dalam kompleksitas komunikasi (yang saya lihat sekarang juga dijelaskan dalam komentar oleh Andy Drucker di blog - nya ) di luar konteks derandomisasi:

Misalkan Alice dan Bob masing-masing diberi string dan , dan mereka ingin mengetahui apakah jarak Hamming antara dan paling banyak (di mana adalah konstanta tetap). Kami ingin membuktikan kompleksitas komunikasi yang lebih rendah untuk masalah ini. Pengamatan adalah bahwa setiap protokol deterministik untuk masalah ini menghasilkan protokol deterministik dengan jumlah putaran yang sama untuk memeriksa kesetaraan dua string dan panjang mana adalah beberapa konstanta tergantung pada . Mengapa? Untuk memeriksa kesetaraany x y ϵ n ϵ a b c n c < 1 ϵ a b C ( a ) C ( b ) C $x$$y$$x$$y$$\epsilon n$$\epsilon$$a$$b$$cn$$c<1$$\epsilon$$a$dan , Alice dan Bob dapat menjalankan protokol untuk masalah pertama pada dan mana adalah kode koreksi kesalahan dengan jarak setidaknya . Karena ada batas bawah linier mudah untuk masalah kesetaraan, ini juga menghasilkan batas bawah linier deterministik untuk masalah pertama.$b$$C(a)$$C(b)$$C$$\epsilon$

Ada sejumlah besar aplikasi kode koreksi kesalahan dalam ilmu komputer teoretis.

Aplikasi klasik [yang saya pikir tidak disebutkan di atas] adalah untuk pembuatan extractor acak / sampler; lihat, misalnya, di sini: http://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/list.htm

Ada juga banyak aplikasi untuk kriptografi, dan saya yakin salah satu pembaca informasi akan dengan senang hati menguraikan :)

Ini adalah aplikasi baru, siapkan media! Laporan ECCC baru oleh Or Meir menjadikannya sebagai abstrak:

Teorema IP, yang menyatakan bahwa IP = PSPACE (Lund et. Al., Dan Shamir, dalam J. ACM 39 (4)), adalah salah satu pencapaian utama teori kompleksitas. Bukti teorema yang diketahui didasarkan pada teknik aritmetisasi, yang mengubah rumus Boolean yang dikuantifikasi menjadi polinomial terkait. Intuisi yang mendasari penggunaan polinomial umumnya dijelaskan oleh fakta bahwa polinomial merupakan kode koreksi kesalahan yang baik. Namun, bukti yang diketahui tampaknya disesuaikan dengan penggunaan polinomial, dan tidak menyamaratakan kode koreksi kesalahan sewenang-wenang.

Dalam karya ini, kami menunjukkan bahwa teorema IP dapat dibuktikan dengan menggunakan kode koreksi kesalahan umum. Kami percaya bahwa ini membangun dasar yang kuat untuk intuisi yang disebutkan di atas, dan menjelaskan lebih lanjut tentang teorema IP.

Ada serangkaian makalah tentang steganografi dan perhitungan rahasia (mulai di sini ) yang secara mendasar membutuhkan kode koreksi kesalahan. Mereka memodelkan panggilan oracle gagal untuk menarik dari distribusi sewenang-wenang sebagai kebisingan di saluran.

Beberapa contoh lain:

• Konstruksi ruang sampel independen k-wise kualifikasi (misalnya, Naor-Naor, STOC'90 ). Sebenarnya, mereka menggunakan ECC dua kali: pertama untuk membangun ruang sampel yang sesuai dengan , dan kemudian mengubahnya menjadi yang independen k-wise.$\epsilon$$\epsilon$

• Peningkatan pengurangan dimensi acak cepat (Fast Johnson-Lindenstrauss Transform), di Ailon-Liberty, SODA'08 .

Kode koreksi kesalahan digunakan dalam kriptografi untuk menyelesaikan masalah rekonsiliasi informasi : Alice dan Bob ingin menyepakati kunci K mulai dari (berkorelasi) string X dan Y, masing-masing. (Contoh dari situasi ini adalah protokol yang bergantung pada saluran yang berisik, dengan Alice mengirim X ke Bob.) Solusi adalah membuat Alice mengirim beberapa kesalahan mengoreksi informasi C ke Bob sehingga ia dapat merekonstruksi X. Tentu saja, masalahnya tidak begitu sederhana: karena C membocorkan beberapa informasi ke Hawa lawan, kita perlu melakukan amplifikasi privasi untuk mendapatkan kunci rahasia. Ini dapat dilakukan dengan fungsi hash 2-universal, seperti yang dijamin oleh lemma hash sisa.

Baru-baru ini, ekstraktor fuzzy diperkenalkan sebagai varian ekstraktor yang toleran terhadap kebisingan: mereka mengekstraksi string acak seragam R dari input W dan juga menghasilkan P "sidik jari" sehingga jika input berubah menjadi string W 'yang serupa, string acak R dapat dipulihkan dari P dan W '. Konstruksi ekstraktor fuzzy juga bergantung pada kode koreksi kesalahan.

Andy Drucker telah menyebutkan survei oleh Trevisan [Tre04] dalam komentar untuk jawaban lain , tapi saya pikir itu harus disebutkan dalam font yang lebih besar!

[Tre04] Luca Trevisan. Beberapa aplikasi teori pengkodean dalam kompleksitas komputasi. Quaderni di Matematica , 13: 347-424, 2004. http://www.cs.berkeley.edu/~luca/pubs/codingsurvey.pdf

Memang, seperti yang disebutkan Dana, ada banyak contoh.

Dalam toleransi kesalahan perhitungan kode koreksi kesalahan sangat penting. Saya pikir makalah tahun 1988 oleh Ben-Atau Goldwasser dan Teorema Kelengkapan Wigderson untuk Non-Cryptographic Fault-Tolerant Distributed Computation , sementara tidak secara eksplisit mengutip kode koreksi kesalahan hasil memiliki rasa ECC.

Tentu saja, "teorema ambang batas" yang memungkinkan perhitungan kuantum toleran kesalahan bergantung pada cara yang krusial pada kode koreksi kesalahan kuantum yang merupakan analog kuantum dari ECC biasa.
( Artikel Wikipedia untuk teorema ambang batas tentu perlu bekerja; Tetapi artikel tentang koreksi kesalahan kuantum lebih baik.)

Periksa daftar makalah ECCC yang ditandai dengan "kode koreksi kesalahan" .

Membaca dengan teliti daftar itu, Anda akan melihat bahwa ada hubungan antara kode-kode koreksi kesalahan dan PCP (saya tidak tahu apakah Anda akan menganggap ini sebuah aplikasi "di luar hanya memperbaiki kesalahan itu sendiri."), Dan juga pembelajaran PAC .

Untuk akun yang sangat bagus tentang bagaimana kode koreksi kesalahan digunakan dalam situasi praktis tertentu, lihat:

Matematika Compact Disc, oleh Jack H. Van Lint, dalam Matematika Everywhere, M. Aigner dan E. Behrends (editor), American Mathematical Society, 2010

(Buku ini adalah terjemahan dari bahasa Jerman asli.)

Aplikasi lain dalam kode otentikasi. Ini pada dasarnya adalah pengkodean yang dirancang untuk mendeteksi adanya gangguan pada pesan, dan secara mendasar bergantung pada koreksi kesalahan. Ini agak lebih dari koreksi kesalahan sederhana, yang cenderung memerlukan asumsi tentang struktur kebisingan.

Kode koreksi kesalahan memiliki aplikasi dalam pengujian properti:

• Pengujian properti fungsional:

  • Menampilkan pengujian toleran bisa sangat sulit: Pengujian Toleransi vs. Intoleransi untuk Properti Boolean , oleh Fischer dan Fortnow
  • Membuktikan batas bawah melalui kompleksitas komunikasi: Pengujian Properti Batas Bawah melalui Kompleksitas Komunikasi , oleh Blais, Brody, dan Matulef (pada dasarnya, ECCC adalah langkah besar pengurangan, memungkinkan untuk mendapatkan celah janji dalam pengujian properti). Lihat juga pendapat Oded Goldreich tentang ini .
  • Menampilkan teorema hierak dalam pengujian properti:
  • berkaitan dengan adaptifitas : Teorema Hierarki Adaptivity untuk Pengujian Properti , oleh Canonne dan Gur. ECCC (sebenarnya, LTC + LDC) digunakan untuk "mengangkat" hierarki model kueri ke pengujian properti.

• Pengujian distribusi: Analog dari metodologi batas bawah [BBM] yang disebutkan di atas juga menggunakan kode koreksi kesalahan sebagai komponen utama: Pengujian Distribusi Batas Bawah melalui Pengurangan dari Kompleksitas Komunikasi , oleh Blais, Canonne, dan Gur.

(Maaf, ini agak bias terhadap makalah yang saya tulis bersama, sebagian besar karena keakraban saya dengan itu.)

Kami percaya kriptografi kunci publik berbasis kode sebagai pasca-kuantum. Faktanya, kriptografi berbasis kode memiliki catatan sejarah terpanjang di antara skema kunci publik pasca-kuantum, tetapi ukuran kunci tampak tidak praktis besar, seperti 1MB di McBits .

Kami menggunakan kode koreksi kesalahan dalam kriptografi kunci publik berbasis kisi juga, yang menggunakan fase rekonsiliasi seperti yang disebutkan Felipe Lacerda. Faktanya, taruhan terbaik kami saat ini untuk pertukaran kunci pasca-kuantum adalah skema Module-LWE Kyber (berbasis kisi).