Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

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

38 Answers 38

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

share|improve this answer
1  
Hilarious. I had not seen that before. –  Derrick Stolee Nov 18 '10 at 15:35
5  
A related tragic (or funny?) headline: THE SKY IS FALLING (The Strong Exponential Hierarchy Collapses), a technical report by L. Hemachandra. The following footnote is attached to the title: "Chicken Little thought that the sky was falling. It was not." –  Alessandro Cosentino Dec 1 '10 at 19:47

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.
share|improve this answer
21  
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
4  
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.

share|improve this answer
5  
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
2  
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

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

share|improve this answer
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

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.

share|improve this answer
3  
@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

Several of Jean-Yves Girad'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.

share|improve this answer
9  
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
1  
@gallais: Actually, the original version of the "Mustard watches" paper is in english and can be found here. –  Damiano Mazza Jan 7 at 22:05
share|improve this answer
5  
Could you split this into two answers? –  ShreevatsaR Nov 18 '10 at 18:42

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.

share|improve this answer

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.

share|improve this answer
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

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

share|improve this answer
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

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
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.

share|improve this answer

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

share|improve this answer

The Alice and Bob After Dinner Speech by John Gordon.

Nice light-hearted talk on coding theory.

share|improve this answer

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

share|improve this answer
7  
Your author ordering here is wrong! Btw, more on author ordering. –  vb le Jun 6 '13 at 10:54

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

The winner of the 2007 Aaronson/Gasarch Complexity Theme Song Contest is amazing! Download the mp3 and its lyrics.

share|improve this answer

protected by Kaveh May 10 '13 at 6:54

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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.