Śmieszne dokumenty związane z TCS itp.?

80

Jaka jest najśmieszniejsza opublikowana praca związana z TCS?

Podaj tylko te, które mają być śmieszne. Preferowane są prace, które zostały stworzone z myślą o inteligentnym humorze (zamiast, powiedzmy, opublikowanym zbiorem krótkich dowcipów dotyczących teorii złożoności). Akceptowane są również prace z humorystycznymi (właściwie humorystycznymi, nie tylko uroczymi) tytułami.

Zadaj tylko jedną pracę na odpowiedź, aby „najlepsi” mogli dostać się na szczyt.

Joshua Grochow
źródło
3
co z artykułami o śmiesznych tytułach? czy to powinno być inne pytanie?
Suresh Venkat
4
Myślę, że śmieszne tytuły są w porządku :).
Joshua Grochow
1
Dlaczego tylko złożoność (a nie inne tematy TCS)? Co z książkami? (Chciałbym opublikować konkretną matematykę :))
Kaveh
3
z jakiegoś powodu mathoverflow.net/questions/44326/most-memorable-titles jest ściśle powiązanym wątkiem.
RJK
2
@Suresh: Wierzę, że masz na myśli xxx.lanl.gov/abs/1003.6064v1
Radu GRIGore

Odpowiedzi:

52

Problem papieru toaletowego (Donald Knuth, American Mathematical Monthly, 1984). Od wprowadzenia:

Dozowniki papieru toaletowego w określonym budynku są przeznaczone do przechowywania dwóch rolek chusteczek, a dana osoba może użyć dowolnej rolki. Istnieją dwa rodzaje ludzi, którzy korzystają z pokoi wypoczynkowych w budynku: wybierający duże i mało wybierający. Duży wyborca ​​zawsze bierze kawałek papieru toaletowego z rolki, która jest obecnie większa; mały wyborca ​​zawsze robi coś przeciwnego. Jednak gdy dwie rolki mają ten sam rozmiar lub gdy tylko jedna rolka jest niepusta, wszyscy wybierają najbliższą niepustą rolkę. Gdy obie rolki są puste, każdy ma problem.
chrześcijan
źródło
24
O nie. Knuth mnie pobił. Zastanawiałem się nad pokrewnym, co prawda prostszym pytaniem i przekonałem siebie, że każdy powinien być małym wyborem, aby wspólnie zminimalizować ryzyko (i od tamtej pory jestem jednym z nich). Jednak nigdy nie miałem czasu na zapisanie wyniku. Przynajmniej cieszę się, że znałem wcześniejsze prace, zanim je napisałem i przedłożyłem na Międzynarodową Konferencję na temat toalet teoretycznych.
Tsuyoshi Ito,
5
Pół rygorystyczne spojrzenie na problem wyboru pisuaru z algorytmów POV: blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability
Andy Drucker
38

Kyle Burke i David Charlton. Dolne granice dla prawdopodobnie istnego wielomianu. Boston University, 2005. (Podziękowania dla @arnab i archiwum internetowego za link).

Jestem prawie pewien, że był to artykuł primaaprilisowy, ale tak czy inaczej jest to absolutnie przezabawne. Streszczenie:

Wypełniamy lukę w istniejącej teorii złożoności, wprowadzając klasę prawdopodobnieistycznych wielomianowych obliczeń czasowych, to znaczy obliczeń, które, jak wiesz, prawdopodobnie kończą się w czasie wielomianowym, o ile nam wiadomo. Stosujemy tę klasę, aby pokazać, że algorytmy dla problemów z kompletnym NP prawdopodobnie nie działają w czasie wielomianowym.

Joshua Grochow
źródło
6
Rozumiem! Nie mogę znaleźć linku
arnab
3
Byłem w klasie z Davidem Charltonem w 2002 roku, kiedy był studentem, więc jestem prawie pewien, że musi to być rok 2005, a nie 1995 ;-)
Mugizi Rwebangira,
1
David napisał to jako zabawną odpowiedź na komentarz, który napisałem w szkole. Nie pamiętam dokładnie tego komentarza, ale gazeta jest przezabawna! : -DI nie mogę wziąć żadnego faktycznego uznania za wesołość.
Kyle
30

Andrew W. Appel's „ Czy POPL Matematyka czy nauka?

Ten artykuł analizuje konferencje CS i próbuje sklasyfikować je jako teoretyczne lub stosowane na podstawie tego, czy autorzy uporządkują swoje nazwiska w kolejności alfabetycznej (teoretycznej) czy według wkładu (zastosowanego).

Robin Kothari
źródło
4
Uwielbiam zakończenie: „Celem badań przedstawionych w tym raporcie było rozśmieszenie POPL '92; cieszę się, że pod tym względem badania były całkowicie udane”.
Dave Clarke,
Chciałbym, aby trwało to do dnia dzisiejszego
Thomas Ahle,
24

Kilka artykułów Jean-Yvesa Girarda .

Jego artykuł Linear Logic ma następujący przypis redaktora czasopisma Theoretical Computer Science:

Ze względu na swoją długość i nowość ten artykuł nie został poddany zwykłemu procesowi sędziowania. Redaktor jest gotowy podzielić się z autorem wszelką krytykę dotyczącą tej pracy.

Kolejnym jest Locus Solum, od reguł logiki do logiki reguł . 192-stronicowy artykuł ma dodatek o długości prawie 100 stron, zatytułowany „ Czysta strata papieru ”, najśmieszniejszy dodatek, jaki kiedykolwiek widziałem.

Kaveh
źródło
12
Fantastycznie dziwne jest to, że „Czysta strata papieru” jest naprawdę bardzo dobra. Nie możesz naiwnie ufać cokolwiek, co w nim pisze, ale jednak istnieje poważna uwaga na temat logiki ukrytej w prawie każdym dowcipie / zniewadze / na bok.
Neel Krishnaswami,
3
Czytelnicy mówiący po francusku mogą cieszyć się jego referatem na temat zegarków musztardowych
Gallais
1
Niestety trzeci link jest zepsuty
maks.
3
@gallais: Właściwie oryginalna wersja „Zegarków musztardowych” jest w języku angielskim i można ją znaleźć tutaj .
Damiano Mazza
1
To jest „poprawka” do linku w głównej odpowiedzi: iml.univ-mrs.fr/~girard/0.pdf
apnorton
22

Artykuł Yonatana Bilu, Dany Porrat i Yoav Yaffe „ O liczbie prezerwatyw w taniej orgii bezpiecznego seksu ”. Ten artykuł nie został opublikowany, więc nie odpowiada jednemu z wymagań (do opublikowania pracy). Ale myślę, że można to tutaj włączyć jako wyjątek.

Oleksandr Bondarenko
źródło
Myślę, że może to być związane: mathworld.wolfram.com/GloveProblem.html
RJK
4
@Oleksander: Wymóg „opublikowany” nie miał być ścisły, ale miał na celu oddzielić rzeczy takie jak artykuły i książki od, powiedzmy, pasków z kreskówek (w przeciwnym razie ten wątek zostałby wypełniony odnośnikami xkcd.)
Joshua Grochow
W podobnym duchu: Trójkąty, zwyrodnienia i trójkąty miłosne Grønlunda i Pettie. To naprawdę poważny papier o drobnej złożoności, a żart w tytule jest wymuszony.
kinokijuf
20

W rzeczywistości istnieje cały dziennik, który ma być zabawny. Czasopismo craptology . Tematy są zwykle związane z kryptografią. Są też filmy z sesji (!)

Jednym z przykładów jest artykuł z kryptografii tomu 4 we wszechświecie autostopowicza (część 5):

Nadchodzące atrakcje

Jeśli podobała Ci się nasza prezentacja, z przyjemnością usłyszysz o nadchodzących atrakcjach tego samego autora:

- Kryptoanaliza systemów interaktywnych protokołów ludzkich. Kontrowersyjna kryptoanaliza pracy Shakiry [4], która dowodzi, że HIPS faktycznie kłamią.

- Wiedza anty-zero. System protokołów, który ujawnia wszystko, co wie dowcipiciel, z wyjątkiem tego, co weryfikator chce usłyszeć. Większość serwisów infolinii dla klientów opracowało ad hoc protokoły o zerowej wiedzy.

- Rozkład klucza kwantowego oparty na zjawiskach społecznych. W tym artykule pokazano, jak dystrybuować klucze przy użyciu technik kwantowych, ale bez użycia obiektów kwantowych. Zamiast używać obiektów kwantowych, protokół wykorzystuje niepewność, jaką ma mężczyzna w kwestii tego, czy jego pierwszy wieczór z kobietą liczy się jako data, czy nie, aby przekazać klucze.

rev. M. Alaggan
źródło
17

Konkretna matematyka: podstawa informatyki , Ronald Graham, Donald Knuth i Oren Patashnik.

Niesamowita książka z mnóstwem zabawnych notatek. :) (Patrz również DEK „s GKP stronę).

Kaveh
źródło
4
Boczne notatki są rzeczywiście zabawne, ale książka jest „po prostu przyjemna” - oczywiście, nie każdy może napisać przyjemną książkę ;-) W każdym razie nie wiem, czy kwalifikuje się jako zabawna praca, ale dostajesz mój głos, ponieważ Bardzo lubię tę książkę.
Anthony Labarre,
1
To moja ulubiona książka. Dziwi mnie, że więcej autorów nie zastosowało się do ich formatu.
Chad Brewbaker
17

Poleciłbym przetwarzanie FUN: Międzynarodowej Konferencji Zabawy Z Algorytmami.

Muszę powiedzieć, że „Twardość gry Lemmings, czy też nie, więcej dowodów na kompletność NP” Grahama Cormode jest jednym z moich ulubionych.

Swann Perarnau
źródło
2
Właśnie znalazłem postępowanie FUN 2007 w książkach Powella w zeszłym tygodniu - całym sercem popieram to zalecenie! Doskonałe wyniki sortowania pesymalnego i najgorsze możliwe algorytmy stronicowania.
Steven Stadnicki
16

Don Knuth's Propozycja terminologiczna . SIGACT News, 6 (1), 1974. Wspomniany na blogu złożoności. Najwyraźniej w tym miejscu mamy pojęcia „NP-complete” i „NP-hard”.

Jednym z moich ulubionych z tego utworu jest sugestia Alberta Meyera, że ​​to, co nazywamy teraz problemami NP-trudnymi, nazywa się Hard-as-Satisfiable, lub trudnym jak-S w skrócie.

Joshua Grochow
źródło
14

Sprawdź rysunek, który towarzyszy 1-stronicowemu artykułowi SODA Adama Kalai, „Łatwe generowanie losowych liczb faktograficznych”: link

Aaron Roth
źródło
12

A. Broder, J. Stolfi „ Algorytmy pesymalne i analiza prostoliniowości”, ACM SIGACT News 16 (3), jesień 1984 r.

Artykuł przedstawia „zupełnie nową gałąź informatyki, projektowanie i analizę algorytmów niechętnych. Intuicyjnie algorytm niechętny dla problemu P to taki, który marnuje czas w sposób, który jest wystarczająco spreparowany, aby oszukać naiwnego obserwatora”.

Hermann Gruber
źródło
9

Parlament w niepełnym wymiarze godzin Lamport dokonał przełomu w dziedzinie przetwarzania rozproszonego, ale artykuł był tak (celowo!) Zaciemniony, że ludzie nie mogli go zrozumieć - o ile mi wiadomo, jego opublikowanie zajęło mu około 10 lat (byli redaktorzy) w zaciemnionej formie. Ostatecznie Lamport kontynuował Paxos Made Simple , który miał następujące streszczenie: „ Algorytm Paxos, gdy jest przedstawiony w prostym języku angielskim, jest bardzo prosty ”.

Lev Reyzin
źródło
9

Stowarzyszenie herezji obliczeniowej w CMU ma wiele z nich, które są prezentowane na dorocznej konferencji SIGBOVIK (następnie 04/01/2011). Moim ulubionym jest:

Podejście oparte na kradzieży do akwizycji obiektów 3d.

użytkownik2333
źródło
8

W tym samym duchu, co post Murilo da Silvy, nie mogę się oprzeć opublikowaniu tego fragmentu Goupila i Schaefera „Faktoring N-cykli i liczenie map danego rodzaju” :

Po tym dowodzie zachęcamy czytelnika do przerwania i cieszenia się lżejszą aktywnością, taką jak obserwowanie ptaków lub ogrodnictwo, przed kontynuowaniem czytania.

Anthony Labarre
źródło
7

„Wyrafinowanie w państwowym formalizmie” Lamport.

Nasz przyjaciel, który był genialnym matematykiem, został hospitalizowany z powodu długotrwałego nadużywania środków halucynogennych. Postanawiamy dać mu cyfrowy zegar do jego pokoju. Jednak jego lekarz sugeruje, że wyświetlanie godzin i minut razem może być zbyt mylące. Tak więc nakładamy taśmę na wyświetlacz minut, zmieniając nasz prezent w cyfrowy zegar godzinowy.

Marcus Ritt
źródło
7

Właśnie odkryłem „List od sfrustrowanego autora gazety” . Niezła lektura ;-)

Anthony Labarre
źródło
1
Zbyt wiele słyszałem o tych procesach, by od razu odrzucić list jako satyrę. Zastanawiam się jednak, czy tak jest. W przeciwnym razie się boję.
Raphael
6

W pewnym momencie natknąłem się na „News Theory złożoności” i pomyślałem, że to całkiem zabawne.

Ryan Williams
źródło
Miły! Praca nad nimi służy również jako miły odświeżacz w niektórych klasycznych wynikach złożoności.
András Salamon
6

Najnowsze śmieszne tytuły:

  • A. Kehagias, P. Pralat, Kilka uwag na temat gliniarzy i pijanych rabusiów , Theoretical Computer Science 463 (2012) 133-147, DOI

  • A. Kehagias, D. Mitsche, P. Pralatb, Gliny i niewidzialni rabusie: Koszt pijaństwa , Teoretyczna informatyka (2013), w prasie

  • Natasha Komarov, Peter Winkle, Capturing the Drunk Robber on a Graph , maj 2013, arXiv: 1305.4559

użytkownik13136
źródło
6

Ile szkód może wyrządzić zły recenzent? Zabawne fikcyjne recenzje znanych starych artykułów z CS.

Diego de Estrada
źródło
Link jest martwy i nie mogłem znaleźć papieru za pomocą szybkiego wyszukiwania w Google. Czy mógłbyś go gdzieś ponownie załadować?
tranisstor
5

Przemówienie Alicji i Boba po obiedzie John Gordon.

Niezła rozmowa o teorii kodowania.

Jagadish
źródło
To zabawne, jak wiele z tego, co według niego mógłby zrobić jego kieszonkowy kalkulator, jest obecnie możliwe na nowoczesnym smartfonie. Nie ma jeszcze wyświetlaczy holograficznych 3D i być może będziesz
musiał
4

Nie mogę teraz myśleć o śmiesznym papierze, ale pamiętam „normalny” papier, który zawierał zabawną linię. W rzeczywistości było to pierwsze zdanie w części 1. Autorzy rozpoczęli pracę od:

„W przeciwieństwie do naszej zwykłej praktyki, czujemy się zobowiązani do rozpoczęcia tego dokumentu kilkoma definicjami”. Więc pozwól G ... ”

Tytuł artykułu to „ $beta$-doskonałe wykresy” autorstwa Markossiana, Gaspariana i Reeda w 1996 r. Zwrócił moją uwagę, ponieważ w rzeczywistości jest to kluczowy artykuł na temat idealnej teorii grafów, w którym zdefiniowano klasę wykresów beta-doskonałych, klasa, która jest w pewnym sensie analogiczna do idealnych wykresów (wykresy beta idealne są podklasą wykresów bez dziur, a doskonałe wykresy są podklasą wykresów bez dziur.

Murilo da Silva
źródło
Znany również jako „Ponieważ jest to wykład teoretyczny, zacznę od zdefiniowania problemu, o którym mówię ...”
Sariel Har-Peled
3

Lambda the Ultimate zwrócił moją uwagę na oficjalny artykuł na temat fosforu, popularnego Lisp , który, jeśli „Popular Lisp” cię nie zdradził, jest satyryczny ^ _-

paul.meier
źródło