Noisy Parity (LWE) hasil batas bawah / kekerasan

Beberapa latar belakang:

Saya tertarik untuk menemukan batas bawah (atau hasil kekerasan) "kurang dikenal" untuk masalah Belajar dengan Kesalahan (LWE), dan generalisasi seperti Belajar dengan Kesalahan atas Cincin. Untuk definisi spesifik, dll., Ini adalah survei yang bagus oleh Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

Tipe standar (R) asumsi gaya LWE adalah melalui (mungkin, kuantum) reduksi ke Masalah Vektor Terpendek pada (mungkin, ideal) kisi. Formulasi SVP yang biasa dikenal sebagai NP-hard, dan itu PERCAYA sulit untuk mendekati faktor polinomial kecil. (Terkait: Sulit untuk memperkirakan CVP dalam / hampir polinomial / faktor: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) Saya juga pernah mendengarnya menyebutkan bahwa (dalam hal algoritma kuantum) mendekati masalah kisi tertentu (seperti SVP) ke faktor perkiraan polinom kecil terkait dengan masalah subkelompok tersembunyi non-Abelian (yang diyakini sulit karena alasannya sendiri), meskipun saya belum pernah melihat sumber formal yang eksplisit untuk hal ini.

Saya lebih tertarik, bagaimanapun, dalam hasil kekerasan (jenis apa pun) yang datang sebagai akibat dari masalah Paritas Bising dari Teori Belajar. Ini bisa berupa hasil kekerasan kelas kompleksitas, batas bawah algoritmik beton, batas kompleksitas sampel, atau bahkan ukuran batas bawah bukti (misalnya Resolusi). Diketahui (mungkin, sudah jelas) bahwa LWE dapat dipandang sebagai generalisasi dari masalah Paritas Bising / Pembelajaran Paritas dengan Kebisingan (LPN), yang (dari Googling) tampaknya telah digunakan dalam pengurangan kekerasan di berbagai bidang seperti teori pengkodean dan PAC belajar.

Dari melihat-lihat sendiri, saya hanya menemukan (agak subeksponensial) BAIK-BAIK MENDAPAT masalah LPN, misalnya http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf

Pertanyaan:

Saya tahu LPN PERCAYA SULIT dalam komunitas belajar. Pertanyaan saya adalah: Mengapa?

Apakah karena semua orang berusaha sangat keras, tetapi belum ada yang menemukan algoritma yang baik? Adakah batas bawah dari varietas yang dicetak miring di atas (atau yang lain yang saya tinggalkan)?

Jika jawabannya sangat jelas, ringkasan singkat tentang apa yang diketahui dan / atau referensi untuk survei / catatan kuliah akan sangat bagus.

Jika banyak yang tidak diketahui, semakin banyak kertas "canggih", semakin baik. :) (Terima kasih sebelumnya!)

Masalah LPN memang diyakini sulit, tetapi seperti kebanyakan masalah yang kami yakini sulit, alasan utamanya adalah karena banyak orang pintar telah berusaha menemukan algoritma yang efisien dan gagal.

"Bukti" terbaik untuk kekerasan LPN berasal dari dimensi kueri statistik yang tinggi dari masalah paritas. Query statistik menangkap algoritma pembelajaran yang paling dikenal, kecuali untuk eliminasi gaussian (yang gagal setiap kali noise diperkenalkan), hashing, dan teknik yang mirip dengan keduanya. Sulit untuk merancang algoritma non-statistik-permintaan, dan ini adalah hambatan utama. Bukti lain dari kekerasan LPN adalah hubungannya dengan masalah-masalah sulit lainnya (seperti LWE, SVP seperti yang telah Anda tunjukkan).

Untuk kekerasan SQ, inilah tautan ke makalah Kearns ('98).

Untuk kemajuan pada batas atas pada masalah ini, ada beberapa hasil:

• $2^N$$2^{n / \log n}$
• $O(2^{n / \log\log n})$$O(n^{1 + \epsilon})$
• $k$$\approx O(n^{0.5 k})$$O(n^k)$$O(n^k)$$\eta$$1/2$
• $\approx O(n^{0.8 k})$