tag:blogger.com,1999:blog-3722233.post116527439643071011..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: On Paper TitlesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger30125tag:blogger.com,1999:blog-3722233.post-1165794020105487412006-12-10T17:40:00.000-06:002006-12-10T17:40:00.000-06:00For really bad titles of good papers, how about my...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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165628962198169452006-12-08T19:49:00.000-06:002006-12-08T19:49:00.000-06:00I once saw a paper called "On properties of the em...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165426957052550782006-12-06T11:42:00.000-06:002006-12-06T11:42:00.000-06:00Either it wasn't a barrier after all or you cheate...<I>Either it wasn't a barrier after all or you cheated and changed the model.</I><BR/><BR/>According to this Einstein "cheated" when he changed Newton's model. Of course this is nonsense. If a paper <B>improves</B> the model, more accurately reflecting the problem we intended to solve and henceforth overcoming a previous barrier this is a breakthrough, not a cheat.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165388227765401782006-12-06T00:57:00.000-06:002006-12-06T00:57:00.000-06:00The clue that this one is bogus is found as a pote...<I>The clue that this one is bogus is found as a potential counterargument in the paper...</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165375068115184072006-12-05T21:17:00.000-06:002006-12-05T21:17:00.000-06:00See comment 10 in http://weblog.fortnow.com/2006/0...See comment 10 in <BR/>http://weblog.fortnow.com/2006/06/focs-accepts-and-movie.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165351629501646662006-12-05T14:47:00.000-06:002006-12-05T14:47:00.000-06:00Even though Lance may have broken these rules a fe...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!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165347238063046942006-12-05T13:33:00.000-06:002006-12-05T13:33:00.000-06:00How do you feel about spelling skills?Spelling is ...<I> How do you feel about spelling skills?</I><BR/><BR/>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).<BR/><BR/>Anyway, the paper in ArXiv seems haphazard, careless and it is reasonable to assume that it is also totaly wrong.<BR/><BR/>I wish there would be some sort of filtering in ArXiV -- like in ECCC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165345052674491222006-12-05T12:57:00.000-06:002006-12-05T12:57:00.000-06:00"How to go Beyond the Black Box Simulation Barrier..."How to go Beyond the Black Box Simulation Barrier"<BR/><BR/>According to the rules it could be a terrible title. The paper is not being judged by the title.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165338632599185012006-12-05T11:10:00.000-06:002006-12-05T11:10:00.000-06:00"How to go Beyond the Black Box Simulation Barrier..."How to go Beyond the Black Box Simulation Barrier"<BR/><BR/>According to your rules, this must be a terrible paper. Hmm...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165338048188804622006-12-05T11:00:00.000-06:002006-12-05T11:00:00.000-06:00Regarding“Using disentangled states and algorithmi...Regarding<BR/>“Using disentangled states and algorithmic information theory to solve the P versus NP problem”<BR/><BR/>The clue that this one is bogus is found as a potential counterargument in the paper:<BR/><BR/>"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)."<BR/><BR/>The problem, of course, is that Omega (Chaitin's constant) is uncomputable. If we had access to it, we could solve the halting problem.<BR/>http://en.wikipedia.org/wiki/Chaitin's_constantAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165336609978364412006-12-05T10:36:00.000-06:002006-12-05T10:36:00.000-06:00>I have a healthy suspicion that anyone lacking th...>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.<BR/><BR/><BR/>How do you feel about spelling skills?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165334952609264622006-12-05T10:09:00.000-06:002006-12-05T10:09:00.000-06:00Some variety in titles is a plus. Lots of titles ...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. <BR/> <BR/>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". <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165333409004641782006-12-05T09:43:00.000-06:002006-12-05T09:43:00.000-06:00What about: One complexity theorist's view of quan...What about: One complexity theorist's view of quantum computing ;-)<BR/><BR/>Does it comply with the rules? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165331337157032262006-12-05T09:08:00.000-06:002006-12-05T09:08:00.000-06:00But I disagree that they are an advertisement of f...<I> But I disagree that they are an advertisement of failure; some good papers have had titles like that</I><BR/><BR/><BR/>Like David said, "On" by no means implies failure. Quite a few of the papers that start with "On a problem..." actually solve it. <BR/><BR/><I>> and in any case full disclosure is better than hype.</I><BR/><BR/>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".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165329046889396622006-12-05T08:30:00.000-06:002006-12-05T08:30:00.000-06:00Regarding the paper and the title "New Directions ...Regarding the paper and the title "New Directions in Cryptography", we can now safely say that the title was an understatement...<BR/><BR/>Btw, an earlier version of the paper was called “Multiuser cryptographic techniques”, which by today's standards is vague. <BR/><BR/>MoniAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165328257987316542006-12-05T08:17:00.000-06:002006-12-05T08:17:00.000-06:00But Lance, when are we allowed to break these rule...But Lance, when are we allowed to break these rules?<BR/><BR/>Your own CV has <BR/> -7 papers starting with "On" <BR/> -2 papers ending with a question mark<BR/> -At least a dozen with complexity classes in the title<BR/><BR/>That was just a minute of searching. What are the exceptions to the rule?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165327917864801012006-12-05T08:11:00.000-06:002006-12-05T08:11:00.000-06:00Ending with a Roman NumeralI have been guilty of e...<I>Ending with a Roman Numeral</I><BR/><BR/>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. <BR/><BR/>However, this is true for most mortals. It obviously did not apply to Robertson and Seymour, who titled a series of papers <I>Graph minors. I-XX</I> leading to their proof of Wagner's conjecture.Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165325918606729572006-12-05T07:38:00.000-06:002006-12-05T07:38:00.000-06:00“Using disentangled states and algorithmic informa...<I>“Using disentangled states and algorithmic information theory<BR/>to solve the P versus NP problem”<BR/>No one seems to be very excited, so I presume there is something wrong with this paper?</I><BR/><BR/>Just looking at the first four words (!) of the abstract shows how serious this paper is:<BR/><BR/><I> In this work, are used Chaitin’s number and ... </I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165324955300498592006-12-05T07:22:00.000-06:002006-12-05T07:22:00.000-06:00One of the worst current habbits concerning titles...One of the worst current habbits concerning titles is <B> name dropping </B>: the attempt to impress the reader by concatenating known figures. For instance:<BR/><BR/><BR/>"<I>On a problem of [name1], [name2], [name3] .....</I>"<BR/><BR/>I even saw a paper that didn't bother to start with "on a problem of..", but just went to <BR/><BR/>"<I>[Somthing], [name1], [name2], [name3] ...</I>"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165314791395813362006-12-05T04:33:00.000-06:002006-12-05T04:33:00.000-06:00Yesterday on the ArXiv:quant-ph/0612001http://arxi...Yesterday on the ArXiv:<BR/>quant-ph/0612001<BR/>http://arxiv.org/ftp/quant-ph/papers/0612/0612001.pdf<BR/>Title:<BR/>“Using disentangled states and algorithmic information theory <BR/>to solve the P versus NP problem”<BR/>No one seems to be very excited, so I presume there is something wrong with this paper?<BR/>Jim GraberAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165306740751667472006-12-05T02:19:00.000-06:002006-12-05T02:19:00.000-06:00There again, in tcs there just might be stuff that...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"?Mattihttps://www.blogger.com/profile/05827021033057908563noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165305752299208122006-12-05T02:02:00.000-06:002006-12-05T02:02:00.000-06:00I am actually becoming convinced that the word nov...I am actually becoming convinced that the word <I>novel</I> 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. <BR/><BR/>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 <I>novel</I> implies).Mattihttps://www.blogger.com/profile/05827021033057908563noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165302790714137332006-12-05T01:13:00.000-06:002006-12-05T01:13:00.000-06:00What about "New directions in cryptography" ? That...What about "New directions in cryptography" ? That took some balls...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165299260146232992006-12-05T00:14:00.000-06:002006-12-05T00:14:00.000-06:00A title such as "Random sampling" to me indicates ...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.<BR/><BR/>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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1165293312160701502006-12-04T22:35:00.000-06:002006-12-04T22:35:00.000-06:00How does starting the title with "Improved" indica...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"?!Anonymousnoreply@blogger.com