Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS.

It is quite clear that most of us might be attracted to read (or at least glance at) a paper with an interesting title (at least I do so every time I go over a list of papers in a conference), or avoid reading poorly named articles.

Which papers do you remember because of their titles (and, not-necessarily, the contents)?

My favorite, while not a proper TCS paper, is "The relational model is dead, SQL is dead, and I don’t feel so good myself." .

  • 5
    Somehow related: cstheory.stackexchange.com/questions/3111/… – Jennifer Ng Oct 22 '14 at 11:32
  • 6
    The question on MO was closed long ago and this one should be, too. It's purely opinion-based and just a big list. – David Richerby Oct 22 '14 at 18:00
  • 3
    Well, as far as I can see, the question on MO was closed only after 9 months of activity because the big list was getting too big, diminishing the signal/noise ratio. – Emil Jeřábek Oct 22 '14 at 18:49
  • 6
    I would not be too happy if this becomes a collection of silly puns or titles that are quotes only marginally related to the topic of the paper. IMO there should be some "quality" criterion, e.g. the title should actually have non-zero information content. – Sasho Nikolov Oct 22 '14 at 21:01
  • 7
    One of the answers on the mathoverflow site pointed to this link: www2.tcs.ifi.lmu.de/~jjohanns/cute.html, which is entitled Here's a random list of papers in Theoretical Computer Science with cute titles. – imallett Oct 23 '14 at 2:53

17 Answers 17

I did a survey on Twitter about this a while back, results here. A few of my favorites:

  • 9
    Pretty much any title by Philip Wadler is memorable. My favorites are his thesis, "Listlessness is Better than Laziness," and a POPL paper with Jeremy Siek, "Threesomes, With and Without Blame." – Huck Bennett Oct 22 '14 at 16:28

I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny titles results in unnecessarily long, uninformative and kludgy phrases that I find difficult to remember and look up.

There are papers like Pnueli's The Temporal Logic of Programs from 1977, which is absolutely straightforward but easy for me to remember. I'm guessing you did not mean memorable in that sense.

Leslie Lamport has several papers with memorable titles that don't strike me as trying to be funny. Titles of the kind you want are numerous and I don't think it's feasible to have a remotely comprehensive list, even of papers I have read and remembered or even of those that are considered significant. Nonetheless, let me recall a few, grouping them where appropriate.

The Writings of Leslie Lamport

Lamport describes the story behind various papers here. He has many memorable titles, though not all titles (or the papers) have been well received.

Paper Title Considered Harmful (thanks to @Bakuriu and @ Kaj_Sotala, whose comments got me to expand this point)

Edsger Dijkstra submitted A Case Against the Goto statement (also EWD 215) to the Communications of the ACM and the final title was modified by the editor Niklaus Wirth to the famous title given below. This title spawned a series of replies. Such titles already existed in journalism as pointed out in this Language log article. In particular, recursive responses to "X considered harmful" with "`X considered harmful', considered harmful" can be found as early as the 1950s (Language log, A Roguish Chrestomathy). In this specific case, we got these titles.

  • Go to statement considered harmful, 1968
  • Structured Programming with go to Statements, Knuth, 1974, which is a calmly written, beautiful article. He quotes Dijkstra's personal communication:

    "Please don't fall into the trap of believing that I am terribly dogmatical about [the go to statement]. I have the uncomfortable feeling that others are making a religion out of it, as if the conceptual problems of programming could be solved by a single trick, by a simple form of coding discipline!" -- Edsger Dijkstra, 1973

    "At the IFIP Congress in 1971 I had the pleasure of meeting Dr. Eiichi Goto of Japan, who cheerfully complained that he was always being eliminated." -- Knuth

  • "Goto Considered Harmful" considered harmful, Rubin, 1987

  • """GOTO Considered Harmful" Considered Harmful" Considered Harmful?", a collection of responses from Moore, Musciano, Liebhaber, Lott and Starr published in 1987.

  • On a somewhat disappointing correspondence, Dijkstra, 1987, which ends with this:

    Evidently, my priorities are not shared by everyone, for Rubin’s letter and most of the five reactions it evoked were conducted instead in terms of all sorts of “programming language features” that seem better ignored than exploited. The whole correspondence was carried out at a level that vividly reminded me of the intellectual climate of twenty years ago, as if stagnation were the major characteristic of the computing profession, and that was a disappointment. -- Dijkstra, 1987

There have been numerous "X considered harmful" titles since (see Google Scholar).

Logic, Programming Languages and Semantics

These are various papers in logic and semantics with memorable titles. I'll expand on them as I find time.

  • Since you mentioned "Go to statement considered harmful", one also needs to mention the response ""GOTO Considered Harmful" Considered Harmful", and the collection of counter-responses posted under the title "'"GOTO Considered Harmful" Considered Harmful' Considered Harmful?". – Kaj_Sotala Oct 23 '14 at 13:21
  • 1
    Since you mention the "Go to statement considered harmful" it should also be noted that Dijkstra did not choose that title. It was his editor that forcibly changed it (just read wikipedia). The original title was: A Case Against the Goto Statement, which is much milder. – Bakuriu Oct 23 '14 at 19:06

It's a recent paper, but its title often comes to my mind:

Giovanni Viglietta: Gaming Is a Hard Job, but Someone Has to Do It! Theory Comput. Syst. 54(4): 595-621 (2014)

Viglietta presents some metatheorems that can be used to study the computational complexity of video games using common elements like destroyable paths, keys, doors, and so on; among the results, he applies those metatheorems to prove the NP-hardness of Pac-Man.

Mihai Patrascu, and Liam Roditty. "Distance oracles beyond the Thorup-Zwick bound." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.

"How to Grow Your Balls" was the original title, though the authors was asked to changed it. I read the paper and actually think that the old title really fits to how you think about the algorithm.

A title that is both memorable and descriptive is Mihai Patrascu's Succincter.

Secure Content Sniffing for Web Browsers, or How to Stop Papers from Reviewing Themselves

Barth, A. ; UC Berkeley, Berkeley, CA, USA ; Caballero, J. ; Song, D. 2009 30th IEEE Symposium on Security and Privacy. DOI 10.1109/SP.2009.3

Lane A. Hemaspandra and Heribert Vollmer. "The Satanic Notations: Counting Classes Beyond #P And Other Definitional Adventures." Newsletter ACM SIGACT Volume 26 Issue 1, March 1995. Pages 2 - 13.

Research, Re: Search & Re-Search by Aske Platt. I ran across this paper when I was learning about AI search algorithms and the title always stuck with me.

Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set - SIAM J. Discrete Math., 26(4)

(reference to Talking heads - Psycho killer (qu'est-ce que c'est))

"The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86)"

The reference is to Bob Dylan's song, "Tombstone Blues." It's about 64-bit buffer overflows, but it evokes images of cleaving innocent programs in two. So metal.

https://dl.acm.org/citation.cfm?doid=1315245.1315313

It's Okay to Be Skinny, If Your Friends Are Fat.

  • Songrit Maneewongvatana , David M. Mount
    Venue: 4th Annual Workshop on Computational Geometry.

How to keep a dead man from shooting.

Through the Labyrinth
Evolution finds a way:
A Silicon Ridge

  • Inman Harvey & Adrian Thompson, Proceedings of the First International Conference on Evolvable Systems, 1996.

J. van der Hoeven. Relax, but don't be too lazy. J. Symb. Comput., 34:479–542, 2002.

Most of Conor McBride's paper titles are very memorable. I can say his paper titles are one reason I have read so many papers on dependent type theory. Some especially memorable ones are:

  • "Do be do be do," S. Lindley, C. McBride & C. McLaughlin, POPL 2017;
  • "Clowns to the left of me, jokers to the right (pearl): dissecting data structures," C. McBride, POPL 2008;
  • "The view from the left," C. McBride & J. McKinna, JFP 14 (1) (2004);
  • "Elimination with a Motive," C. McBride, TYPES 2000.

Many of the "functional pearl" published at ICFP and in JFP have interesting titles, in the very spirit of "functional pearls," which are to be instructive, concise and interesting to read. Towards this end, the authors work hard to come up with interesting titles. Some recent nominees:

  • "What You Needa Know about Yoneda: Profunctor Optics and the Yoneda Lemma," G. Boisseau & J. Gibbons, ICFP 2018;
  • "Oh Lord, Please Don't Let Contracts Be Misunderstood," C. Dimoulas, M. New, R. Findler & M. Felleisen, ICFP 2016;
  • "Two Can Keep a Secret, If One of Them Uses Haskell," A. Russo, ICFP 2015.

From the math world, I have always thought On Starshaped Fuzzy Sets is kind of adorable.

protected by Lev Reyzin Oct 26 '14 at 3:06

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.