Look, I do complexity theory myself. There’s no contradiction between acknowledging that most of it has very little relevance to anything practical and wanting to work in that field. Personally I just find it fascinating, and I suspect Karp does too.

You’re pretty dumb (I normally don’t insult people outright, but you started this) if you think algorithm design automatically qualifies as complexity theory. In that sense, *all* CS is complexity theory. Karp’s string matching algorithm is hardly any more complexity theory than an algorithm for optimizing SQL statements or one for doing facial recognitions of middle aged men is.

*The same Karp who has spent the last ten years or so publishing algorithmic results in bioinformatics conferences.*

I guess you missed the “bioinformatics” part. Bioinformatics algorithms are indeed useful. Oracle QC proofs, normally not so much.

]]>Definitely not. Sometimes the conclusion will look exciting, but the proof will have nothing going on — e.g., just applying a standard result from a different field. Other times the conclusion will look laughably arcane, but to prove it the authors have to introduce an amazing technique that might later revolutionize the field.

]]>*Don’t tell me you were gullible enough to believe that…*

You’re gullible if you think that Karp meant this as an insult to complexity theory.

The “distaste” for complexity theory in TCS is–much like the “distaste” for gay rights in some parts of this country–a symptom of people who don’t come much into contact with complexity theorists (resp, gay people). You will not see such ridiculousness in any of the top 10 CS departments in the US.

]]>Of course he was. The fact that Karp has done work in both complexity theory and algorithms doesn’t mean they’re the same thing.

]]>Don’t tell me you were gullible enough to believe that, coming from the author of the Karp-Rabin string matching algorithm and the Hopcroft-Karp bipartite algorithm, both of which are **extensively** used in practice. The same Karp who has spent the last ten years or so publishing algorithmic results in bioinformatics conferences. You didn’t think he was serious, did you?

And unless quantum computing can deliver something practical within the next five to ten years it will be as popular then as, say, PRAMs are today.

]]>*– real-life relevance: how useful is the result outside theory*

I actually laughed out loud at reading this. You do know that this is the blog of someone who writes papers about quantum computing and oracles, right?

I think it was Karp who summed up complexity theory with “if pigs can fly, then elephants can dance”. That pretty much describes how much relevance most of it has to, well, *anything*.

As for the topic of this blog post, I think it remains to be seen where this goes. There are certainly a lot of problems that can arise. However, I applaud Nature (of all journals!) for actually trying something new.

]]>Your system does exist in the following sense.

The first stage is when the author solicits comments by expositing on his proof techniques, e.g. talks, seminars, circulation of drafts for feedback, etc. The second stage is then the actual review of the paper, itself having been modified with the aid of said feedback.

A description of “the kind of conclusion-assumption relationship that [a proof technique] was capable of delivering”, without the actual availability of the proof itself, is normally referred to as a “conjecture”, a “sketch” of a purported proof, or, on a grander scale, a “program”. Papers can be written on this basis, but then the interest in these papers is then on whether and how the problems posed can be solved, and that would be the subsequent topic of future papers.

Scott’s example from prime number theory is the work of Green-Tao, who answered the question in the affirmative. Another example is Andrew Wiles’ proof, which may perhaps give a better illustration.

You may recall that Wiles announced his proof in a series of lectures in Cambridge. This would correspond to your “first stage”, and after the lectures, it was reported that the audience was apparently convinced that Wiles had laid FLT to rest. Granted, Wiles’ lectures were detailed, but even talks and humans can only go so far, in terms of details and stamina respectively.

It was only in the actual review stage, your “second stage”, that the reviewers found a huge flaw in Wiles’ work, which took many months to fix (even with a collaborator, Richard Taylor, on board), and which the audience of Wiles’ talks apparently were not able to spot.

This illustrates how subtle errors can still creep in, despite the proof “technique” looking legitimate at the gross level. In fact, apparently a “wrong” technique was used, but somehow this wasn’t spotted at the “first stage”, and illustrates how a technique can seem interesting or plausible even when it turns out to be used inappropriately.

In short, at least in mathematically-oriented papers, the focus of the very review of the paper itself is in the “second stage”: spotting the subtle errors in the proof techniques used. Certainly, gross errors will be picked out as well, if there are any, but careful authors would have worked hard to avoid them. Formalizing the “first stage” would then make less sense given this situation.

]]>In other words, we can end up with a situtation when only people with vested interests (or an axe to grind) will post, while more impartial readers may decide not to post anything.

It may also polarize the review process. You can see it on blogs and internet discussion forums – controversial topics get a lot more comments, and some people leave a lot more comments, while others may be more introverted – they may agree or disagree with the post or a paper, but keep their ideas to themselves.

So overall I am not terribly optimistic about blogging approach to peer-review. I think it opens a number of possibilities for unfair “ganging up” on a certain paper from certain groups of competitors, for example, or the other way around – authors may request their friends and colleagues to post positive reviews in attempt to influence decision of reviewer.

There are also a lot of advantages offered by anonimity of referee process, and while Nature is correct in making posters reveal their names (would those be checked, by the way?), it may prevent certain people from saying negative things or blogging altogether, at the same time encouraging more participation from people who don’t particularly care about their reputation – unaffiliated “crackpots” for example, unqualified laymen who like the sound of their own voice etc.

Let’s put it this way – let’s say you are giving a talk and there are 100 people in the audience. Let’s say the talk represents excellent science, and if you poll people afterwards, 90 out of 100 will say that this is good talk. However, there’s always a person or two who like to ask assinine questions and undermine the presenter’s credibility. Some like the sound of their voice and for some reason think that disbelieving everything somehow makes them a better scientist. I know at least couple of people like that.

A disproportionate amount of questions are asked by people like that, while more reasonable scientists may not ask anything at all. Blogging approach seems to weigh towards the “question asking people” – which could be just a few people in the audience, while neglecting to inquire what the rest 98 people in the audience think of your research.

]]>