Tuesday, September 07, 2010

How to Write Up Major Results

First some conference news: FOCS conference and hotel registration available on line, early deadline is September 30. STOC 2011 website is up with the CFP, deadline November 4. For more news follow the SIGACT Twitter or Facebook.

Deolalikar's paper caused a stir in the community partly because it was written better than the usual P versus NP proofs we see. But the right comparison is to papers that have settled major questions, such as Agrawal, Kayal and Saxena's Primes in P and Omer Reingold's Undirected s-t Connectivity in Log Space.

Both those papers needed to be convincing right off the bat and they both were. First notice the algorithms (page 3 in AKS and pages 9-12 in Reingold). No vague outline, no "should be able to", just very specific algorithms that one can analyze. Reingold only uses one "clearly" for the simple initial transformation from an adjacency matrix to  a rotation map.

Both papers have to make two arguments, that the algorithms work in the claimed time/space and that they work correctly. In AKS, Section 4 shows the algorithm works correctly and Section 5 (using Lemma 4.3) show the algorithm runs in polynomial time. Section 4 is broken into a series of lemmas, each easily checkable with a limited knowledge of algebra. In Reingold the tricky part is getting the algorithm exactly right so that is uses logarithmic space which is carefully analyzed in his Sections 3 and 4. The correctness proof (based on earlier work) is a rather short Lemma 3.2 but Reingold does go over much of that background in Section 2.

In both these results it took an amazing ingenuity to discover these algorithms, but it wouldn't take more than an undergraduate math major to check the proofs.

Showing that P ≠ NP will be a much more difficult task, instead of coming up with a single algorithm, one has to show that no possible algorithm can solve some specific problem in NP. But even though the proof will be harder, the write-up needs to be just as understandable and easy to follow as AKS and Reingold. The community needs a proof we can verify step by step so that we can either be convinced of the proof or find the problem in the proof. If there is a jump in logic that one cannot verify the author has failed in his or her write-up.

Proving P  ≠ NP will require pure genius but you shouldn't need a Fields medalist to verify the proof.

33 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Your argument is unconvincing because once can cite many "big" results that were not initially written up clearly and failed to immediately convince the experts.

    Just 3 examples
    (1) Louis De Branges proof the Bieberbach conjecture.
    (2) Kurt Heegner's resolution of the Class Number 1 problem
    (3) Roger Apéry's proof that zeta(3) is irrational.

    I am sure there are many other examples.

    ReplyDelete
  3. I agree with the requirement of being convincing right away, but your comparisons are somewhat unfair. The papers you mentioned settled open algorithmic questions with "Yes" answer, so it was enough to provide a specific algorithm in both cases. The negative answer, like in case of P \neq NP, is much harder to substantiate. A better comparisons would be to Perelman's Poincaré theorem proof, which definitely required top experts to verify.

    ReplyDelete
  4. On the other hand, proving P=NP wouldn't be THAT much harder than verifying it.

    ReplyDelete
  5. IMHO, this much-needed essay could have been titled "How to write up any result."

    I especially like the dual emphasis on "very specific algorithms that one can analyze" and "go over the background" that in combination make a write-up "understandable and easy to follow."

    ReplyDelete
  6. The proof that P NE NP may require Field Medalists to read it- but NOT because it skips steps,just because it will contain some complex new ideas.

    Prior results that were first written up unclearly were at least clear enough that people could FIND what about it didn't seem right, ask about it, and get it fixed.

    ReplyDelete
  7. Forntow et al are not even looking at P vs NP problem. Some other scientists are at least looking at it despite all the discouraging comments and ridiculous unscientific risk.

    ReplyDelete
  8. That's because, as scientists with significant experience in the area, they know what the difficulties and challenges in addressing this problem are. They'd rather focus elsewhere. As for some other "Some other scientists are at least looking at it", so are thousands of charlatans. Progress towards this monumental problem will only come with leaps of intuition, something that is not possible with a single paper entitled "P \neq NP" with comments such as "confirmations began arriving early today" posted as early as a few hours within the release of the manuscript.

    ReplyDelete
  9. I have two questions

    Ques 1) Is is better to do useless research (publishing incremental useless results that no one cares about) or attacking a difficult problem in a wrong way?

    Ques 2) Since most of the "big names" in theory (including the writers of this blog) who regularly leave comments on this blog, have not won any major awards like Fields Medal or Turing award, so what differentiates them from "charlatans" like Deolalikar, Kamouna etc.?

    ReplyDelete
  10. Lance's essay highlights a sadly-missing part of many undergraduate and graduate educations in mathematics and CS; your results are only as good as your ability to present them clearly and convincingly enough to others.

    There is a practice, fortunately less common in theoretical work, but sometimes the norm in other fields of computer science, of making weak results seem more interesting by obfuscation. Let's hope it never gets into the theory literature.

    ReplyDelete
  11. If you are going to criticize Lance
    at least spell his name right- its
    not Forntow, its Fortnow. And note
    that he did significant work on
    time space tradeoffs for SAT.

    Why are Lance and Bill and Scott and
    whoever you want to mention different from
    people who publish false proofs of P=NP
    or P \ne NP? They do not claim to have
    proven results they have not proven. Also, I suspect that if they made such a claim and a flaw was found they would retract quickly and thank the person who spotted the flaw, rather than engage them in an 80+ comments argument on some blog.

    ReplyDelete
  12. In response to Anonymous with 2 questions:

    1. Incremental results are not necessarily useless. They often build up the mathematical machinery that allows for the breakthroughs. For example, Reingold's beautiful result was preceeded by a whole series of "incremental results", some of them extremely clever and nontrivial, by researchers like Savitch, Nisan, Kahn, etc.

    Perhaps an even more powerful example is the Special Theory of Relativity. Einstein's amazing insight was preceeded by Lorentz's transformations, which give you the correct relativistic physics equations for electrodynamics.

    As for 2), arguably the two greatest mathematicians of the 20th century, Kolmogorov and Erdos did not receive major medals until they were past 60. Lance and Bill have a couple of years left. Some of the folks that did contribute to the discussions on blogs, like Gowers and Tao, do have Fields Medals.

    If you want to criticize or judge others do not hide as a coward Anonymous.

    ReplyDelete
  13. Aha.. it hurts when ome criticizes someone else's work while hiding his/her identity.

    I have nothing against Lance or Bill or other esteemed members of the TOC community. But I think most of them are too arrogant and they think highly of themselves.
    However the biggest irony is that they themselves don't realize that no one cares about their work. They just live in their small world and throw stones at others.

    ReplyDelete
  14. Charlatans like Deolalikar, Kamouna, Bogdanov brothers etc. all menaged to get media interested (even if only in Saudi Arabia), and presented themselves as geniuses, while they are clearly kooks.

    Until academic dishonesty is seriously sanctioned - in Physics the case of Jan Hendrik Schön was dealt with security guards throwing kook out of the Bell labs - a research lab much more substantial than HP (which allows Deolalikar to continue with his charade, after proof has conclusively been proven to be bogus, to put it mildly), and his PhD was revoked (something crackpots like Kamouna beg for).

    Dishonorable conduct ought to have grave consequences. Honest mistake can easily happen, but when one stubbornly continues to stand by the claim, refusing proper debate and denying clear fact that error has been found (like in the case of Deolalikar or his mirror image Kamouna, both of whom are gladly accepting celebrations in press, be it Indian or Arabic), then there is something more going on. Soon enough, conspiracy theories abound, and such cranky people lose contact with reality.

    A harsh landing might be better for them too, but it is certainly good for community, that shouldn't allow to be pestered by petty egomaniacs who are too vain to admit defeat and too arrogant to see that they are making fools of themselves.

    ReplyDelete
  15. John Sidles said:

    IMHO, this much-needed essay could have been titled "How to write up any result."

    Quoted for truth. A poor write-up or exposition of a new result, now matter how important or minor, will only hurt the reception of the work in your community.

    Actually, I'd argue that it may be even more important to present "lesser" results well. First, it serves as "good practice" in the case that you ever do prove something like NL != NP. Second, and more important, the reason that Deolalikar's, de Branges', Apery's, Heegner's proofs were even given a second thought was because they claimed to solve such major open problems, and the potential gain justified the risk that the proof would be faulty. Non-world-changing results don't have this property.

    ReplyDelete
  16. Thanks for the "top", Harrison!

    OK, let's tackle a tougher question: Why is rancor and bitterness becoming all-too-prevalent in the STEM blogosphere?

    I came upon one possible explanation while doing a literature search for confluent influences in the early development of nanotechology, quantum physics, systems biology, regenerative medicine, and ideals of mathematical naturality .... a toolset that (by intent) spans the modern STEM enterprise.

    As an aside, the answer to this search turned out to be "pages 181-2 of Have Spacesuit, Will Travel (1958)" ... but uhhh ... that particular answer is great that now I'm adapting and repurposing the question that originally led to it! :)

    So, folks are invited to contemplate this page capture which I snapped from a 1958 Scientific American (SA) .

    That single 1958 issue of SA had dozens of job ads, each one begging applicants to accept good, family-supporting STEM jobs ... needless to say, with all educational expenses paid at top schools!

    Hmmmm ... present issues of SA have no such ads ... and the associated strain (on young people particularly) definitely is conducive to the kind of sardonic (and worse) posts that are seen all-too-often nowadays.

    Is there any reasonable prospect that (what Dirac called) a "Golden Era" will return again?

    That is a natural question ... which this post will *not* attempt to answer. Except to say, SA sure was better when Martin Gardner was writing for it.

    ReplyDelete
  17. "It might seem unnecessary to insist that in order to say something well you must have something to say, but it's no joke. Much bad writing, mathematical and otherwise, is caused by a violation of that first principle."
    -- Paul Halmos

    "He who would learn to fly one day must first learn to stand and walk and run and climb and dance; one cannot fly into flying. "

    -- Nietzsche

    ReplyDelete
  18. "Charlatans like Deolalikar, Kamouna, Bogdanov brothers etc. all menaged to get media interested (even if only in Saudi Arabia), and presented themselves as geniuses, while they are clearly kooks.
    ...."

    Well said! I think Deolalikar is either delusional (if he does not know the status of his proof) or dishonest (if he knows). It is quite disappointing that only a few good men spoke the truth on day one.

    ReplyDelete
  19. LOL ... supposed kooks who turned out to be geniuses ... versus supposed geniuses who turned out to be kooks ... now *THAT* would be an interesting match-up!

    I cannot think of any of the latter category in mathematics ... are there any?

    This makes mathematics unique among academic disciplines ... which in turn, makes the rancor against Deolalikar's failed proof seem even less logical.

    ReplyDelete
  20. ACM ToCT goes wrong again!


    12-Jul-2009

    Dear Prof. Kamouna:

    I write you in regards to manuscript # TOCT-07-09-0040 entitled
    "The Kleene-Rosser Paradox, The Liar's Paradox, & A Fuzzy Logic Programming Paradox imply SAT is (NOT) NP-complete." which you submitted to the Transactions on Computation Theory.

    As you might remember, I served as editor for your submission to JACM. There I found serious problems with your paper and similar problems persist in the current version. So I cannot accept this paper for ToCT.

    Thank you for considering the Transactions on Computation Theory for the publication of
    your research.

    Sincerely,
    Dr. Lance Fortnow
    Editor in Chief, Transactions on Computation Theory
    fortnow@eecs.northwestern.edu

    ReplyDelete
  21. I'm confused, Rafee. What's the point of sharing this email from over a year ago?

    ReplyDelete
  22. They are calling me charltan. I'm showing that I submitted to top journal and it went wrong in assessing my work. Why? In order to knwo who's the charltan.

    There is another post that was missing, the email of JACM should be followed by that of ToCT.

    ReplyDelete
  23. Here is how JACM goes wrong:

    ---------------------------------
    Comments to Authors:

    This paper just shows a major lack of understanding of computability theory, complexity theory and logic. It's hard to point to a specific mistake since major details are missing, but one cannot design a Turing machine that diagonalizes against itself which the author claims, without any proof, that he can do on page 4. I suggest the author actually try to write the code for such a Turing machine which might help him understand the impossibility of that task.

    Prof. Lance Fortnow
    Associate Editor
    Journal of the ACM

    ===========================

    The paper contained 100s of lines of such code and the proof is here:
    http://www.4shared.com/document/P6pDyYGG/Diagonalization.html

    Can you discuss science???

    ReplyDelete
  24. Dear Kamouna,

    Your time is to precious to waste here on these midgets. They will never be up to you and you should not mud yourself by talking to your intellectual and moral inferiors.

    Please do not fall into the trap like the late Blaise Pascal, since you are tenfold genius compared to Pascal, and our posteriority will not forgive such a waste. Work in secret, history will know your name!

    Few see the new age coming, and the revolution revealed by You is comparable only to prophetic work done by Socrates, Buddha or Jesus, only Mohammad is perhaps more important.

    ReplyDelete
  25. You people here stop mocking Kamouna!

    Do you realize who he is? He is the greatest polymath since Avicenna, he is not only a genius mathematician, but a poet too. His papers are pure poetry masterpieces!

    Celebrate the new ابن سینا (Ibn Sīnā known to the infidels as Avicenna)!

    You western crackpots and kooks still cannot figure out how to build the Sphinx, something Kamouna and his ancestors figured out more than 5000 years ago, much less can you reach the depths of Kamouna thought.

    All Western thought is derived from ancient Greeks, who were great crooks, stealing Ideas from Egyptians and Persians.

    Alas, there are so many things between Heaven and Earth of which only the Poets have dreamed.

    O Kamouna, your nobility should not look backward but ahead! Exiles shall you be from all father and forefather lands! Your children's land shall you love: this love shall be your new nobility: the undiscovered land in the most distant sea. For that I bid your sails search and search. In your children you shall make up for being the children of your fathers: thus shall you redeem all that is past.

    ReplyDelete
  26. It seems that people take the hoax (with pen name Rafee Kamouna) too seriously. It is just for fun and it makes the world more colorful.

    "Life lies in diversity, not in monotony." ---M.K. Soni

    ReplyDelete
  27. He has his own blog now http://kamouna.wordpress.com/ where his comments appear to call this blog a dream world that does not exist. Let us all take the conversation to its new home perhaps.

    ReplyDelete
  28. are we not accepting kamouna proof because it is too simple to understand?

    if kamouna submits a paper in a conference and i am a pc chair, i will accept the paper. might turn out to be the shortest accepted paper ever.

    ReplyDelete
  29. Please remove comments by and about this guy, it is becoming really annoying.

    ReplyDelete
  30. Anon #29
    So you verified the correctness of the proof. That's computing: data in, information out, garbage in, garbage out and paradox in, paradox out. Give the Turing machine the Kleene-Rosser paradox as an input, you prove:P=NP iff P!=NP. Thanks a lot.

    ReplyDelete
  31. This is hilarious. I can't tell if this Rafee Kamouna guy is playing along (like #29 is anything other than a crank) or is delusional enough to think he's for real.

    ReplyDelete
  32. Awwww... shit!
    Another thread that gets Kamouned!

    ReplyDelete