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.

41 Answers 41

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

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.
  • 24
    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. – Tsuyoshi Ito Nov 19 '10 at 1:41
  • 5
    There have been semi-rigorous looks at the urinal selection problem from an algorithms POV: blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability – Andy Drucker Dec 14 '12 at 3:46

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.

  • 6
    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/… – arnab Nov 18 '10 at 16:40
  • 3
    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 ;-) – Mugizi Rwebangira Nov 19 '10 at 1:33
  • 1
    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. – Kyle Oct 9 '17 at 18:10

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

  • 4
    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." – Dave Clarke Nov 18 '10 at 11:44
  • I would love to see this continued to the present day – Thomas Ahle Jul 12 '17 at 22:45

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.

  • 12
    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. – Neel Krishnaswami Nov 18 '10 at 11:23
  • 3
    French speaking readers may enjoy his paper on mustard clocks – gallais Mar 2 '12 at 14:18
  • 1
    Unfortunately the third link is broken – Max Oct 25 '12 at 9:59
  • 3
    @gallais: Actually, the original version of the "Mustard watches" paper is in english and can be found here. – Damiano Mazza Jan 7 '14 at 22:05
  • 1
    This is the "fix" for the link in the main answer: iml.univ-mrs.fr/~girard/0.pdf – apnorton Feb 9 '14 at 18:16
  • 6
    Could you split this into two answers? – ShreevatsaR Nov 18 '10 at 18:42
  • Do you mean “superpolylogarithmic”? – Geoffrey Irving Mar 27 at 5:37

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.

  • I think this might be related: mathworld.wolfram.com/GloveProblem.html – RJK Nov 18 '10 at 11:56
  • 4
    @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.) – Joshua Grochow Nov 18 '10 at 16:36

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.

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

  • 4
    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. – Anthony Labarre Nov 19 '10 at 8:10
  • 1
    This is my favorite book. I am amazed more authors haven't followed their format. – Chad Brewbaker Feb 26 '14 at 17:07

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.

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.

  • 2
    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. – Steven Stadnicki Nov 20 '10 at 0:22

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

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

  • He also changed the presentation name during the FOCS 2010 talk... that was funny – chazisop Nov 22 '10 at 19:34

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

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

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.

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.

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

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

  • 1
    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. – Raphael Jan 31 '11 at 15:18

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

  • Nice! Working through these also serves as a nice refresher in some of the classic complexity results. – András Salamon Feb 29 '12 at 14:56

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

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

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

  • The link is dead and I couldn't find the paper using a quick google search. Could you maybe reupload it somewhere? – tranisstor Mar 26 at 12:30

The Alice and Bob After Dinner Speech by John Gordon.

Nice light-hearted talk on coding theory.

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

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

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.

  • Also known as "Since this is a theory talk, I would start by defining the problem I am talking about..." – Sariel Har-Peled Nov 18 '10 at 21:03

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


Lambda the Ultimate brought to my attention the whitepaper on Phosphorous, the Popular Lisp, which if "Popular Lisp" didn't tip you off, is satirical ^_-

protected by Kaveh May 10 '13 at 6:54

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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