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.
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.
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.
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).
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.
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.
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.)
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.
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.
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 :-)
Check out the figure that accompanies Adam Kalai's 1 page SODA paper, "Generating Random Factored Numbers, Easily": link
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 ;-)
I came across the "Complexity Theory Newsflash" at some point, and thought it was pretty funny.
How much damage could be caused by a peer reviewer having a bad day? Hilarious fictional reviews of famous old CS papers.
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).
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 ;)
The Alice and Bob After Dinner Speech by John Gordon.
Nice light-hearted talk on coding theory.
"Busy beavers gone wild" by Grégory Lafitte, EPTCS 1, 2009, pp. 123-129 arXiv:0906.3257v1
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.
As far as a funny title: "How to play a coloring game against a color-blind adversary"
Without doubt, the most humorous mathematical writing award should go to Zeilberger. Considering that he writes about areas close to TCS and his views of TCS are very favorable makes his writings even more fun to read.
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 ^_-
Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts by Anne Driemel and Sariel Har-Peled at SODA 2012.
Found this on László Babai's homepage:
"Enjoy a fun paper from 1990 that is only partly technical and tells a fable about Merlin, Arthur, competition, and the ethics of mathematical communication: E-mail and the Unexpected Power of Interaction"
On the hardness of losing weight by Dániel Marx and Andrei Krokhin. ACM Transactions on Algorithms, 8(2):19, 2012. Despite the funny title, the paper is serious.
This paper is not a humorous theory paper, but it is a really humorous paper by a theoretician, about dangers of being sloppy about punctuation.
For example, in bibliography, he spelled his own name as:
J. Dullman
(As most reader know, Ullman's middle initial is D.)
I can't recall the full details (issue, year #, page), but it appeared in SIGACT newsletter in late 80's.
"Why ordinals are good for you" by I. Lepper and G. Moser. The paper itself is not intended to be humorous but it contains some funny quotes. I would be curious to see a similar introductory paper to the surreal numbers, a superclass of the ordinals introduced by J.H. Conway.
When I read this question, I immediately expected to see a mention of Connor McBride's "Kleisli Arrows of Outrageous Fortune". It begins with the greatest series of puns I've seen in any CS paper.
Have you considered to use mixed integer linear programming to assist you playing Pokemon Go?
Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems
In this paper, a new routing problem, referred to as the Generalized Clustered Orienteering Problem (GCOP), is studied. The problem is motivated by the mobile phone game Pokémon GO, an augmented reality game for mobile devices (...)
The computational performance of the proposed approaches is assessed in an extensive computational study, using real-world instances that combine crowd-sourced data associated with the Pokémon GO game with street maps of three European cities (...)
blog posts ok? its "published" in a sense & blogs are increasingly mainstream and many now written by senior/elite researchers. just recently ran across this old, imaginative entry from last April 1 from the Algorithmic Game Theory Blog, with clever resemblance to real events. see comments for colorful feedback. eg MacArthur fellow Terence Tao comments
A fantastic achievement! Now that Reimann’s hypothesis is settled, one can hope that the closely related Riemann’s hypothesis will fall next…
