86
$\begingroup$

What is the funniest TCS-related published work you know?

Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, a published collection of short jokes regarding complexity theory) are preferred. Works with humorous (actually humorous, not just cute) titles are also accepted.

Please only one work per answer so the "best" ones can bubble to the top.

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ what about papers with funny titles ? or should that be a different question ? $\endgroup$
    – Suresh Venkat
    Commented Nov 18, 2010 at 3:46
  • 4
    $\begingroup$ I think funny titles are fine :). $\endgroup$
    – Joshua Grochow
    Commented Nov 18, 2010 at 3:51
  • 1
    $\begingroup$ Why just complexity (and not other TCS topics)? What about books? (I would like to post Concrete Mathematics :) ) $\endgroup$
    – Kaveh
    Commented Nov 18, 2010 at 4:15
  • 3
    $\begingroup$ for some reason, mathoverflow.net/questions/44326/most-memorable-titles is a closely-related thread. $\endgroup$
    – RJK
    Commented Nov 18, 2010 at 11:51
  • 2
    $\begingroup$ @Suresh: I believe you mean xxx.lanl.gov/abs/1003.6064v1 $\endgroup$
    – Radu GRIGore
    Commented Nov 18, 2010 at 19:30

42 Answers 42

Reset to default
1
2
77
$\begingroup$

Scott Aaronson's newspiece: Polynomial hierarchy collapses: thousands feared tractable

Improve this answer
$\endgroup$
2
53
$\begingroup$

The Toilet Paper Problem (Donald Knuth, American Mathematical Monthly, 1984). From the introduction:

The toilet paper dispensers in a certain building are designed to hold two rolls of tissues, and a person can use either roll. There are two kinds of people who use the rest rooms in the building: big-choosers and little-choosers. A big-chooser always takes a piece of toilet paper from the roll that is currently larger; a little-chooser always does the opposite. However, when the two rolls are the same size, or when only one roll is nonempty, everybody chooses the nearest nonempty roll. When both rolls are empty, everybody has a problem.
Improve this answer
$\endgroup$
2
  • 24
    $\begingroup$ Oh, no. Knuth beat me to it. I had considered a related, admittedly simpler question and convinced myself that everyone should be a little-chooser to minimize the risk cooperatively (and I have been one since then). I have never had time to write up the result, though. At least, I am glad to know the prior work before I write it up and submit it to the International Conference on Theoretical Restrooms. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 19, 2010 at 1:41
  • 6
    $\begingroup$ There have been semi-rigorous looks at the urinal selection problem from an algorithms POV: blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability $\endgroup$
    – Andy Drucker
    Commented Dec 14, 2012 at 3:46
40
$\begingroup$

Kyle Burke and David Charlton. Lower bounds for probably-istic polynomial time. Boston University, 2005. (Thanks to @arnab and the Web Archive for the link.)

I'm pretty sure this was an April Fool's paper, but either way it is absolutely hilarious. The abstract:

We fill a gap in existing complexity theory by introducing the class of probablyistic polynomial time computations, that is, computations that, you know, probably terminate in polynomial time, as far as we know. We apply this class to show that algorithms for NP-complete problems probably don't run in polynomial time.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ Got it! I can't find it linked from any existing webpage, but you can retrieve it here: web.archive.org/web/20080211140314/http://cs-people.bu.edu/… $\endgroup$
    – arnab
    Commented Nov 18, 2010 at 16:40
  • 3
    $\begingroup$ I was in a class with David Charlton in 2002 when he was an undergraduate so I am pretty sure that must be 2005 not 1995 ;-) $\endgroup$
    – Mugizi Rwebangira
    Commented Nov 19, 2010 at 1:33
  • 1
    $\begingroup$ David wrote this as a hilarious response to a comment I made in grad school. I don't remember my exact comment, but the paper is hilarious! :-D I can't take any actual credit for the hilarity. $\endgroup$
    – Kyle
    Commented Oct 9, 2017 at 18:10
32
$\begingroup$

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

This paper studies varies CS conferences and tries to classify them as theoretical or applied based on whether authors order their names in alphabetical order (theoretical) or by contribution (applied).

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ I love the ending "The goal of the research presented in this report was to provide some laughs at POPL ’92; I am happy to say that in this respect the research was entirely successful." $\endgroup$
    – Dave Clarke
    Commented Nov 18, 2010 at 11:44
  • $\begingroup$ I would love to see this continued to the present day $\endgroup$
    – Thomas Ahle
    Commented Jul 12, 2017 at 22:45
26
$\begingroup$

Several of Jean-Yves Girard's papers.

His Linear Logic paper has the following footnote by the editor of Theoretical Computer Science journal:

Because of its length and novelty this paper has not been subjected to the normal process of refereeing. The editor is prepared to share with the author any criticism that eventually will be expressed concerning this work.

Another one is Locus Solum, From the rules of logic to the logic of rules. The 192 page paper has an appendix which is almost 100 pages long named "A pure waste of paper", the funniest appendix I have ever seen.

Improve this answer
$\endgroup$
5
  • 14
    $\begingroup$ The fantastically odd thing is that "A pure waste of paper" is really very good. You can't naively trust anything he writes in it, but nevertheless there's a serious point about logic hidden within almost every joke/insult/aside. $\endgroup$
    – Neel Krishnaswami
    Commented Nov 18, 2010 at 11:23
  • 4
    $\begingroup$ French speaking readers may enjoy his paper on mustard clocks $\endgroup$
    – gallais
    Commented Mar 2, 2012 at 14:18
  • 1
    $\begingroup$ Unfortunately the third link is broken $\endgroup$
    – Max
    Commented Oct 25, 2012 at 9:59
  • 3
    $\begingroup$ @gallais: Actually, the original version of the "Mustard watches" paper is in english and can be found here. $\endgroup$
    – Damiano Mazza
    Commented Jan 7, 2014 at 22:05
  • 1
    $\begingroup$ This is the "fix" for the link in the main answer: iml.univ-mrs.fr/~girard/0.pdf $\endgroup$
    – apnorton
    Commented Feb 9, 2014 at 18:16
24
$\begingroup$
Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ Could you split this into two answers? $\endgroup$
    – ShreevatsaR
    Commented Nov 18, 2010 at 18:42
  • $\begingroup$ Do you mean “superpolylogarithmic”? $\endgroup$
    – Geoffrey Irving
    Commented Mar 27, 2018 at 5:37
22
$\begingroup$

The paper by Yonatan Bilu, Dana Porrat and Yoav Yaffe "On The Number of Condoms at a Cheap Safe-Sex Orgy". This paper was not published, so it doesn't correspond to one of the requirements (to be published work). But I think it can be included here as an exception.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think this might be related: mathworld.wolfram.com/GloveProblem.html $\endgroup$
    – RJK
    Commented Nov 18, 2010 at 11:56
  • 5
    $\begingroup$ @Oleksander: The "published" requirement was not meant to be strict, but meant to separate things like articles and books from, say, cartoon strips (otherwise this thread would be filled with xkcd references.) $\endgroup$
    – Joshua Grochow
    Commented Nov 18, 2010 at 16:36
  • $\begingroup$ In a similar vein: Threesomes, Degenerates and Love Triangles by Grønlund and Pettie. It is really a serious paper in fine-grained complexity, and the joke in the title is forced. $\endgroup$
    – kinokijuf
    Commented Aug 17, 2018 at 20:36
20
$\begingroup$

In fact there is a whole journal that is intended to be funny. The journal of craptology. The topics are usually related to cryptography. There are also some sessions videos (!)

One example is the Volume 4 paper of Cryptography in a Hitchhiker's Universe (section 5) is :

Coming Attractions

If you have enjoyed our feature presentation, you’ll be pleased to hear about upcoming attractions by the same author:

– The cryptanalysis of Human Interactive Protocol Systems. A controversial cryptanalysis of the paper of Shakira [4] which proves that HIPS do, in fact, lie.

– Anti-zero-knowledge. A protocol system which reveals everything that a prover knows except that which the verifier wants to hear. Ad-hoc anti-zero-knowledge protocols have been developed by most customer helpline services.

– Quantum key distribution based on social phenomena. This paper demonstrates how to distribute keys using quantum techniques but without using quantum objects. Instead of using quantum objects, the protocol instead uses the uncertainty that any man has about whether his first evening out with a woman counts as a date or not to transmit the keys.

Improve this answer
$\endgroup$
18
$\begingroup$

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik.

An amazing book with lots of funny side notes. :) (See also DEK's GKP page.)

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ The side notes are indeed funny, but the book is "just enjoyable" -- granted, not everyone can write an enjoyable book ;-) Anyway, I don't know whether it qualifies as a funny work, but you get my vote because I like the book so much. $\endgroup$
    – Anthony Labarre
    Commented Nov 19, 2010 at 8:10
  • 2
    $\begingroup$ This is my favorite book. I am amazed more authors haven't followed their format. $\endgroup$
    – Chad Brewbaker
    Commented Feb 26, 2014 at 17:07
17
$\begingroup$

I would recommend the processings of FUN: the International Conference on Fun With Algorithms.

I must say that "The hardness of the Lemmings game, or Oh no, more NP-completeness proofs" by Graham Cormode is one of my favorite.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I just found the 2007 FUN proceedings at Powell's books last week - I wholeheartedly second this recommendation! Some great results on pessimal sorting and worst-possible paging algorithms. $\endgroup$
    – Steven Stadnicki
    Commented Nov 20, 2010 at 0:22
16
$\begingroup$

Don Knuth's A terminological proposal. SIGACT News, 6(1), 1974. Mentioned on The Complexity Blog. This is apparently where we got the terms "NP-complete" and "NP-hard."

One of my favorite's from this piece is Albert Meyer's suggestion that what we now call NP-hard problems be called Hard-as-Satisfiability, or hard-as-S for short.

Improve this answer
$\endgroup$
14
$\begingroup$

Mihai Patrascu and Liam Roditty's paper on "Distance Oracles Beyond the Thorup–Zwick Bound" was initially titled "How to grow your balls" on Mihai's homepage :-)

Improve this answer
$\endgroup$
1
  • $\begingroup$ He also changed the presentation name during the FOCS 2010 talk... that was funny $\endgroup$
    – chazisop
    Commented Nov 22, 2010 at 19:34
14
$\begingroup$

Check out the figure that accompanies Adam Kalai's 1 page SODA paper, "Generating Random Factored Numbers, Easily": link

Improve this answer
$\endgroup$
12
$\begingroup$

A. Broder, J. Stolfi "Pessimal algorithms and simplexity analysis", ACM SIGACT News 16(3), Fall 1984.

The paper introduces "an entirely new branch of Computer Science, the design and analysis of reluctant algorithms. Intuitively, a reluctant algorithm for a problem P is one which wastes time in a way that is sufficiently contrived to fool a naive observer."

Improve this answer
$\endgroup$
9
$\begingroup$

Lamport's Part Time Parliament made a breakthrough in distributed computing, but the paper was so (purposely!) obfuscated that people couldn't understand it -- as far as I know, it took him around 10 years to get it published (past editors) in its obfuscated form. Eventually Lamport followed up with Paxos Made Simple, which had the following abstract: "The Paxos algorithm, when presented in plain English, is very simple."

Improve this answer
$\endgroup$
9
$\begingroup$

The Association for Computational Heresy at CMU has a number of these, which are presented at the annual SIGBOVIK conference (next held 04/01/2011). My personal favorite is :

A theft-based approach to 3d object acquisition.

Improve this answer
$\endgroup$
8
$\begingroup$

In the same spirit as Murilo da Silva's post, I cannot resist posting this excerpt from Goupil and Schaefer's "Factoring N-Cycles and Counting Maps of Given Genus":

After this proof, we kindly encourage the reader to pause and enjoy a lighter activity such as bird watching or gardening before pursuing the reading.

Improve this answer
$\endgroup$
7
$\begingroup$

"Refinement in State-Based Formalism" by Lamport.

A friend of ours, who was a brilliant mathematician, has been hospitalized because of long-term abuse of hallucinogenic drugs. We decide to give him a digital clock for his room. However, his doctor suggests that the hour and minute displays together might be too confusing. So, we put tape over the minute display, turning our gift into a digital hour clock.

Improve this answer
$\endgroup$
7
$\begingroup$

I just discovered "A letter from the frustrated author of a journal paper". Nice read ;-)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I have heard too much about these processes to reject the letter immediately as satire. I wonder if it is, though. Otherwise, I'm scared. $\endgroup$
    – Raphael
    Commented Jan 31, 2011 at 15:18
6
$\begingroup$

On another topic (How do I referee a paper?), I found the following paper:

Graham Cormode. 2009. How NOT to review a paper: the tools and techniques of the adversarial reviewer. SIGMOD Rec. 37, 4 (March 2009), 100-104. DOI=10.1145/1519103.1519122 http://doi.acm.org/10.1145/1519103.1519122

I had a lot of fun reading this paper ;)

Improve this answer
$\endgroup$
6
$\begingroup$

I came across the "Complexity Theory Newsflash" at some point, and thought it was pretty funny.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice! Working through these also serves as a nice refresher in some of the classic complexity results. $\endgroup$
    – András Salamon
    Commented Feb 29, 2012 at 14:56
6
$\begingroup$

Recent funny titles:

  • A. Kehagias, P. Pralat, Some remarks on cops and drunk robbers, Theoretical Computer Science 463 (2012) 133-147, DOI

  • A. Kehagias, D. Mitsche, P. Pralatb, Cops and invisible Robbers: The cost of drunkenness, Theoretical Computer Science (2013), in Press

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

Improve this answer
$\endgroup$
6
$\begingroup$

Mick gets some (the odds are on his side) by Reed Chvatal and Chvatal Reed (FOCS 1992), on satisfaction (aka satisfiability).

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ Your author ordering here is wrong! Btw, more on author ordering. $\endgroup$
    – vb le
    Commented Jun 6, 2013 at 10:54
6
$\begingroup$

How much damage could be caused by a peer reviewer having a bad day? Hilarious fictional reviews of famous old CS papers.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link is dead and I couldn't find the paper using a quick google search. Could you maybe reupload it somewhere? $\endgroup$
    – tranisstor
    Commented Mar 26, 2018 at 12:30
5
$\begingroup$

The Alice and Bob After Dinner Speech by John Gordon.

Nice light-hearted talk on coding theory.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It's entertaining how much of what he claims his pocket calculator could do is actually now possible on a modern smartphone. No 3D holographic displays yet, and you might be hard-pressed to find a compiler from ADA to Android, but apart from that... $\endgroup$
    – AlexC
    Commented Oct 19, 2018 at 12:43
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

I cannot think now of a funny paper, but I do remember of a "normal" paper that had a funny line in it. It was in fact the very first sentence in Section 1. The authors began the paper with:

"Contrary to our usual practice, we feel obliged to begin this paper with a few definitions". So let G..."

The title of the paper is "$beta$-perfect graphs", by Markossian, Gasparian and Reed in 1996. It called my attention because it is in fact a key paper on perfect graph theory, where it is defined the class of beta-perfect graphs, a class that is in a way analogous to the perfect graphs (beta-perfect graphs being a subclass of EVEN-hole-free graphs, whereas perfect graphs are a subclass of ODD-hole-free graphs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Also known as "Since this is a theory talk, I would start by defining the problem I am talking about..." $\endgroup$
    – Sariel Har-Peled
    Commented Nov 18, 2010 at 21:03
4
$\begingroup$

As far as a funny title: "How to play a coloring game against a color-blind adversary"

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

Improve this answer
$\endgroup$
4
$\begingroup$

How about Scott is not always sober?

Improve this answer
$\endgroup$
4
$\begingroup$

"Busy beavers gone wild" by Grégory Lafitte, EPTCS 1, 2009, pp. 123-129 arXiv:0906.3257v1

Improve this answer
$\endgroup$
1
2

Not the answer you're looking for? Browse other questions tagged or ask your own question.