Saya baru-baru ini menghadiri Workshop tentang Pseudorandomness di Chennai Mathematical Institute on Pseudorandomness. Venkat Guruswami membuat pernyataan yang indah berikut saat berbicara (tentang teori pengkodean):
Sungguh luar biasa berapa banyak seseorang dapat membuktikan menggunakan fakta sederhana bahwa tingkat polinomial atas lapangan dapat memiliki paling d akar.
Saya percaya ini juga disebut Metode Stepanov (dalam aplikasi-aplikasi itu, biasanya root muncul dengan banyak juga). Satu tempat di mana saya pernah melihat ini dalam sebuah makalah tentang batas akar kuadrat untuk non-residu terkecil oleh Michael Forbes, Neeraj Kayal, Rajat Mittal dan Chandan Saha.
Kepala sekolah ini disorot dalam lokakarya dengan decoding kode Reed-Solomon yang unik dan daftar ( yang dapat ditemukan dalam kursus ini , misalnya) dalam pembicaraan Venkat. Dalam ceramah Neeraj Kayal, ia memberikan dua contoh lain - bukti dari Field Hingga Kakeya Conjecture dan Joints Conjecture (keduanya dapat ditemukan dalam survei yang sangat bagus ini oleh Zeev Dvir). Contoh lain yang dapat saya pikirkan adalah bukti Dana Moshkovitz tentang Schwartz-Zippel Lemma , dan favorit saya yang lain adalah tes AKS Primality yang (jika saya diizinkan untuk melakukan peregangan) hanya menggunakan fakta ini pada dasarnya.
Saya bertanya-tanya apakah ada contoh lain dari hasil elegan menggunakan (pada dasarnya) hanya fakta sederhana ini.
Posting ini terkait erat dengan pertanyaan sebelumnya " Metode polinomial untuk hasil kompleksitas " tetapi itu untuk 'metode polinomial' yang lebih umum.
sumber
Jawaban:
Ini mungkin terlalu jelas, tetapi bukti kebenaran dari algoritma acak Schwartz-Zippel untuk pengujian identitas polinomial pada dasarnya hanya menggunakan fakta ini, ditambah induksi.
sumber