Monday, December 04, 2006

On Paper Titles

How do you take a twenty page research paper and condense its essence into a few words? A couple of title don'ts with some (made up) examples.
  • Starting a title with "On", "Towards", "New" or "Improved" or ending with "?"
    You are announcing that you have failed to solve the problem you really care about and this is the best you can do. Nobody would title a paper proving P≠NP "On an Open Problem of Cook".
  • "Breaking the … Barrier"
    Either it wasn't a barrier after all or you cheated and changed the model.
  • Cutesy Titles
  • "A slice of π"
  • Ending with a Roman Numeral
    "Pig Complexity I". Does the world need more than one paper on pig complexity?
  • Out of Context Titles
    "Three rounds suffice"
  • Technical Terms
    Don't use highly technical terms or complexity classes in the title. Any computer scientist should at least understand the words in the title.
  • Formal Statement of Result
    "A O(n3/2log n log log n/log* n)-time one-sided randomized algorithm giving a O(n1/3/(log n)4/3) approximation to 12-sided 3-way 20-dimensional hypergraph coloring."
  • Long Titles
    Ditto.
What makes a good title? Short and to the point. Some of several titles I liked from the last FOCS: "Cryptography from Anonymity", "Fault-Tolerant Distributed Computing in Full-Information Networks", "Planar Point Location in Sublogarithmic Time". Enough to give you the idea of the paper and the desire to read more.

I went through my bibtex file trying to find great papers with lousy titles. Except for a few "On"s (On computable numbers, with an application to the Entscheidungsproblem), great papers seem to have at least reasonable titles. A lesson for all of us paper titlers.

30 comments:

  1. Some of these are pretty funny.
    Are you sure Bill G. didn't write this post?

    ReplyDelete
  2. Great papers with questionable titles? How about...

    . "Mick gets some (the odds are on his side)" by Chvatal and Reed

    . "The importance of being biased" (by Dinur and Safra, retitled for Annals of Math as "On the Hardness of Approximating Minimum Vertex-Cover")


    I'm also impressed that Noga Alon, Asaf Shapira, and Oded Schwartz titled their SODA '07 paper "Random Sampling".

    ReplyDelete
  3. I think your post would benefit from some more explanation of why your don'ts are don'ts:

    - Words like "on", "towards", etc make the title longer without making it more informative or memorable. They are wasted space. But I disagree that they are an advertisement of failure; some good papers have had titles like that, and in any case full disclosure is better than hype.

    - "Blasting through the information-theoretic barrier" and similar titles: this sort of thing can make your title memorable, which is good, but can also lead people to think you're overhyping your results.

    - Cutesy titles: guilty as charged. I don't see them as wrong per se. I see this as a taste issue (Lance doesn't like them, but some other people do) rather than useful general advice. The problem with "A slice of π" isn't that it's cute, it's that it's uninformative. Cuteness can help make a title memorable but won't help draw readers to the paper if they don't know what it's about.

    - Out of context: same problem as with "A slice of π", insufficiently informative.

    - Technical terms: can be ok if you don't mind limiting your readership to people who understand those terms. Sometimes the content of a paper is very technical, and there's no harm in warning the readers of that.

    - Notation in titles: a very bad idea. The reason has nothing to do with human readers: it's that automated indexing systems such as Google Scholar are more likely to get confused and misindex your work. In addition, this part of the title is likely to be corrupted in listings containing your paper.

    In summary: short, memorable, and informative are all important qualities to aim for. Cutesiness can help on the memorability axis but shouldn't impede informativeness. Notation in a title is a much bigger sin than the other issues.

    ReplyDelete
  4. >Some of these are pretty funny.
    >Are you sure Bill G. didn't write this post?

    Do you see any words in all caps?

    ReplyDelete
  5. If I have the extremely good fortune to be the person who prove P!=NP, I'm definitely titling it "On an Open Problem of Cook."

    ReplyDelete
  6. How does starting the title with "Improved" indicate a failure to solve the problem? Because you haven't concocted a setting in which it's "optimal"?!

    ReplyDelete
  7. A title such as "Random sampling" to me indicates that the authors claim that they are the first to ever do this, that they are the first to do it right, or that the paper is a survey. I haven't read the Alon-Shapira-Schwartz paper, so I don't know what category, if any, it belongs into.

    My pet peeve has always been paper titles that are generic enough to be applicable to heaps of papers. E.g. "Zero-knowledge proofs made easy" (I just made this title up, I hope I don't offend anybody). That said, it's hard to come up with a title that is both short and specific - there are only so many titles with less than ten words...

    ReplyDelete
  8. What about "New directions in cryptography" ? That took some balls...

    ReplyDelete
  9. I am actually becoming convinced that the word novel in the title of an article means that there's not much worth reading. Title is, after all, the part of the article that tells you what's worthwhile in the article.

    And if the word that describes your work best is "new", then the value of your contribution is quite dubious, uh? I'd like to read articles that describe how to do things "faster", "easier", "clearer", etc., instead of just "differently" (which is what novel implies).

    ReplyDelete
  10. There again, in tcs there just might be stuff that is best characterized "novel". What if Turing had named his 1936 paper "A novel approach to automatic computation"?

    ReplyDelete
  11. Yesterday on the ArXiv:
    quant-ph/0612001
    http://arxiv.org/ftp/quant-ph/papers/0612/0612001.pdf
    Title:
    “Using disentangled states and algorithmic information theory
    to solve the P versus NP problem”
    No one seems to be very excited, so I presume there is something wrong with this paper?
    Jim Graber

    ReplyDelete
  12. One of the worst current habbits concerning titles is name dropping : the attempt to impress the reader by concatenating known figures. For instance:


    "On a problem of [name1], [name2], [name3] ....."

    I even saw a paper that didn't bother to start with "on a problem of..", but just went to

    "[Somthing], [name1], [name2], [name3] ..."

    ReplyDelete
  13. “Using disentangled states and algorithmic information theory
    to solve the P versus NP problem”
    No one seems to be very excited, so I presume there is something wrong with this paper?


    Just looking at the first four words (!) of the abstract shows how serious this paper is:

    In this work, are used Chaitin’s number and ...

    I have a healthy suspicion that anyone lacking the most basic grammer skills (or worse, that doesn't take the trouble to correct such mistakes in a published paper) can solve the P=NP problem. But I may be wrong after all.

    ReplyDelete
  14. Ending with a Roman Numeral

    I have been guilty of ending the title of a paper with "I", and the planned companion paper never saw the light of day, alas. I know of several other instances of this phenomenon, which offers another good reason for following Lance's advice.

    However, this is true for most mortals. It obviously did not apply to Robertson and Seymour, who titled a series of papers Graph minors. I-XX leading to their proof of Wagner's conjecture.

    ReplyDelete
  15. But Lance, when are we allowed to break these rules?

    Your own CV has
    -7 papers starting with "On"
    -2 papers ending with a question mark
    -At least a dozen with complexity classes in the title

    That was just a minute of searching. What are the exceptions to the rule?

    ReplyDelete
  16. Regarding the paper and the title "New Directions in Cryptography", we can now safely say that the title was an understatement...

    Btw, an earlier version of the paper was called “Multiuser cryptographic techniques”, which by today's standards is vague.

    Moni

    ReplyDelete
  17. But I disagree that they are an advertisement of failure; some good papers have had titles like that


    Like David said, "On" by no means implies failure. Quite a few of the papers that start with "On a problem..." actually solve it.

    > and in any case full disclosure is better than hype.

    Exactly, often those papers with "On" are borne out of modesty. There is something pretentious if not downright crackpottish about titleing your paper "P=NP".

    ReplyDelete
  18. What about: One complexity theorist's view of quantum computing ;-)

    Does it comply with the rules? :)

    ReplyDelete
  19. Some variety in titles is a plus. Lots of titles like "An {adjective} algorithm/lower bound for the {noun} problem" make things pretty boring. I must admit to being partial to the joke in the 'Mick gets his (the odds are on his side)' title and it really made me want to attend the talk to hear more.

    In addition to Best Paper awards maybe we should have Best Title awards. At the last FOCS, Les Valiant would have won for his title "Accidental Algorithms".

    Finally, I disagree with Lance's assertion about "On" (though it is over-used). When I see a paper whose title begins with "On" I expect an amount of thoroughness. Without the "On" I expect the first or last paper on the subject but not neceesarily thoroughness. (The "On" in the title of this blog entry somehow indicated Lance's attempt at thoroughness.) Given the inability of our field to settle so many questions, "On" papers may be the best we can get.

    ReplyDelete
  20. >I have a healthy suspicion that anyone lacking the most basic grammer skills (or worse, that doesn't take the trouble to correct such mistakes in a published paper) can solve the P=NP problem. But I may be wrong after all.


    How do you feel about spelling skills?

    ReplyDelete
  21. Regarding
    “Using disentangled states and algorithmic information theory to solve the P versus NP problem”

    The clue that this one is bogus is found as a potential counterargument in the paper:

    "One can argue that to generate Omega_ST maybe itself a problem not in P. Let me assume that the computer used to solve the proposed problem has infinite amount of memory and Omega is stored there (this maybe a problem because it is still necessary to have other data in memory and some contradictions may arise, but this point will not be considered here)."

    The problem, of course, is that Omega (Chaitin's constant) is uncomputable. If we had access to it, we could solve the halting problem.
    http://en.wikipedia.org/wiki/Chaitin's_constant

    ReplyDelete
  22. "How to go Beyond the Black Box Simulation Barrier"

    According to your rules, this must be a terrible paper. Hmm...

    ReplyDelete
  23. "How to go Beyond the Black Box Simulation Barrier"

    According to the rules it could be a terrible title. The paper is not being judged by the title.

    ReplyDelete
  24. How do you feel about spelling skills?

    Spelling is somewhat less important. But, surely, anyone (like me) for whom English is not the native language should take special care when he publishes a paper that the spelling is correct (naturally, when I'm writing comments I'm much less careful).

    Anyway, the paper in ArXiv seems haphazard, careless and it is reasonable to assume that it is also totaly wrong.

    I wish there would be some sort of filtering in ArXiV -- like in ECCC.

    ReplyDelete
  25. Even though Lance may have broken these rules a few times as a some commenters have pointed out, we should give him a break. After all, the post title is "On Paper Titles" so he isn't claiming to have solved the problem!

    ReplyDelete
  26. See comment 10 in
    http://weblog.fortnow.com/2006/06/focs-accepts-and-movie.html

    ReplyDelete
  27. The clue that this one is bogus is found as a potential counterargument in the paper...

    No, it's much easier; the paper doesn't pass the MS Word Test. The revolution will not be televised, and the P vs. NP resolution will not be typeset in Word.

    ReplyDelete
  28. Either it wasn't a barrier after all or you cheated and changed the model.

    According to this Einstein "cheated" when he changed Newton's model. Of course this is nonsense. If a paper improves the model, more accurately reflecting the problem we intended to solve and henceforth overcoming a previous barrier this is a breakthrough, not a cheat.

    ReplyDelete
  29. I once saw a paper called "On properties of the empty set". As I recall, it dealt with formal languages, and showed an undecidability result on the emptiness problem. How's that for a way-too-cute title?

    ReplyDelete
  30. For really bad titles of good papers, how about my paper with Ken Clarkson "Applications of random sampling in computational geometry II." Mistake number one: never write a sequel to a paper that doesn't exist (there's a paper called "New applications of random sampling in computational geometry," which our paper is supposedly the sequel to, but dropping the "new" caused an incredible amount of confusion).

    ReplyDelete