Makalah terkait TCS lucu dll?

Apa karya terbitan terkait TCS terlucu yang Anda tahu?

Harap sertakan hanya yang dimaksudkan untuk menjadi lucu. Karya-karya yang secara eksplisit dibuat untuk menjadi humor cerdas (daripada, katakanlah, kumpulan lelucon singkat tentang teori kompleksitas) lebih disukai. Karya dengan judul lucu (sebenarnya lucu, tidak hanya lucu) juga diterima.

Harap hanya satu pekerjaan per jawaban sehingga yang "terbaik" dapat menggelembung ke atas.

Koran Scott Aaronson: Hirarki polinomial runtuh: ribuan dikhawatirkan bisa dituruti

Masalah Kertas Toilet (Donald Knuth, American Mathematical Monthly, 1984). Dari pendahuluan:

Dispenser kertas toilet di bangunan tertentu dirancang untuk menampung dua gulungan tisu, dan seseorang dapat menggunakan salah satu gulungan tersebut. Ada dua jenis orang yang menggunakan kamar kecil di gedung: pemilih besar dan pemilih kecil. Pemilih besar selalu mengambil selembar kertas toilet dari gulungan yang saat ini lebih besar; pemilih kecil selalu melakukan yang sebaliknya. Namun, ketika kedua gulungan memiliki ukuran yang sama, atau ketika hanya satu gulungan yang kosong, semua orang memilih gulungan kosong yang terdekat. Saat kedua gulungan kosong, semua orang memiliki masalah.

Kyle Burke dan David Charlton. Batas bawah untuk waktu polinomial mungkin-istic. Boston University, 2005. (Terima kasih kepada @arnab dan Web Archive untuk tautannya.)

Saya cukup yakin ini adalah makalah April Mop, tapi bagaimanapun juga itu benar - benar lucu. Abstrak:

Kami mengisi celah dalam teori kompleksitas yang ada dengan memperkenalkan kelas perhitungan waktu polinomial yang mungkinistik, yaitu, perhitungan yang, Anda tahu, mungkin berakhir dalam waktu polinomial, sejauh yang kami tahu. Kami menerapkan kelas ini untuk menunjukkan bahwa algoritma untuk masalah NP-complete mungkin tidak berjalan dalam waktu polinomial.

Andrew W. Appel " Is POPL Mathematics or Science? "

Makalah ini mempelajari berbagai konferensi CS dan mencoba untuk mengklasifikasikannya sebagai teori atau diterapkan berdasarkan apakah penulis memesan nama mereka dalam urutan abjad (teoretis) atau dengan kontribusi (diterapkan).

Beberapa surat kabar Jean-Yves Girard .

-Nya Linear Logic kertas memiliki catatan kaki berikut dengan editor Theoretical jurnal Ilmu Komputer:

Karena panjang dan kebaruan makalah ini belum mengalami proses refereeing yang normal. Editor siap untuk berbagi dengan penulis kritik apa pun yang pada akhirnya akan diungkapkan mengenai karya ini.

Satu lagi adalah Locus Solum, Dari aturan logika hingga logika aturan . Makalah 192 halaman memiliki lampiran yang hampir 100 halaman panjang bernama " A murni kertas ", lampiran terlucu yang pernah saya lihat.

• Kompleksitas Lagu oleh Don Knuth
• Tentang Fungsi Subeksponensial Superpolinomial oleh Alan T. Sherman (bukan "Man T. Sherman" seperti yang disarankan oleh Perpustakaan Digital ACM).

Makalah karya Yonatan Bilu, Dana Porrat dan Yoav Yaffe " Tentang Jumlah Kondom di Pesta Seks Aman yang Murah ". Makalah ini tidak diterbitkan, jadi tidak sesuai dengan salah satu persyaratan (karya yang akan diterbitkan). Tapi saya pikir itu bisa dimasukkan di sini sebagai pengecualian.

Bahkan ada jurnal lengkap yang dimaksudkan untuk menjadi lucu. The jurnal craptology . Topik biasanya terkait dengan kriptografi. Ada juga beberapa video sesi (!)

Salah satu contoh adalah kertas Volume 4 Kriptografi dalam Semesta Hitchhiker (bagian 5) adalah:

Atraksi Datang

Jika Anda menikmati presentasi fitur kami, Anda akan senang mendengar tentang atraksi yang akan datang oleh penulis yang sama:

- The cryptanalysis Sistem Protokol Interaktif Manusia. Sebuah analisis kriptografi kontroversial dari makalah Shakira [4] yang membuktikan bahwa HIPS memang berbohong.

- Anti-zero-knowledge. Suatu sistem protokol yang mengungkapkan segala sesuatu yang diketahui oleh seorang pepatah kecuali yang ingin didengar oleh verifier. Protokol anti-nol-pengetahuan ad-hoc telah dikembangkan oleh sebagian besar layanan bantuan pelanggan.

- Distribusi kunci kuantum berdasarkan fenomena sosial. Makalah ini menunjukkan bagaimana mendistribusikan kunci menggunakan teknik kuantum tetapi tanpa menggunakan objek kuantum. Alih-alih menggunakan objek kuantum, protokol malah menggunakan ketidakpastian yang dimiliki pria mana pun tentang apakah malam pertamanya dengan seorang wanita dianggap sebagai kencan atau tidak untuk mengirimkan kunci.

Matematika Konkret: Yayasan Ilmu Komputer , oleh Ronald Graham, Donald Knuth, dan Oren Patashnik.

Buku luar biasa dengan banyak catatan sisi lucu. :) (Lihat juga DEK 's GKP halaman.)

Saya akan merekomendasikan proses FUN: Konferensi Internasional tentang Kesenangan dengan Algoritma.

Saya harus mengatakan bahwa "Hardness of the Lemmings game, atau Oh tidak, lebih banyak bukti kelengkapan NP" oleh Graham Cormode adalah salah satu favorit saya.

Don Knuth's A proposal terminologis . SIGACT News, 6 (1), 1974. Disebutkan di The Complexity Blog. Di sinilah kami mendapatkan istilah "NP-complete" dan "NP-hard."

Salah satu favorit saya dari karya ini adalah saran Albert Meyer bahwa apa yang sekarang kita sebut masalah NP-hard disebut Hard-as-Satisfiability, atau hard-as-S singkatnya.

Lihatlah gambar yang menyertai 1 halaman makalah SODA Adam Kalai, "Menghasilkan Angka Acak, Mudah,": tautan

Makalah Mihai Patrascu dan Liam Roditty tentang " Distance Oracles Beyond the Thorup – Zwick Bound " awalnya berjudul " Cara menumbuhkan bola " di beranda Mihai :-)

A. Broder, J. Stolfi " Algoritma Pessimal dan analisis kesederhanaan ", ACM SIGACT News 16 (3), Fall 1984.

Makalah ini memperkenalkan "cabang yang sama sekali baru dari Ilmu Komputer, desain dan analisis algoritma enggan. Secara intuitif, algoritma enggan untuk masalah P adalah yang menghabiskan waktu dengan cara yang cukup dirancang untuk menipu pengamat yang naif."

Paruh Waktu Parlemen Lamport membuat terobosan dalam komputasi terdistribusi, tetapi makalah itu (sengaja!) Dikaburkan sehingga orang tidak bisa memahaminya - sejauh yang saya tahu, butuh waktu sekitar 10 tahun untuk menerbitkannya (editor masa lalu) dalam bentuknya yang dikaburkan. Akhirnya Lamport menindaklanjuti dengan Paxos Made Simple , yang memiliki abstrak sebagai berikut: " Algoritma Paxos, ketika disajikan dalam bahasa Inggris yang sederhana, sangat sederhana ."

Asosiasi untuk Kesesatan Komputasi di CMU memiliki beberapa di antaranya, yang dipresentasikan pada konferensi tahunan SIGBOVIK (selanjutnya diadakan 04/01/2011). Favorit pribadi saya adalah:

Pendekatan berbasis pencurian untuk akuisisi objek 3d.

Dengan semangat yang sama dengan tulisan Murilo da Silva, saya tidak dapat menahan posting kutipan ini dari Goupil dan Schaefer "Siklus N-Siklus dan Menghitung Peta Genus Yang Diberikan" :

Setelah bukti ini, kami mendorong pembaca untuk berhenti sejenak dan menikmati kegiatan yang lebih ringan seperti mengamati burung atau berkebun sebelum melanjutkan membaca.

"Perbaikan dalam Formalisme Berbasis Negara" oleh Lamport.

Seorang teman kami, yang merupakan ahli matematika yang brilian, telah dirawat di rumah sakit karena penyalahgunaan obat-obatan halusinogen jangka panjang. Kami memutuskan untuk memberinya jam digital untuk kamarnya. Namun, dokternya menyarankan bahwa jam dan menit yang ditampilkan bersama mungkin terlalu membingungkan. Jadi, kami menempelkan pita pada tampilan menit, mengubah hadiah kami menjadi jam digital.

Saya baru saja menemukan "Sepucuk surat dari penulis jurnal yang frustrasi" . Bagus dibaca ;-)

Saya menemukan "Complexity Theory Newsflash" di beberapa titik, dan berpikir itu cukup lucu.

Judul lucu terbaru:

• A. Kehagias, P. Pralat, Beberapa komentar pada polisi dan perampok mabuk , Ilmu Komputer Teoritis 463 (2012) 133-147, DOI

• A. Kehagias, D. Mitsche, P. Pralatb, Polisi dan Perampok yang tidak terlihat: Biaya kemabukan , Ilmu Komputer Teoritis (2013), dalam Pers

• Natasha Komarov, Peter Winkle, Menangkap Perampok yang Mabuk dalam Grafik , Mei 2013, arXiv: 1305.4559

Mick mendapat beberapa (kemungkinan ada di pihaknya) oleh Reed Chvatal dan Chvatal Reed (FOCS 1992), pada kepuasan (alias satisfiability).

Berapa banyak kerusakan yang bisa disebabkan oleh peer reviewer mengalami hari yang buruk? Ulasan fiksi yang lucu dari makalah CS tua yang terkenal.

Pidato Alice dan Bob After Dinner oleh John Gordon.

Pembicaraan yang menyenangkan tentang teori pengkodean.

Pada topik lain ( Bagaimana saya menulis makalah? ), Saya menemukan makalah berikut:

Graham Cormode. 2009. Bagaimana TIDAK untuk meninjau makalah: alat dan teknik pengulas permusuhan. SIGMOD Rec . 37, 4 (Maret 2009), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

Saya senang membaca makalah ini;)

Bruce Reed, Mangga dan Blueberry , Combinatorica 19 (1999) 267-296.

Saya tidak bisa memikirkan kertas lucu sekarang, tetapi saya ingat kertas "normal" yang memiliki garis lucu di dalamnya. Itu sebenarnya kalimat pertama dalam Bagian 1. Penulis memulai makalah dengan:

"Bertentangan dengan praktik kami yang biasa, kami merasa berkewajiban untuk memulai makalah ini dengan beberapa definisi". Jadi biarkan G ... "

Judul makalah ini adalah " $beta$-perfect graphs", oleh Markossian, Gasparian dan Reed pada tahun 1996. Itu menarik perhatian saya karena pada kenyataannya ini adalah makalah kunci tentang teori graf sempurna, di mana ia didefinisikan sebagai kelas grafik beta-sempurna, kelas yang analog dengan grafik sempurna (grafik beta-sempurna menjadi subkelas dari grafik bebas lubang EVEN, sedangkan grafik sempurna adalah subkelas dari grafik bebas-lubang ODD.

Sejauh judul lucu: "Cara bermain game mewarnai melawan musuh buta warna"

http://portal.acm.org/citation.cfm?id=1137865

Bagaimana dengan Scott yang tidak selalu sadar ?

Lambda the Ultimate mengingatkan saya pada kertas putih tentang Fosforus, Lisp Populer , yang jika "Popular Lisp" tidak memberi tip kepada Anda, menyebalkan ^ _-