P ≠ NP and the future of peer review

1 Leave a comment on paragraph 1 0 “We demonstrate the separation of the complexity class NP from its subclass P. Throughout our proof, we observe that the ability to compute a property on structures in polynomial time is intimately related to the statistical notions of conditional independence and sufficient statistics. The presence of conditional independencies manifests in the form of economical parametrizations of the joint distribution of covariates. In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.”

2 Leave a comment on paragraph 2 0 Vinay Deolalikar –

3 Leave a comment on paragraph 3 0 No. I have no idea either, and the rest of the document just gets more confusing for a non-mathematician. Nonetheless the online maths community lit up with excitement as this document, claiming to prove one of the major outstanding theorems in maths circulated. And in the process we saw online collaborative post publication peer review take off.

4 Leave a comment on paragraph 4 0 It has become easy to say that review of research after it has been published doesn’t work. Many examples have failed, or been partially successful. Most journals with commenting systems still get relatively few comments on the average paper. Open peer review tests have generally been judged a failure. And so we stick with traditional pre-publication peer review despite the lack of any credible evidence that it does anything except cost around a few billion pounds a year.

5 Leave a comment on paragraph 5 0 Bill Hooker, not exactly a nay-sayer when it comes to using the social web to make research more effective wrote:

6 Leave a comment on paragraph 6 0 “…when you get into “likes” etc, to me that’s post-publication review — in other words, a filter. I love the idea, but a glance at PLoS journals (and other experiments) will show that it hasn’t taken off: people just don’t interact with the research literature (yet?) in a way that makes social filtering effective.”

7 Leave a comment on paragraph 7 0 But actually the picture isn’t so negative. We are starting to see examples of post-publication peer review and see it radically out-perform traditional pre-publication peer review. The rapid demolition [1, 2, 3] of theJACS hydride oxidation paper (not least pointing out that the result wasn’t even novel) demonstrated the chemical blogosphere was more effective than peer review of one of the premiere chemistry journals. More recently 23andMe issued a detailed, and at least from an outside perspective devastating, peer review (with an attempt at replication!) of a widely reported Science paper describing the identification of genes associated with longevity. This followed detailed critiques from a number of online writers.

8 Leave a comment on paragraph 8 0 These, though were of published papers, demonstrating that a post-publication approach can work, but not showing it working for an “informally published” piece of research such as a a blog post or other online posting. In the case of this mathematical proof, the author Vinay Deolalikar, apparently took the standard approach that one does in maths, sent a pre-print to a number of experts in the field for comments and criticisms. The paper was not posted on the ArXiv and was in fact made public by one of the email correspondents. The rumours then spread like wildfire, with widespread media reporting, and widespread online commentary.

9 Leave a comment on paragraph 9 0 Some of that commentary was expert and well informed. Firstly a series of posts appeared stating that the proof is “credible”. That is, that it was worth deeper consideration and the time of experts to look for holes. Then there was a widespread skepticism that the proof could be correct, including a $200,000 bet from Scott Aaronson, although there was also a widespread view that could nonetheless is useful, that it would progress the field in a helpful way even if it is wrong.

10 Leave a comment on paragraph 10 0 After this first round, there were summaries of the proof, and the identification of potential issues is occurring (see RJLipton for a great summary). These issues were subtle and required the attention of domain experts to resolve. In a couple of cases experts potentially “patched” those problems, adding their own expertise to contribute to the proof. And then Michael Nielsen pointed out to me there was the beginning of a more organised collaboration to check through the paper.

11 Leave a comment on paragraph 11 0 This was collaborative, and positive peer review, and happened at web scale. I suspect that there were relatively few experts in the area who weren’t spending some of their time on the problem that week. In the market for expert attention this proof bought big, as it should. An important problem got a good going over and was tested, ultimately to destruction, in a much more efficient manner than could possibly be done by traditional peer review.

12 Leave a comment on paragraph 12 0 There are a number of objections to seeing this as a generalizable to other research problems and fields. Firstly, maths has a strong pre-publication communication and review structure which has been strengthened over the years by the success of the ArXiv. Moreover there is a culture of much higher standards of peer review in maths, review which can take years to complete. Both of these encourage circulation of drafts to a wider community than in most other disciplines, priming the community for distributed review to take place.

13 Leave a comment on paragraph 13 0 The other argument is that only high profile work will get this attention, only high profile work will get reviewed, at this level, possibly at all. Actually I think this is a good thing. Most papers are never cited, so why should they suck up the resource required to review them? Of those that are or aren’t published whether they are useful to someone, somewhere, is not something that can be determined by one or two reviewers. Whether they are useful to you is something that only you can decide. The only person competent to review which papers you should look at in detail is you. Sorry.

14 Leave a comment on paragraph 14 0 Many of us have argued for some time that post-publication peer review with little or no pre-publication review is the way forward. Many have argued against this on practical grounds that we simply can’t get it to happen, there is no motivation for people to review work that has already been published. What I think this proof, and the other stories of online review tell us is that these forms of review will grow of their own accord, particularly around work that is high profile. My hope is that this will start to create an ecosystem where this type of commenting and review is seen as valuable. That would be a more positive route than the other alternative, which seems to be a wholesale breakdown of the current system as the workloads rise too high and the willingness of people to contribute drops.

15 Leave a comment on paragraph 15 0 The argument always brought forward for peer review is that it improves papers. What interests me about the online activity around Deolalikar’s paper was that there was a positive attitude. By finding the problems, the proof could be improved, and new insights found, even if the overall claim was wrong. If we bring a positive attitude to making peer review work more effectively and efficiently then perhaps we can find a good route to improving the system for everyone.

16 Leave a comment on paragraph 16 0 Notes:

17 Leave a comment on paragraph 17 0 This post was originally published as “P ≠ NP and the future of peer review” on Science in the Open on 10 August 2010. Substantial weaknesses were found in the proof in the weeks following this post, and ultimately Deolalikar withdrew the draft. I can’t currently find a copy online and according to Wikipedia the work has not yet been published. I considered updating this post with commentary about more recent cases but opted in the end to just change it to past tense.

Page 43

Source: http://book-shaped-object.cameronneylon.net/wp/discarded/assessment-and-metrics/p-%E2%89%A0-np-and-the-future-of-peer-review/