What I find most interesting is that Deolalikar did not submit the paper to a journal, as far as I know. He didn’t even post it on arxiv likeÂ Perelman. Yet, he is receiving much attention. His name is being tweeted several times a minute. Many of the most influential theoretical computer scientists are reacting to the paper.Â He is getting the best peer review possible. Most similar papers don’t get so much attention.
Why is this paper different?
- Everyone seems to agree that the paper is well written, it has nice (color!) figures and the reference section appears up-to-date and complete. Â If your result is important, communicate it well.
- Deolalikar has published just a handful of papers in theoretical computer science, and none at the major conferences. But he has enough peer-reviewed research papers to be treated as a peer.
- While I doubt he was hired to work on complexity theory, Deolalikar is an industry researcher at HP. Being paid to do research might make you more credible.
Update: Porreca has the best write-up on reactions to this paper.
Update 2: The consensus after two weeks is that the proof wrong and unfixable.