Bagaimana mengutip hasil grafik isomorfisma baru Babai?

16

Baru-baru ini, Babai telah menerbitkan sebuah makalah tentang STOC 2016 mengklaim bahwa grafik isomorfisme dapat diselesaikan dalam waktu quasipolynomial.

Pada awal 2017, Babai mencabut klaim semasipolinomial karena beberapa kesalahan serius yang ditemukan oleh Harald Helfgott. Sebagaimana dijelaskan oleh Babai sendiri, kelemahan ini membuat peningkatan lebih sederhana dalam hal waktu berjalan.

Sekitar 5 hari setelah mencabut klaim kuasi-polinomial, Babai memposting pembaruan lain di berandanya dengan alasan bahwa ia telah memperbaiki cacat pada buktinya, memulihkan dengan cara ini waktu kuasi-polinomial berjalan.

Saya harus mengatakan bahwa setelah perubahan cepat ini pada status kebenaran bukti saya biasanya benar-benar mengabaikan makalah baru sampai diterbitkan dalam jurnal yang dihormati.

Tetapi karena Babai adalah Babai, sebagian besar masyarakat menerima perkataannya begitu saja, setidaknya secara publik, meskipun versi baru dari makalah dengan semua koreksi yang diterapkan bahkan tidak tersedia. Perhatikan bahwa orang hebat sekalipun membuat kesalahan dan ada peluang yang tidak dapat diabaikan bahwa perbaikan baru juga memiliki kekurangan dan sebagainya.

Jadi sekarang, bagaimana saya harus mengutip hasil yang baru?

  1. Kutip makalah STOC yang mengklaim upperbound kuasipolinomial.
  2. Mengutip makalah STOC yang menjelaskan bahwa ia memiliki kekurangan yang serius dan waktu berjalan yang sebenarnya meningkatkan batas bawah subeksponensial sebelumnya.
  3. Kutip kertas STOC yang mengatakan bahwa itu memiliki kelemahan yang diperbaiki oleh Babai.
  4. Jangan mengutip sama sekali, dan nyatakan batas atas lama sebagai batas atas yang ditetapkan saat ini.2HAI(n)
graph-isomorphism Tak seorangpun
sumber
8
Saya akan berpikir (1) akan menjadi pilihan yang buruk - mengingat bahwa cacat itu ditunjukkan dan diakui sebagai benar (yaitu, kesalahan asli tidak diperebutkan, tetapi diakui oleh penulis), opsi (1) tidak mencerminkan informasi terbaik yang tersedia saat ini. Selain 2-4, ada opsi lain juga - misalnya Anda bisa memberikan informasi lengkap (keseluruhan cerita seperti di atas), atau Anda bisa mengutip versi STOC tetapi mengatakan versi peer-review lengkap dengan perbaikan cacat yang diketahui belum belum muncul, dan mengutip ikatan terbaik sebelumnya juga.
Joshua Grochow
7
Anda dapat menulis "Babai telah mengumumkan algoritma ...." dan memberikan petunjuk ke situs webnya.
Chandra Chekuri
3
Tergantung pada mengapa Anda mengutip makalahnya. Jika Anda memiliki hasil yang dibangun di atas miliknya, Anda dapat menjadikannya milik Anda bersyarat dan kemudian mengutip makalahnya seperti yang ditulis Chandra. Jika Anda mengutipnya tetapi tidak menggunakannya, Anda dapat mengutipnya lagi seperti yang ditulis Chandra. Dalam kedua kasus, tautan ke posnya atau / dan konsepnya. Siapa pun yang tertarik dapat memeriksa apakah itu benar atau tidak untuk diri mereka sendiri.
Kaveh
7
Tapi saya rasa Babai tidak diperlakukan secara berbeda dari para ahli lain di bidang keahlian mereka, bahwa bagian dari posting Anda tidak bergantung pada pertanyaan tentang bagaimana mengutip klaim atau draft paper yang masih dalam peninjauan. Itu membuat posting Anda terlihat seperti keluhan, jadi saya sarankan menghapusnya. Perbedaan dalam perawatan dibandingkan dengan orang-orang acak yang tidak dikenal yang belum mempublikasikan hasil penting apa pun di lapangan dan karena itu belum membuktikan keahlian apa pun di bidang tersebut dibenarkan seperti di mana pun.
Kaveh
@ Kaveh Saya sangat setuju dengan sudut pandang Kaveh.
Tayfun Bayar

Jawaban:

5

Pertama, saya akan mencegah pengiriman makalah tanpa syarat yang tergantung pada hasil kuasi-polinomial, jika itu yang Anda inginkan kutipannya. Bentuk ulang hasil sebagai persyaratan pada adanya algoritma GI quasi-polinomial dan nyatakan dalam catatan kaki bahwa Babai mungkin telah membuktikan ini tetapi makalah itu tidak tersedia untuk umum. Dalam hal ini, tidak ada kutipan yang diperlukan karena Anda tidak memerlukan hasil untuk kertas.

Dalam konteks lain, saya tidak berpikir itu perlu untuk mengutip makalah yang tersedia - mengutip situs webnya baik-baik saja. Ini sedikit tergantung pada apa yang Anda tulis, tetapi saya akan merekomendasikan menegaskan sesuatu di sepanjang baris "secara luas diyakini bahwa GI dapat dipecahkan dalam waktu quasipolynomial dan bukti dari ini telah diumumkan oleh Laszlo Babai [rujukan ke halaman web di mana ia membuat klaim]. "

Satu keuntungan penting dari mengutip klaim online-nya adalah bahwa situs webnya mengandung kata-katanya sendiri tentang klaim saat ini dan tautan ke pracetaknya.

Stella Biderman
sumber
6
(Saya juga tidak memilih.) Saya tidak begitu yakin saya membeli bahwa bagian pertama dari kalimat Anda (secara luas diyakini bahwa GI ada di QP) adalah benar sebelum pengumuman Babai. Saya pikir sebelum pengumuman Babai, bahkan pendapat tentang apakah GI berada di QP mungkin lebih terbagi daripada, katakanlah, pendapat tentang P vs NP (hanya sebagai titik perbandingan untuk sesuatu yang "dipercaya secara luas"). Setelah pengumuman Babai, saya pikir pendapat masih terbagi pada apakah GI akan berakhir di P.
Joshua Grochow