- 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
- 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(n

^{3/2}log n log log n/log^{*}n)-time one-sided randomized algorithm giving a O(n^{1/3}/(log n)^{4/3}) approximation to 12-sided 3-way 20-dimensional hypergraph coloring." - Long Titles
Ditto.

"A slice of π"

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.

Some of these are pretty funny.

ReplyDeleteAre you sure Bill G. didn't write this post?

Great papers with questionable titles? How about...

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

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

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

>Some of these are pretty funny.

ReplyDelete>Are you sure Bill G. didn't write this post?

Do you see any words in all caps?

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

ReplyDeleteHow 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"?!

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

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

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

ReplyDeleteI am actually becoming convinced that the word

ReplyDeletenovelin 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

novelimplies).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"?

ReplyDeleteYesterday on the ArXiv:

ReplyDeletequant-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

One of the worst current habbits concerning titles is

ReplyDeletename 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“Using disentangled states and algorithmic information theoryto 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.

ReplyDeleteEnding with a Roman NumeralI 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-XXleading to their proof of Wagner's conjecture.But Lance, when are we allowed to break these rules?

ReplyDeleteYour 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?

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

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

Moni

ReplyDeleteBut I disagree that they are an advertisement of failure; some good papers have had titles like thatLike 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".

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

ReplyDeleteDoes it comply with the rules? :)

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.

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

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

ReplyDeleteHow do you feel about spelling skills?

Regarding

ReplyDelete“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

"How to go Beyond the Black Box Simulation Barrier"

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

"How to go Beyond the Black Box Simulation Barrier"

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

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

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!

ReplyDeleteSee comment 10 in

ReplyDeletehttp://weblog.fortnow.com/2006/06/focs-accepts-and-movie.html

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

ReplyDeleteEither 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

improvesthe model, more accurately reflecting the problem we intended to solve and henceforth overcoming a previous barrier this is a breakthrough, not a cheat.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?

ReplyDeleteFor 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