Śmieszne dokumenty związane z TCS itp.?

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.

Gazeta Scotta Aaronsona: Hierarchia wielomianowa upada: tysiące osób obawiało się, że jest to możliwe

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.

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.

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).

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.

• Złożoność pieśni Dona Knutha
• O superpolinomalnych funkcjach podwykładniczych Alana T. Shermana (nie „Man T. Sherman”, jak sugeruje Biblioteka Cyfrowa ACM).

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.

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.

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ę).

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.

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.

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

Artykuł Mihai Patrascu i Liama ​​Roditty'ego pt. „ Distance Oracles Beyond the Thorup – Zwick Bound ” był początkowo zatytułowany „ Jak wyhodować piłki ” na stronie głównej Mihai :-)

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”.

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 ”.

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.

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.

„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.

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

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

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

Mick dostaje niektóre (kursy są po jego stronie) przez Reed Chvátal i Chvátal Reed (Focs 1992), na zadowolenie (aka spełnialności).

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

Przemówienie Alicji i Boba po obiedzie John Gordon.

Niezła rozmowa o teorii kodowania.

Na inny temat ( Jak sędziować artykuł? ) Znalazłem następujący artykuł:

Graham Cormode. 2009. Jak NIE recenzować artykułu: narzędzia i techniki recenzenta przeciwnika. SIGMOD Rec . 37, 4 (marzec 2009 r.), 100–104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

Miałem dużo zabawy czytając ten artykuł;)

Bruce Reed, Mangoes and Blueberries , Combinatorica 19 (1999) 267-296.

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.

Jeśli chodzi o zabawny tytuł: „Jak grać w kolorowankę przeciwko przeciwnikowi z daltonizmem”

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

A może Scott nie zawsze jest trzeźwy ?

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 ^ _-