From http://weblog.fortnow.com/2006/12/on-paper-titles.html.

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.

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.

Comment:

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