Makalah baru yang paling penting dalam kompleksitas komputasi

Kita sering mendengar tentang penelitian klasik dan publikasi di bidang kompleksitas komputasi (Turing, Cook, Karp, Hartmanis, Razborov dll). Saya bertanya-tanya apakah ada makalah yang diterbitkan baru-baru ini dianggap mani dan harus dibaca. Maksud saya baru-baru ini dalam 5/10 tahun terakhir.

Baru-baru ini kertas dari László Babai menunjukkan bahwa Grafik isomorfisma dalam Kuasi-P sudah klasik.

Berikut adalah paparan yang lebih mudah diakses dari hasil yang dipublikasikan dalam proses ICM 2018.

Dalam cetakan awal baru-baru ini, Harvey dan Van Der Hoeven menunjukkan bagaimana menghitung perkalian bilangan bulat dalam waktu $O(n \log n)$ pada mesin Turing multi-tape, yang memuncak sekitar 60 tahun penelitian (Karatsuba, Toom-Cook, Schönhage-Strassen, Fürer , Harvey – Van Der Hoeven – Lecerf). Makalah ini belum ditinjau oleh sejawat, tetapi pekerjaan sebelumnya dari penulis tentang masalah ini membuatnya masuk akal, dan para ahli tampaknya optimis.

Pentingnya di mata yang melihatnya. Namun, saya akan mengatakan bahwa dugaan dikotomi Feder-Vardi CSP, dibuktikan secara independen oleh A. Bulatov dan D. Zhuk , adalah hasil mani.

Sirkuit Non-Seragam ACC Batas Bawah oleh Ryan Williams:

https://people.csail.mit.edu/rrw/acc-lbs.pdf

dan Verifikasi Klasik Komputasi Quantum oleh Urmila Mahadev:

http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f259.pdf

sepertinya kandidat yang bagus

Makalah baru ini oleh Hao Huang [1] (belum peer-review, sejauh yang saya tahu) mungkin memenuhi syarat ... ini membuktikan dugaan sensitivitas Nisan dan Szegedy, yang telah dibuka selama ~ 30 tahun.

[1] Subgraf yang diinduksi hypercubes dan bukti dari Dugaan Sensitivitas, Hao Huang. Manuskrip, 2019. https://arxiv.org/abs/1907.00847

Subhash Khot, Dor Minzer, dan karya Muli Safra tahun 2018 "Set Pseudorandom di Grassmann Graph memiliki Ekspansi Dekat-Sempurna" telah membuat kita "setengah jalan" ke Konjektur Game Unik dan secara metodologis cukup menarik menurut orang yang lebih berpengetahuan daripada I. Mengutip Boaz Barak ,

Ini menetapkan untuk pertama kalinya kekerasan permainan unik di rezim yang algoritma waktu sub-eksponensial diketahui, dan karenanya (perlu) menggunakan pengurangan dengan beberapa (besar) blowup polinomial. Walaupun secara teori masih mungkin untuk dugaan gim-gim yang unik itu salah (seperti yang saya pribadi yakini akan terjadi hingga urutan hasil terbaru ini) skenario yang paling mungkin adalah sekarang bahwa UGC benar, dan kompleksitas UG (s) , c) masalah terlihat seperti berikut ...

Makalah ini telah menyebabkan beberapa peneliti (termasuk Barak) secara terbuka mengubah pendapat mereka tentang kebenaran UGC (dari false menjadi true).

"Tentang kemungkinan algoritma SAT yang lebih cepat" oleh Pătraşcu & Williams (SODA 2010). Ini memberikan hubungan yang erat antara kompleksitas pemecahan CNF-SAT dan kompleksitas beberapa masalah polinomial (himpunan k-dominasi, d-sum, dll.).

Hasilnya ada dua: kita bisa meningkatkan kompleksitas penyelesaian beberapa masalah polinomial, dan karenanya ETH salah dan kita mendapatkan algoritma yang lebih baik untuk CNF-SAT. Atau ETH benar, dan dengan demikian kita mendapatkan batas bawah pada beberapa masalah polinomial.

Makalah ini sangat mudah dibaca dan dimengerti. Bagi saya, ini adalah awal dari kompleksitas yang rumit.

Ini satu tahun di luar batas 10 tahun, tetapi "Mendelegasikan Komputasi: Bukti Interaktif untuk Muggle" oleh Goldwasser, Kalai, dan Rothblum telah menjadi makalah yang sangat berpengaruh. Hasil utama adalah bahwa ada bukti interaktif untuk setiap perhitungan seragam ruang-log di mana prover berjalan dalam waktu poly (n) dan verifier dalam waktu n * polylog (n) dengan bit komunikasi polylog (n).

Makalah ini telah memulai penelitian awal tentang bukti interaktif dan perhitungan yang dapat diverifikasi untuk masalah dalam P telah sangat berpengaruh dalam kriptografi di mana itu dan pekerjaan yang diikuti telah membuat bukti interaktif dunia nyata hampir praktis.

Untuk dampak, dan menjangkau kertas tengara oleh Indyk, dan Backurs memberikan batasan untuk mengedit perhitungan jarak. Makalah ini menunjukkan batas komputasi, dengan menautkan, k-SAT, dan SETH. Untuk membatasi penghitungan jarak levenshtein, di antara string, kertas menunjukkan batas ketat untuk menghitung jarak pengeditan - lebih baik daripada SETH dilanggar (SETH mungkin salah pada awalnya, atau bahkan memiliki batas bawah yang lebih ketat sekalipun). Penerapan SETH untuk kemungkinan masalah dalam P, untuk mendapatkan batasan, atau membatasi penerapan algoritma (kemungkinan perhitungan!) Adalah hal baru.

Atau makalah ini oleh P. Goldberg, dan C. Papadimitrou, tentang kompleksitas yang seragam untuk fungsi total. Menuju teori kompleksitas terpadu dari fungsi total .

Tidak yakin apakah ini memenuhi syarat - keduanya berusia lebih dari 10 tahun, dan tidak benar-benar menghasilkan kompleksitas komputasi itu sendiri - tetapi saya pikir pasangan {Graph Structure Theorem, Graph Minor Theorem} patut diperhatikan. Itu selesai pada tahun 2004, dan menetapkan kesetaraan antara "kompleksitas topologi terbatas" dan "Tidak mengandung beberapa set anak di bawah umur yang terbatas". Setiap teorema menetapkan satu arah kesetaraan.

Ini terutama memiliki dampak dalam bidang teori kompleksitas parameter, di mana salah satu dari tindakan ini sering dibatasi, memungkinkan untuk algoritma yang efisien yang memanfaatkan yang lain. Jadi, saya akan mengatakan bahwa hasil ini memiliki dampak besar pada kompleksitas komputasi, bahkan jika mereka tidak datang langsung dari bidang itu sendiri.