Someone at the workshop pointed out that the STOC 2006 program has been posted and lists the award winners. The best student paper award is going to Anup Rao for Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources and Jakob Nordström for Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. The best paper award is (surprise, surprise) going to Irit Dinur for her PCP Theorem by Gap Amplification.
Nordström gave a talk on his paper Monday. A resolution proof of unsatisfiability of a CNF formula takes a clause containing x and another clause with the negation of x and resolves it into a clause containing the remaining variables of the first two clauses. A CNF formula is unsatisfiable iff there is a resolution proof that leads to the empty clause. In 1985, Haken showed that there are no polynomial-length resolution proofs for all unsatisfiable CNF formula.
The width of a proof is the size of the largest clause produced. The space of the proof is the number of clauses one needs to keep in memory. No immediately obvious reason that the two should be related but in fact the space is an upper bound on the width and conjectured to be the same up to constant factors. Nordström disproves the conjecture by giving a family of formulas where the width is constant but the space is not.
anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know.
ReplyDeleteYou need only mention the probabilistic verification of proofs, and your voice will be taken for that of complexity theory.
ReplyDeleteMy feeling is that most people working on the problem would have conjectured what Nordstrom proved. Only nobody knew how to do it and Nordstrom found an interesting solution.
ReplyDelete"anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know."
ReplyDeleteEven though the above post is essentially flamebaiting, I'll take the bait and respond. Dinur's paper is a monumental contribution to our field, allowing for an elegant, intuitive proof for the PCP theorem, and for this alone is doubtless deserving of the award. If one contends that the test of whether or not a paper should be eligible for the title "best" is if it proves something new, then Dinur's paper passes that test as well, by resolving the open problem of establishing a PCP system with quasilinear proof length and constant number of queries.
Whether or not a paper is more deserving of the award is not a useful discussion to have, and denigrates the tireless work the PC put into organizing this conference. Leave it be.
the PCP theorem had already been proved, you know.
ReplyDeleteCertainly not for this reason. A much simpler proof of a known, important, difficult result can be more valuable than a new insight.
Guruswami-Rudra was certainly a worthy candidate. I personally might have chosen G-R over PCP, but then again I prefer codes over complexity results, so that only goes to show my bias. I think either one was definitely a worthy candidate.
anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know.
ReplyDeleteCertainly this post seems to be intentionally caustic, but I disagree with:
Whether or not a paper is more deserving of the award is not a useful discussion to have...
It's unclear why this is not a useful discussion. It's a potentially harmful discussion, because it could offend and/or hurt the parties involved, but that doesn't have to be the outcome.
I think that--beyond question--Dinur deserves the best paper award. The question that arises for me, then, is whether Guruswami-Rudra also deserve it (I believe the PC is allowed to choose up to 3 papers), and whether giving G-R the award also somehow "equates" the significance of G-R with that of Dinur.
Since it's the "best" paper award, it's clearly a relative merit, and with respect to this, I think the PC made the right decision. The G-R paper loses a little bit in light of Parvaresh-Vardy winning the best paper award at focs.