Documents drôles liés au TCS, etc.?

80

Quel est le travail publié le plus drôle sur le TCS que vous connaissez?

S'il vous plaît inclure uniquement ceux qui sont destinés à être drôle. Les œuvres explicitement conçues pour être intelligemment humoristiques (plutôt que, par exemple, un recueil publié de petites blagues sur la théorie de la complexité) sont préférées. Les œuvres avec des titres humoristiques (en fait, pas seulement mignons) sont également acceptées.

Veuillez ne faire qu’une œuvre par réponse afin que les "meilleures" puissent faire des bulles.

Joshua Grochow
la source
3
Qu'en est-il des papiers avec des titres amusants? ou est-ce que cela devrait être une question différente?
Suresh Venkat
4
Je pense que les titres amusants vont bien :).
Joshua Grochow
1
Pourquoi seulement la complexité (et pas d'autres sujets du SDC)? Qu'en est-il des livres? (Je voudrais poster Concrete Mathematics :))
Kaveh
3
Pour une raison quelconque, mathoverflow.net/questions/44326/most-memorable-titles est un fil étroitement lié.
RJK
2
@Suresh: Je pense que vous voulez dire xxx.lanl.gov/abs/1003.6064v1
Radu GRIGore

Réponses:

72

Le journal de Scott Aaronson: La hiérarchie polynomiale s'effondre: des milliers de personnes craignent la destruction

Joshua Grochow
la source
2
Hilarant. Je n'avais jamais vu ça auparavant.
Derrick Stolee
7
Un titre connexe tragique (ou drôle?): THE SKY IS FALLING (La hiérarchie exponentielle forte s'effondre) , rapport technique de L. Hemachandra. La note de bas de page suivante est jointe au titre: "Poulet Peu pensait que le ciel était en train de tomber. Ce n'était pas le cas."
Alessandro Cosentino
52

Le problème du papier hygiénique (Donald Knuth, American Mathematical Monthly, 1984). De l'introduction:

Les distributeurs de papier toilette dans un bâtiment donné sont conçus pour contenir deux rouleaux de mouchoirs en papier et une personne peut utiliser l’un ou l’autre des rouleaux. Il y a deux types de personnes qui utilisent les salles de repos dans le bâtiment: les gros-choosers et les petits-choosers. Un gros sélectionneur prend toujours un morceau de papier hygiénique du rouleau qui est actuellement plus gros; un petit sélecteur fait toujours le contraire. Cependant, lorsque les deux rouleaux ont la même taille ou lorsqu'un seul rouleau est non vide, tout le monde choisit le rouleau non vide le plus proche. Lorsque les deux rouleaux sont vides, tout le monde a un problème.
chrétien
la source
24
Oh non. Knuth m'a battu à cela. J'avais envisagé une question connexe, certes plus simple, et me suis convaincue que tout le monde devrait faire un peu le choix de minimiser les risques en coopération (et j'en ai une depuis ce moment). Je n'ai cependant jamais eu le temps de rédiger le résultat. Au moins, je suis heureux de connaître les travaux antérieurs avant de les rédiger et de les soumettre à la Conférence internationale sur les toilettes théoriques.
Tsuyoshi Ito
5
Il y a eu des analyses
Andy Drucker
38

Kyle Burke et David Charlton. Limites inférieures pour le temps polynomial probablement istique. Université de Boston, 2005. (Merci à @arnab et aux archives Web pour le lien.)

Je suis à peu près sûr que c'était un journal du poisson d'avril, mais de toute façon, il est absolument hilarant. L'abstrait:

Nous comblons une lacune dans la théorie de la complexité existante en introduisant la classe des calculs de temps polynomiaux probables, c'est-à-dire des calculs qui, vous le savez, se terminent probablement par le temps polynomial, à notre connaissance. Nous appliquons cette classe pour montrer que les algorithmes pour les problèmes NP-complets ne fonctionnent probablement pas dans le temps polynomial.

Joshua Grochow
la source
6
Je l'ai! Je ne parviens pas à trouver le lien à partir d'une page Web existante, mais vous pouvez le récupérer ici: web.archive.org/web/20080211140314/http://cs-people.bu.edu/…
arnab
3
J'étais dans une classe avec David Charlton en 2002 alors qu'il était étudiant, alors je suis presque sûr que ce doit être en 2005 et non en 1995 ;-)
Mugizi Rwebangira,
1
David a écrit ceci comme une réponse hilarante à un commentaire que j'ai fait lors de mes études supérieures. Je ne me souviens pas de mon commentaire exact, mais le papier est hilarant! : -DI ne peut prendre aucun crédit pour l'hilarité.
Kyle
30

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

Cet article étudie diverses conférences CS et essaie de les classer comme théoriques ou appliquées, selon que les auteurs classent leurs noms par ordre alphabétique (théorique) ou par contribution (appliqué).

Robin Kothari
la source
4
J'adore la fin "Le but de la recherche présentée dans ce rapport était de faire rire POPL '92; je suis heureux de dire que, à cet égard, la recherche a été entièrement fructueuse."
Dave Clarke
J'adorerais que cela se poursuive jusqu'à présent
Thomas Ahle
24

Plusieurs papiers de Jean-Yves Girard .

Son article sur Linear Logic contient la note suivante du rédacteur en chef du journal Theoretical Computer Science:

En raison de sa longueur et de sa nouveauté, ce document n'a pas été soumis au processus normal d'arbitrage. L’éditeur est disposé à partager avec l’auteur les critiques éventuellement exprimées concernant cet ouvrage.

Un autre est Locus Solum, Des règles de la logique à la logique des règles . Le document de 192 pages comporte une annexe de près de 100 pages intitulée " Un pur déchet de papier ", l’annexe la plus drôle que j’ai jamais vue.

Kaveh
la source
12
Ce qui est fantastique, c’est que "un pur déchet de papier" est vraiment très bon. Vous ne pouvez naïvement faire confiance à rien de ce qu'il écrit, mais néanmoins, il y a un problème sérieux de logique caché dans presque chaque blague / insulte / aparté.
Neel Krishnaswami
3
Les lecteurs francophones apprécieront son article sur les horloges à la moutarde
gallais
1
Malheureusement, le troisième lien est brisé
Max
3
@gallais: En fait, la version originale du journal "Mustard watches" est en anglais et peut être trouvée ici .
Damiano Mazza
1
C'est le "correctif" pour le lien dans la réponse principale: iml.univ-mrs.fr/~girard/0.pdf
apnorton
22

Le document de Yonatan Bilu, Dana Porrat et Yoav Yaffe " Sur le nombre de préservatifs dans une orgie sans risque pour le sexe ". Cet article n'a pas été publié, il ne correspond donc pas à l'une des exigences (être un travail publié). Mais je pense que cela peut être inclus ici à titre d'exception.

Oleksandr Bondarenko
la source
Je pense que cela pourrait être lié: mathworld.wolfram.com/GloveProblem.html
RJK
4
@Oleksander: L'exigence "publiée" n'était pas censée être stricte, mais bien séparer des choses telles que des articles et des livres, par exemple, de bandes dessinées (sinon ce fil serait rempli de références xkcd.)
Joshua Grochow
Dans la même veine: Triplettes, Dégénérés et Triangles de l'amour de Grønlund et Pettie. Il s’agit d’un article sérieux, d’une complexité fine, et la blague du titre est forcée.
kinokijuf
20

En fait, il y a tout un journal qui se veut drôle. Le journal de la craptologie . Les sujets sont généralement liés à la cryptographie. Il y a aussi des vidéos de sessions (!)

Le volume 4 de la cryptographie dans l'univers de l'auto-stoppeur (section 5) en est un exemple:

Attractions à venir

Si vous avez apprécié notre présentation, vous serez ravi d’entendre parler des attractions à venir du même auteur:

- L'analyse cryptographique des systèmes de protocoles interactifs humains. Une analyse cryptographique controversée du papier de Shakira [4] qui prouve que HIPS ment, en fait.

- connaissance anti-zéro. Un système de protocole qui révèle tout ce qu'un prouveur sait, sauf ce que le vérificateur veut entendre. Des protocoles ad hoc de connaissance zéro ont été développés par la plupart des services d'assistance téléphonique.

- Répartition des clés quantiques basée sur des phénomènes sociaux. Cet article montre comment distribuer des clés à l'aide de techniques quantiques sans utiliser d'objets quantiques. Au lieu d'utiliser des objets quantiques, le protocole utilise plutôt l'incertitude de tout homme quant à savoir si sa première soirée avec une femme compte comme une date ou non pour transmettre les clés.

M. Alaggan
la source
17

Mathématiques concrètes: un fondement de l'informatique , par Ronald Graham, Donald Knuth et Oren Patashnik.

Un livre incroyable avec beaucoup de notes latérales amusantes. :) (Voir aussi la page GKP de DEK .)

Kaveh
la source
4
Les notes de côté sont certes drôles, mais le livre est "tout simplement agréable" - certes, tout le monde n’est pas capable d’écrire un livre agréable ;-) En tout cas, je ne sais pas si c’est une œuvre amusante, mais vous obtenez mon vote car J'aime tellement le livre.
Anthony Labarre
1
C'est mon livre préféré. Je suis étonné que plus d'auteurs n'aient pas suivi leur format.
Chad Brewbaker
17

Je recommanderais les traitements de FUN: la Conférence internationale sur le plaisir de jouer avec les algorithmes.

Je dois dire que "La dureté du jeu Lemmings, ou Oh non, plus de preuves de NP-complétude" par Graham Cormode est l’un de mes préférés.

Swann Perarnau
la source
2
Je viens de retrouver les débats de 2007 sur les livres FUN de Powell la semaine dernière - j'appuie sans réserve cette recommandation! Quelques excellents résultats sur le tri pessimal et les algorithmes de pagination les moins performants.
Steven Stadnicki
16

Don Knuth's Une proposition terminologique . SIGACT News, 6 (1), 1974. Mentionné sur le blog Complexity. C'est apparemment où nous avons eu les termes "NP-complet" et "NP-difficile".

Une des choses que je préfère de cet article est la suggestion d'Albert Meyer selon laquelle ce que nous appelons maintenant les problèmes NP-difficiles soit appelé «difficile à satisfaire», ou «difficile à reproduire».

Joshua Grochow
la source
14

Découvrez la figure qui accompagne le document SODA d'une page d'Adam Kalai, "Générer facilement des nombres pondérés aléatoires": lien

Aaron Roth
la source
12

A. Broder, J. Stolfi " Algorithmes pessimaux et analyse de simplexité ", ACM SIGACT News 16 (3), automne 1984.

Le document introduit "une branche entièrement nouvelle de l'informatique, la conception et l'analyse d'algorithmes réticents. Intuitivement, un algorithme réticent pour un problème P est un algorithme qui perd du temps de manière suffisamment artificielle pour tromper un observateur naïf."

Hermann Gruber
la source
9

Le Parlement à temps partiel de Lamport a fait une percée dans l'informatique distribuée, mais le journal était tellement (délibérément!) Obscurci que les gens ne pouvaient pas le comprendre - à ma connaissance, il lui a fallu environ 10 ans pour le faire publier (anciens rédacteurs) sous sa forme obscurcie. Finalement, Lamport a fait un suivi avec Paxos Made Simple , qui avait le résumé suivant: " L'algorithme de Paxos, lorsqu'il est présenté en langage clair, est très simple ."

Lev Reyzin
la source
9

L'Association pour l'hérésie informatique à la CMU en possède un certain nombre, qui sont présentées lors de la conférence annuelle SIGBOVIK (tenue le 04/01/2011). Mon préféré est:

Une approche basée sur le vol pour l'acquisition d'objets en 3D.

utilisateur2333
la source
8

Dans le même esprit que celui de Murilo da Silva, je ne peux m'empêcher de publier cet extrait de "Factoring N-Cycles et cartes de dénombrement du genre donné" de Goupil et Schaefer :

Après cette démonstration, nous encourageons le lecteur à faire une pause et à profiter d’une activité plus légère, comme observer les oiseaux ou jardiner, avant de poursuivre la lecture.

Anthony Labarre
la source
7

"Raffinement du formalisme d'État" par Lamport.

Un de nos amis, qui était un mathématicien brillant, a été hospitalisé en raison de l'abus prolongé de drogues hallucinogènes. Nous décidons de lui donner une horloge numérique pour sa chambre. Cependant, son médecin suggère que les affichages des heures et des minutes peuvent être trop déroutants. Nous avons donc mis du ruban adhésif sur l'affichage des minutes, transformant notre cadeau en horloge numérique.

Marcus Ritt
la source
7

Je viens de découvrir "une lettre de l'auteur frustré d'un journal" . Bonne lecture ;-)

Anthony Labarre
la source
1
J'ai trop entendu parler de ces processus pour rejeter la lettre immédiatement comme une satire. Je me demande si c'est le cas. Sinon, j'ai peur.
Raphaël
6

Je suis tombé sur le "Complexity Theory Newsflash" à un moment donné, et j'ai trouvé ça plutôt drôle.

Ryan Williams
la source
Agréable! Travailler à travers ceux-ci constitue également un bon rappel des résultats classiques de complexité.
András Salamon le
6

Titres amusants récents:

  • A. Kehagias, P. Pralat, Quelques remarques sur les flics et les voleurs ivres , Informatique théorique 463 (2012) 133-147, DOI

  • A. Kehagias, D. Mitsche, P. Pralatb, Policiers et voleurs invisibles: Le coût de l'ivresse , Théoretical Computer Science (2013), dans Presse

  • Natasha Komarov, Peter Winkle, Capture du voleur ivre sur un graphique , mai 2013, arXiv: 1305.4559

utilisateur13136
la source
5

Le discours d'Alice et de Bob après le dîner de John Gordon.

Joli discours léger sur la théorie du codage.

Jagadish
la source
Il est amusant de voir tout ce qu'il prétend que sa calculatrice de poche pourrait faire est maintenant possible sur un smartphone moderne. Pas encore d'affichages holographiques en 3D, et vous aurez peut-être du mal à trouver un compilateur d'ADA à Android, mais à part cela ...
AlexC
5

Sur un autre sujet ( comment arbitrer un article? ), J’ai trouvé l’article suivant:

Graham Cormode. 2009. Comment ne PAS réviser un article: les outils et techniques de l'examinateur contradictoire. SIGMOD Rec . 37, 4 (mars 2009), 100-104. DOI = 10.1145 / 1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

J'ai eu beaucoup de plaisir à lire ce document;)

M.S. Dousti
la source
4

Je ne peux pas penser maintenant à un papier drôle, mais je me souviens d'un papier "normal" contenant une ligne amusante. C'était en fait la toute première phrase de la section 1. Les auteurs ont commencé le document avec:

"Contrairement à notre habitude, nous nous sentons obligés de commencer cet article avec quelques définitions". Alors laissez G ... "

Le titre de l'article est " $beta$-parfect graphs", de Markossian, Gasparian et Reed en 1996. Il a attiré mon attention car il s'agit en fait d'un document clé sur la théorie des graphes parfaits, dans lequel est définie la classe de graphes bêta-parfaits, une classe qui est en quelque sorte analogue aux graphes parfaits (les graphes bêta-parfaits étant une sous-classe de graphes EVEN sans trous, tandis que les graphes parfaits sont une sous-classe de graphiques ODD sans trous.

Murilo da Silva
la source
Aussi connu comme "Puisqu'il s'agit d'un discours théorique, je commencerais par définir le problème dont je parle ..."
Sariel Har-Peled