Saya punya pertanyaan tentang polinomial derajat rendah dan probabilitas: Apa (perilaku asiptotik dari) probabilitas yang polinomial * acak, , lebih dari GF (2), dengan derajat dan n variabel memiliki .
* Ketika saya menulis polinomial acak dengan variabel derajat dan n, Anda dapat memikirkan setiap monomial derajat total dipilih dengan probabilitas 1/2.
Satu-satunya hal yang relevan yang saya tahu adalah varian dari Schwartz-Zippel yang menyatakan bahwa jika polinomialnya tidak konstan maka biasnya paling banyak . Oleh karena itu, untuk probabilitasnya tepat mana ini adalah probabilitas bahwa adalah sebuah konstanta. Sayangnya, ini cukup besar.
randomness
pr.probability
algebra
polynomials
Avishay Tal
sumber
sumber
Jawaban:
Makalah "Polinomial tingkat rendah acak sulit diperkirakan" oleh Ben-Eliezer, Hod, dan Lovett menjawab pertanyaan Anda. Mereka menunjukkan batasan kuat pada korelasi polinomial acak derajat dengan polinomial derajat paling banyak , dengan menganalisis bias polinomial acak. Lihat Lemma 2 mereka: bias polinomial derajat- acak (hingga beberapa yang linier dalam ) paling banyak , kecuali dengan probabilitas .d d- 1 d d n 2- Ω ( n / d) 2- Ω ( ( n≤ d) )
sumber
Pertanyaan Anda setara dengan batas ekor pada distribusi berat kode Reed-Muller. Memahami distribusi bobot kode Reed-Muller adalah pertanyaan lama dan menantang dalam teori pengkodean, dan beberapa hasil menarik diketahui tentang hal itu (distribusi bobot dipahami sepenuhnya hanya untuk dan ). Sebagai titik awal yang baik, lihat "Distribusi Berat dan Ukuran Kode Kode Reed-Muller yang Didekodekan" oleh Tali Kaufman, Shachar Lovett, Ely Porat, dan referensi di dalamnya.d=1 d=2
sumber