5 ms·

Head spinning. At least I got that bit about LFP... mostly. The coolest thing about this all is watching the Internet doing what it was built for. Real-time co

by sprout 16y ago

Head spinning. At least I got that bit about LFP... mostly. The coolest thing about this all is watching the Internet doing what it was built for. Real-time collaboration on a massive scale. The whole of the relevant scientific communities all in one virtual space clamoring at a hundred virtual whiteboards. I love living in the future.

Jun8 16y ago
Precisely! I found the crowdsourcing approach that got started at http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-cro... amazing. Terence Tao had done a similar thing, not for paper review but to prove some theorems. Compared to this, the rigid approach adopted in Math Overflow to close any discussion on the issue seems so 19th century. See the discussion here: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/
- sidww2 16y ago
  I think the stance taken by MathOverflow is correct. It would be one thing if that were the only venue to have a discussion about the proof validity possible but there exist much better discussion mediums. The linked blog is a case in point. MathOverflow is geared towards being a Q&A site.
  - aswanson 16y ago
    Totally agree. MO seems to enforce an rigid, sanitary culture for precise question and answering. Perfect approach to mathematical discovery and enlightenment.
    - eru 16y ago
      What makes you think so? I always found the process of discovery (when you are working stuff out on your own) to be quite messy. You clean up only after you have found your way. For discovery by reading another one's work, I agree that cleanliness helps. (That's one of the reasons to clean up your work in the first place.)
      - aswanson 16y ago
        The communication part, which you alluded to in terms of reading someone else's work, is what I was referring to.
- mfukar 16y ago
  I wouldn't trust a (relatively new, correct?) Q&A site with commenting on research-level work, at least not above the level of informal chat. While outsiders, id est people largely not acquainted with the subject at hand or lacking the expertise, can provide a fresh perspective, I would not expect the benefits from a discussion on such a high-level to outweigh the potential distractions and/or misguided approaches. Let alone other issues that arise with discussing unpublished work. On the other hand, a discussion in the spirit of "what are the concepts behind this proof?", or "what are the implications if this proof is correct/wrong?", or even "what is the approach of this proof? what are the pitfalls associated with such a process?" are excellent ways of disseminating knowledge and educating about the subject a) without having to resort to the few experts on the field and b) keeping the content in line with the principles of a Q&A site.
  - omaranto 16y ago
    You don't sound familiar with MathOverflow: it is for research level questions in mathematics, and for the most part lives up to that purpose. The reason I wouldn't want to read about this paper there is that the MathOverflow users don't seem to include many computer scientists; they are mostly mathematicians who work in non-computery areas of math. In other words, I would go to MathOverflow for comments on a breakthrough paper in certain areas, just not this one.
joe_the_user 16y ago
I haven't looked at the proof in any kind of detail. But comments by Jame S. Gates etc. raise a question in my mind. Any statical argument that a given phenomena is unlikely is based on the space of phenomena behaving very roughly "communatively" - AB and BA equally likely or at least correlated. How do you apply that kind of reasoning to a totally arbitrary process of computation, a process which wouldn't necessarily have respect any kind of randomness? It seem like any statistical argument for P=/NP has to have a detailed and direct discussion of how you can escape this problem. Anyway, that's my crude effort to translate the discussion into my mere math MA understanding...
- Tichy 16y ago
  I also don't have high hopes for the statistical angle, in fact I seem to remember that statistical arguments have been around for a long time. But they are not good enough as a proof.
- tetha 16y ago
  Note, I have not read the paper in detail yet, I just want to explain certain statistical proof techniques which are quite counter-intuitive to me, and maybe help you :) You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist. For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist. Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.
- nonce3232321 16y ago
  Probabilistic arguments for deterministic systems are standard practice. Search for Erdős and probabilistic methods to see several examples in combinatorics. In computation theory many proofs have the tagline "...with probability 1", meaning the author enumerated all desired possibilities and showed their probabilities summed to one. Most people accept this as proof, although it is less preferred, in the way that proof by contradiction is less favored than direct proof.
hristov 16y ago
"The coolest thing about this all is watching the Internet doing what it was built for." And that would be commenting on a paper before anyone has finished reading it? Just kidding.
- Confusion 16y ago
  Well, that's an interesting point actually. Not just commenting before they have finished reading it: also commenting without enough knowledge to say anything useful about it. Moderators on meta.mathoverflow.com decided not to allow possibly premature discussions on mathoverflow: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/. The arguments are quite reasonable: So answers could linger on MO asserting that some parts of the proof are correct, other sketchy, other flat out wrong and precious few people will be able to decide for sure if this is true or not.
  - sprout 16y ago
    Consensus is an imperfect metric. Some of those things, even if discarded by consensus in the near-to-long term could prove valid in a couple years' time. We want as many avenues of exploration as possible, even once the proof is decided right or wrong.
  - tqft 16y ago
    A minor point: that decision on meta.mathoverflow.net barely involved the moderators at all. One said what he was inclined to do, but otherwise it was the MO community.
- tetha 16y ago
  I am not entirely sure about myself here, but I think, I kind of like the way people handle this. Sure, there will be a lot of questions which are trivial to someone deep in the field and even more questions which are already answered in the paper, but these should be removed pretty fast. However, those questions which are not answered via "See page X" or "Look in that book, page X" will need explanation and will strengthen trust in this proof, should it be correct.

by sprout 16y ago

Jun8 16y ago

Precisely! I found the crowdsourcing approach that got started at http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-cro... amazing. Terence Tao had done a similar thing, not for paper review but to prove some theorems. Compared to this, the rigid approach adopted in Math Overflow to close any discussion on the issue seems so 19th century. See the discussion here: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/

sidww2 16y ago
I think the stance taken by MathOverflow is correct. It would be one thing if that were the only venue to have a discussion about the proof validity possible but there exist much better discussion mediums. The linked blog is a case in point. MathOverflow is geared towards being a Q&A site.
- aswanson 16y ago
  Totally agree. MO seems to enforce an rigid, sanitary culture for precise question and answering. Perfect approach to mathematical discovery and enlightenment.
  - eru 16y ago
    What makes you think so? I always found the process of discovery (when you are working stuff out on your own) to be quite messy. You clean up only after you have found your way. For discovery by reading another one's work, I agree that cleanliness helps. (That's one of the reasons to clean up your work in the first place.)
    - aswanson 16y ago
      The communication part, which you alluded to in terms of reading someone else's work, is what I was referring to.
mfukar 16y ago
I wouldn't trust a (relatively new, correct?) Q&A site with commenting on research-level work, at least not above the level of informal chat. While outsiders, id est people largely not acquainted with the subject at hand or lacking the expertise, can provide a fresh perspective, I would not expect the benefits from a discussion on such a high-level to outweigh the potential distractions and/or misguided approaches. Let alone other issues that arise with discussing unpublished work. On the other hand, a discussion in the spirit of "what are the concepts behind this proof?", or "what are the implications if this proof is correct/wrong?", or even "what is the approach of this proof? what are the pitfalls associated with such a process?" are excellent ways of disseminating knowledge and educating about the subject a) without having to resort to the few experts on the field and b) keeping the content in line with the principles of a Q&A site.
- omaranto 16y ago
  You don't sound familiar with MathOverflow: it is for research level questions in mathematics, and for the most part lives up to that purpose. The reason I wouldn't want to read about this paper there is that the MathOverflow users don't seem to include many computer scientists; they are mostly mathematicians who work in non-computery areas of math. In other words, I would go to MathOverflow for comments on a breakthrough paper in certain areas, just not this one.

joe_the_user 16y ago

I haven't looked at the proof in any kind of detail. But comments by Jame S. Gates etc. raise a question in my mind. Any statical argument that a given phenomena is unlikely is based on the space of phenomena behaving very roughly "communatively" - AB and BA equally likely or at least correlated. How do you apply that kind of reasoning to a totally arbitrary process of computation, a process which wouldn't necessarily have respect any kind of randomness? It seem like any statistical argument for P=/NP has to have a detailed and direct discussion of how you can escape this problem. Anyway, that's my crude effort to translate the discussion into my mere math MA understanding...

Tichy 16y ago
I also don't have high hopes for the statistical angle, in fact I seem to remember that statistical arguments have been around for a long time. But they are not good enough as a proof.
tetha 16y ago
Note, I have not read the paper in detail yet, I just want to explain certain statistical proof techniques which are quite counter-intuitive to me, and maybe help you :) You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist. For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist. Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.
nonce3232321 16y ago
Probabilistic arguments for deterministic systems are standard practice. Search for Erdős and probabilistic methods to see several examples in combinatorics. In computation theory many proofs have the tagline "...with probability 1", meaning the author enumerated all desired possibilities and showed their probabilities summed to one. Most people accept this as proof, although it is less preferred, in the way that proof by contradiction is less favored than direct proof.

hristov 16y ago

"The coolest thing about this all is watching the Internet doing what it was built for." And that would be commenting on a paper before anyone has finished reading it? Just kidding.

Confusion 16y ago
Well, that's an interesting point actually. Not just commenting before they have finished reading it: also commenting without enough knowledge to say anything useful about it. Moderators on meta.mathoverflow.com decided not to allow possibly premature discussions on mathoverflow: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/. The arguments are quite reasonable: So answers could linger on MO asserting that some parts of the proof are correct, other sketchy, other flat out wrong and precious few people will be able to decide for sure if this is true or not.
- sprout 16y ago
  Consensus is an imperfect metric. Some of those things, even if discarded by consensus in the near-to-long term could prove valid in a couple years' time. We want as many avenues of exploration as possible, even once the proof is decided right or wrong.
- tqft 16y ago
  A minor point: that decision on meta.mathoverflow.net barely involved the moderators at all. One said what he was inclined to do, but otherwise it was the MO community.
tetha 16y ago
I am not entirely sure about myself here, but I think, I kind of like the way people handle this. Sure, there will be a lot of questions which are trivial to someone deep in the field and even more questions which are already answered in the paper, but these should be removed pretty fast. However, those questions which are not answered via "See page X" or "Look in that book, page X" will need explanation and will strengthen trust in this proof, should it be correct.