Pertanyaan saya berkaitan dengan bukti teorema utama Ajtai dalam makalahnya yang inovatif pada tahun 1996, Menghasilkan contoh-contoh sulit dari masalah kisi , yang menunjukkan hubungan antara masalah kisi hard case terburuk dan hard case rata-rata. Bukti ini sulit bagi saya untuk mengerti. Apakah ada eksposisi yang jelas dari bukti ini dalam literatur?
integer-lattice
Krishnan Narayanan
sumber
sumber
Jawaban:
Anda dapat mencoba membaca makalah yang lebih baru seperti Pengurangan kasus terburuk ke kasus rata-rata berdasarkan Pengukuran Gaussian oleh Miccancio dan Regev, atau catatan kuliah Regev tentang subjek (Anda mungkin ingin membaca seluruh kursus ).
sumber