tag:blogger.com,1999:blog-3722233.post114233438085485603..comments2022-05-17T19:30:53.024-05:00Comments on Computational Complexity: Resolving DagstuhlLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1142378117155907622006-03-14T17:15:00.000-06:002006-03-14T17:15:00.000-06:00anyone else think Guruswami-Rudra should have won ...<I> anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know.</I><BR/><BR/>Certainly this post seems to be intentionally caustic, but I disagree with:<BR/><BR/><I>Whether or not a paper is more deserving of the award is not a useful discussion to have...</I><BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142364034973273132006-03-14T13:20:00.000-06:002006-03-14T13:20:00.000-06:00the PCP theorem had already been proved, you know....<I> the PCP theorem had already been proved, you know.</I><BR/><BR/>Certainly not for this reason. A much simpler proof of a known, important, difficult result can be more valuable than a new insight. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142363410120389582006-03-14T13:10:00.000-06:002006-03-14T13:10:00.000-06:00"anyone else think Guruswami-Rudra should have won..."anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know."<BR/><BR/>Even 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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142361214801041352006-03-14T12:33:00.000-06:002006-03-14T12:33:00.000-06:00My feeling is that most people working on the prob...My 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142358256095787752006-03-14T11:44:00.000-06:002006-03-14T11:44:00.000-06:00You need only mention the probabilistic verificati...You need only mention the probabilistic verification of proofs, and your voice will be taken for that of complexity theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1142353228013613812006-03-14T10:20:00.000-06:002006-03-14T10:20:00.000-06:00anyone else think Guruswami-Rudra should have won ...anyone else think Guruswami-Rudra should have won Best Paper? the PCP theorem had already been proved, you know.Anonymousnoreply@blogger.com