Lustige TCS-bezogene Papiere etc?

80

Was ist das lustigste veröffentlichte Werk zum Thema TCS, das Sie kennen?

Bitte geben Sie nur diejenigen an, die lustig sein sollen. Es werden Werke bevorzugt, die explizit so gestaltet sind, dass sie auf intelligente Weise humorvoll sind (und nicht etwa eine veröffentlichte Sammlung von kurzen Witzen in Bezug auf die Komplexitätstheorie). Arbeiten mit humorvollen (eigentlich humorvollen, nicht nur süßen) Titeln werden ebenfalls akzeptiert.

Bitte nur eine Arbeit pro Antwort, damit die "besten" nach oben sprudeln können.

Joshua Grochow
quelle
3
Was ist mit Papieren mit lustigen Titeln? oder sollte das eine andere frage sein?
Suresh Venkat
4
Ich denke, lustige Titel sind in Ordnung :).
Joshua Grochow
1
Warum nur Komplexität (und nicht andere TCS-Themen)? Was ist mit Büchern? (Ich würde gerne Concrete Mathematics posten :))
Kaveh
3
Aus irgendeinem Grund ist mathoverflow.net/questions/44326/most-memorable-titles ein eng verwandter Thread.
RJK
2
@ Suresh: Ich glaube du meinst xxx.lanl.gov/abs/1003.6064v1
Radu GRIGore 18.11.10

Antworten:

72

Scott Aaronsons Zeitung: Polynomial Hierarchie bricht zusammen: Tausende fürchteten, sie könnten verfolgt werden

Joshua Grochow
quelle
2
Urkomisch. Das hatte ich noch nie gesehen.
Derrick Stolee 18.11.10
7
Eine verwandte tragische (oder lustige?) Schlagzeile: THE SKY IS FALLING (Die starke exponentielle Hierarchie bricht zusammen) , ein technischer Bericht von L. Hemachandra. Die folgende Fußnote wird an den Titel angehängt: "Huhn wenig dachte, dass der Himmel fiel. Es war nicht."
Alessandro Cosentino
52

Das Toilettenpapierproblem (Donald Knuth, American Mathematical Monthly, 1984). Aus der Einleitung:

Die Toilettenpapierspender in einem bestimmten Gebäude sind für die Aufnahme von zwei Taschentuchrollen ausgelegt, und eine Person kann jede Rolle verwenden. Es gibt zwei Arten von Menschen, die die Ruheräume im Gebäude benutzen: große und kleine. Ein Big-Choser nimmt immer ein Stück Toilettenpapier von der aktuell größeren Rolle. ein kleiner wähler macht immer das gegenteil. Wenn jedoch die beiden Rollen dieselbe Größe haben oder wenn nur eine Rolle nicht leer ist, wählt jeder die nächste nicht leere Rolle aus. Wenn beide Rollen leer sind, hat jeder ein Problem.
Christian
quelle
24
Ach nein. Knuth hat mich geschlagen. Ich hatte über eine verwandte, zugegebenermaßen einfachere Frage nachgedacht und mich davon überzeugt, dass jeder eine kleine Entscheidung treffen sollte, um das Risiko kooperativ zu minimieren (und seitdem bin ich eine). Ich hatte jedoch nie Zeit, das Ergebnis aufzuschreiben. Zumindest bin ich froh, die Vorarbeiten zu kennen, bevor ich sie aufschreibe und der Internationalen Konferenz für Theoretische Toiletten vorlege.
Tsuyoshi Ito
5
Das Problem der Urinalselektion
Andy Drucker
38

Kyle Burke und David Charlton. Untergrenzen für die wahrscheinlich-istische Polynomzeit. Boston University, 2005. (Vielen Dank an @arnab und das Webarchiv für den Link.)

Ich bin mir ziemlich sicher, dass dies eine Aprilscherz-Zeitung war, aber so oder so ist es absolut lustig. Die Zusammenfassung:

Wir schließen eine Lücke in der bestehenden Komplexitätstheorie, indem wir die Klasse der wahrscheinlichen Polynomzeitberechnungen einführen, dh Berechnungen, die, wie Sie wissen, nach unserem Kenntnisstand wahrscheinlich in der Polynomzeit enden. Wir wenden diese Klasse an, um zu zeigen, dass Algorithmen für NP-vollständige Probleme wahrscheinlich nicht in Polynomzeit ausgeführt werden.

Joshua Grochow
quelle
6
Verstanden! Ich kann es nicht von einer vorhandenen Webseite verlinkt, aber Sie können es hier abrufen: web.archive.org/web/20080211140314/http://cs-people.bu.edu/...
arnab
3
Ich war in einer Klasse mit David Charlton im Jahr 2002, als er ein Bachelor war, also bin ich mir ziemlich sicher, dass es 2005 nicht 1995 sein
muss ;-)
1
David schrieb dies als eine lustige Antwort auf einen Kommentar, den ich in der Grundschule machte. Ich erinnere mich nicht genau an meinen Kommentar, aber das Papier ist witzig! : -DI kann die Heiterkeit nicht wirklich würdigen.
Kyle
30

Andrew W. Appels " Ist POPL Mathematik oder Wissenschaft? "

Diese Papierstudien variieren CS-Konferenzen und versuchen, sie als theoretisch oder angewendet zu klassifizieren, basierend darauf, ob Autoren ihre Namen in alphabetischer Reihenfolge (theoretisch) oder nach Beitrag (angewendet) sortieren.

Robin Kothari
quelle
4
Ich liebe das Ende "Das Ziel der in diesem Bericht vorgestellten Forschung war es, POPL '92 zum Lachen zu bringen. Ich bin froh zu sagen, dass die Forschung in dieser Hinsicht vollkommen erfolgreich war."
Dave Clarke
Ich würde gerne sehen, dass dies bis heute so bleibt
Thomas Ahle
24

Mehrere Papiere von Jean-Yves Girard .

Sein Artikel über lineare Logik enthält die folgende Fußnote des Herausgebers der Zeitschrift Theoretical Computer Science:

Aufgrund seiner Länge und Neuheit wurde dieses Papier nicht dem normalen Prozess des Schiedsrichtens unterworfen. Der Herausgeber ist bereit, dem Autor jegliche Kritik mitzuteilen, die eventuell zu diesem Werk geäußert wird.

Ein anderes ist Locus Solum, Von den Regeln der Logik zur Logik der Regeln . Das 192-seitige Papier enthält einen fast 100-seitigen Anhang mit dem Titel " Eine reine Verschwendung von Papier ", den witzigsten Anhang, den ich je gesehen habe.

Kaveh
quelle
12
Das fantastisch Seltsame ist, dass "Eine reine Verschwendung von Papier" wirklich sehr gut ist. Man kann nichts naivem vertrauen, was er darin schreibt, aber trotzdem steckt in fast jedem Witz / Beleidigung / Nebeneffekt ein ernster Punkt in der Logik.
Neel Krishnaswami
3
Französisch sprechende Leser können seine Zeitung auf
Senfuhren
1
Leider ist der dritte Link kaputt
Max
3
@gallais: Die Originalversion des Papiers "Mustard watches" ist in englischer Sprache und hier zu finden .
Damiano Mazza
1
Dies ist der "Fix" für den Link in der Hauptantwort: iml.univ-mrs.fr/~girard/0.pdf
apnorton
22

Die Zeitung von Yonatan Bilu, Dana Porrat und Yoav Yaffe " Über die Anzahl der Kondome bei einer billigen Orgie mit sicherem Sex ". Dieser Artikel wurde nicht veröffentlicht, entspricht also nicht einer der Anforderungen (zu veröffentlichende Arbeit). Aber ich denke, es kann hier ausnahmsweise aufgenommen werden.

Oleksandr Bondarenko
quelle
Ich denke, das könnte damit zusammenhängen: mathworld.wolfram.com/GloveProblem.html
RJK
4
@Oleksander: Die "veröffentlichte" Anforderung sollte nicht streng sein, sondern Dinge wie Artikel und Bücher von beispielsweise Comic-Streifen trennen (andernfalls würde dieser Thread mit xkcd-Referenzen gefüllt sein.)
Joshua Grochow,
In ähnlicher Weise: Dreier, Entartete und Liebesdreiecke von Grønlund und Pettie. Es ist wirklich eine seriöse Arbeit in feinkörniger Komplexität, und der Witz im Titel ist erzwungen.
Kinokijuf
20

In der Tat gibt es eine ganze Zeitschrift, die lustig sein soll. Die Zeitschrift für Kraptologie . Die Themen beziehen sich in der Regel auf die Kryptographie. Es gibt auch einige Sitzungsvideos (!)

Ein Beispiel für die Veröffentlichung von Band 4 der Kryptographie in einem Per Anhalter durchgeführten Universum (Abschnitt 5) ist:

Kommende Attraktionen

Wenn Ihnen unsere Feature-Präsentation gefallen hat, freuen Sie sich über bevorstehende Attraktionen desselben Autors:

- Die Kryptoanalyse menschlicher interaktiver Protokollsysteme. Eine kontroverse Kryptoanalyse der Arbeit von Shakira [4], die beweist, dass HIPS tatsächlich lügt.

- Anti-Null-Wissen. Ein Protokollsystem, das alles enthüllt, was ein Prüfer weiß, außer dem, was der Prüfer hören möchte. Ad-hoc-Protokolle gegen Null-Wissen wurden von den meisten Kundenberatungsdiensten entwickelt.

- Quantenschlüsselverteilung basierend auf sozialen Phänomenen. In diesem Artikel wird gezeigt, wie Schlüssel mithilfe von Quantentechniken, jedoch ohne Verwendung von Quantenobjekten, verteilt werden. Anstatt Quantenobjekte zu verwenden, verwendet das Protokoll stattdessen die Unsicherheit, die ein Mann hat, ob sein erster Abend mit einer Frau als Datum gilt oder nicht, um die Schlüssel zu übermitteln.

M. Alaggan
quelle
17

Konkrete Mathematik: Eine Stiftung für Informatik von Ronald Graham, Donald Knuth und Oren Patashnik.

Ein tolles Buch mit vielen lustigen Randnotizen. :) (Siehe auch die GKP- Seite von DEK .)

Kaveh
quelle
4
Die Randnotizen sind in der Tat lustig, aber das Buch ist "einfach nur unterhaltsam" - zugegeben, nicht jeder kann ein unterhaltsames Buch schreiben ;-) Wie auch immer, ich weiß nicht, ob es sich um ein lustiges Werk handelt, aber du bekommst meine Stimme dafür Ich mag das Buch so sehr.
Anthony Labarre
1
Das ist mein Lieblingsbuch. Ich bin erstaunt, dass mehr Autoren nicht ihrem Format gefolgt sind.
Chad Brewbaker
17

Ich würde die Verarbeitung von FUN empfehlen: die Internationale Konferenz über Spaß mit Algorithmen.

Ich muss sagen, dass "Die Härte des Lemmings-Spiels oder Oh nein, mehr NP-Vollständigkeitsnachweise" von Graham Cormode einer meiner Favoriten ist.

Swann Perarnau
quelle
2
Ich habe das FUN-Verfahren 2007 letzte Woche in Powells Büchern gefunden - ich bin dieser Empfehlung von ganzem Herzen gefolgt! Einige großartige Ergebnisse bei der pessimalen Sortierung und den schlechtesten Paging-Algorithmen.
Steven Stadnicki
16

Don Knuths Ein terminologischer Vorschlag . SIGACT News, 6 (1), 1974. Erwähnt im Complexity Blog. Hier haben wir anscheinend die Begriffe "NP-komplett" und "NP-hart".

Einer meiner Favoriten aus diesem Stück ist Albert Meyers Vorschlag, das, was wir jetzt NP-harte Probleme nennen, Hard-as-as-Satisfiability oder kurz Hard-as-S zu nennen.

Joshua Grochow
quelle
14

Schauen Sie sich die Abbildung an, die Adam Kalais 1-seitigem SODA-Artikel "Generieren von Zufallszahlen auf einfache Weise" beigefügt ist: Link

Aaron Roth
quelle
12

A. Broder, J. Stolfi " Pessimalalgorithmen und Simplexitätsanalyse ", ACM SIGACT News 16 (3), Herbst 1984.

Der Aufsatz stellt "einen völlig neuen Zweig der Informatik vor, das Entwerfen und Analysieren von widerstrebenden Algorithmen. Intuitiv ist ein widerstrebender Algorithmus für ein Problem P einer, der Zeit auf eine Weise verschwendet, die ausreicht, um einen naiven Beobachter zum Narren zu halten."

Hermann Gruber
quelle
9

Lamports Teilzeitparlament erzielte einen Durchbruch in Sachen verteiltes Rechnen, aber die Zeitung war so (absichtlich!) Verschleiert, dass die Leute es nicht verstehen konnten - soweit ich weiß, brauchte er ungefähr 10 Jahre, um es zu veröffentlichen (frühere Herausgeber). in seiner verschleierten Form. Schließlich folgte Lamport mit Paxos Made Simple , das die folgende Zusammenfassung hatte: " Der Paxos-Algorithmus ist, wenn er in einfachem Englisch dargestellt wird, sehr einfach ."

Lev Reyzin
quelle
9

Die Association for Computational Heresy an der CMU hat eine Reihe von diesen, die auf der jährlichen SIGBOVIK- Konferenz (nächste statt 01.04.2011) vorgestellt werden. Mein persönlicher Favorit ist:

Ein diebstahlbasierter Ansatz zur Erfassung von 3D-Objekten.

user2333
quelle
7

"Verfeinerung im Staatsformalismus" von Lamport.

Ein Freund von uns, der ein brillanter Mathematiker war, wurde ins Krankenhaus eingeliefert, weil er halluzinogene Medikamente über einen längeren Zeitraum missbraucht hatte. Wir beschließen, ihm eine Digitaluhr für sein Zimmer zu geben. Sein Arzt schlägt jedoch vor, dass die Stunden- und Minutenanzeige zusammen zu verwirrend sein könnten. Also haben wir die Minutenanzeige mit Klebeband versehen und unser Geschenk in eine digitale Stundenuhr verwandelt.

Marcus Ritt
quelle
6

Irgendwann bin ich auf den "Complexity Theory Newsflash" gestoßen und fand ihn ziemlich lustig.

Ryan Williams
quelle
Nett! Das Durcharbeiten dieser dient auch als nette Auffrischung einiger der klassischen Komplexitätsergebnisse.
András Salamon
6

Aktuelle lustige Titel:

  • A. Kehagias, P. Pralat, Einige Bemerkungen zu Cops und betrunkenen Räubern , Theoretical Computer Science 463 (2012) 133-147, DOI

  • A. Kehagias, D. Mitsche, P. Pralatb, Polizisten und unsichtbare Räuber: Die Kosten der Trunkenheit , Theoretische Informatik (2013), in der Presse

  • Natasha Komarov, Peter Winkle, Erfassung des betrunkenen Räubers auf einer Grafik , Mai 2013, arXiv: 1305.4559

user13136
quelle
5

Die Rede von Alice und Bob nach dem Abendessen von John Gordon.

Netter unbeschwerter Vortrag über Codierungstheorie.

Jagadisch
quelle
Es ist unterhaltsam, wie viel von dem, was er von seinem Taschenrechner behauptet, auf einem modernen Smartphone tatsächlich möglich ist. Noch keine holographischen 3D-Anzeigen, und es ist schwer für Sie, einen Compiler von ADA auf Android zu finden, aber
ansonsten
5

Zu einem anderen Thema ( Wie referiere ich eine Arbeit? ) Habe ich folgende Arbeit gefunden:

Graham Cormode. 2009. Wie man ein Papier NICHT überprüft: die Werkzeuge und Techniken des kontroversen Überprüfers.SIGMOD Rec . 37, 4 (März 2009), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

Ich hatte viel Spaß beim Lesen dieser Zeitung;)

M.S. Dousti
quelle
4

Ich kann jetzt nicht an ein lustiges Papier denken, aber ich erinnere mich an ein "normales" Papier, das eine lustige Linie enthielt. Es war in der Tat der allererste Satz in Abschnitt 1. Die Autoren begannen die Arbeit mit:

"Im Gegensatz zu unserer üblichen Praxis fühlen wir uns verpflichtet, dieses Papier mit ein paar Definitionen zu beginnen." Also lass G ... "

Der Titel des Papiers lautet " $beta$-perfect graphs", von Markossian, Gasparian und Reed im Jahr 1996. Es hat meine Aufmerksamkeit erregt, weil es in der Tat ein Schlüsselpapier zur perfekten Graphentheorie ist, in dem es die Klasse der beta-perfekten Graphen definiert. Eine Klasse, die in gewisser Weise den perfekten Graphen entspricht (Beta-perfekte Graphen sind eine Unterklasse von Graphen ohne Löcher, während perfekte Graphen eine Unterklasse von Graphen ohne ungerade Löcher sind).

Murilo da Silva
quelle
Auch bekannt als "Da dies ein theoretischer Vortrag ist, würde ich damit beginnen, das Problem zu definieren, über das ich spreche ..."
Sariel Har-Peled