tag:blogger.com,1999:blog-3722233.post110202409418102718..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: Bad TimingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1102097542681281032004-12-03T12:12:00.000-06:002004-12-03T12:12:00.000-06:00Dude, chill out Eric. I doubt that Lance is trying...Dude, chill out Eric. I doubt that Lance is trying to shoot down Trifonov. In fact Lance seems symathetic to the fact that an otherwise important result is now destined to become a footnote.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1102089030073870992004-12-03T09:50:00.000-06:002004-12-03T09:50:00.000-06:00If it came out a few months earlier (assuming the ...<EM>If it came out a few months earlier (assuming the proof is correct) it would have been an amazing result, greatly improving the previously best known O(log4/3 n) bound. <br /></EM>It still is an amazing result, it still greatly improves the previously best known bound.<br /><br /><EM>Unfortunately for Trifonov, Omer Reingold announced his result giving the stronger O(log n) space algorithm a few weeks earlier. Trifonov's work was done independently from Reingold.<br /></EM>I find the first sentence quite judgmental, and the second one awfully condescending. You seem to be pre-supposing that Reingold gains precedence here -- keep in mind that both ECCC TRs came out a few weeks after the STOC/CCC submission deadlines, and there is a fair chance that both papers have been submitted to one of these conferences, and might end up in the same proceedings. In which case, they will have identical publication dates.<br /><br />Not to take anything away from Reingold's brilliant work, but Trifonov's paper points out (a) that the problem was not as hard as made out to be, and (b) derandomizing the random walk algorithm via pseudorandom generators, etc., is not the only way to think about it. Furthermore, a cursory glance at Trifonov's paper says that it solves a specific conjecture of Ramachandran -- i.e., she had specifically laid out a path for obtaining a low-space algorithm for USTCON. I've never been a big fan of the PRAM stuff, but it appears that there's an element of vindication here for that community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1102033246529603192004-12-02T18:20:00.000-06:002004-12-02T18:20:00.000-06:00Because eventually log(log(n)) will become an insu...Because eventually log(log(n)) will become an insurmountably huge multiplier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1102032400020959442004-12-02T18:06:00.000-06:002004-12-02T18:06:00.000-06:00Still an admirable breakthrough. Bravo! :)Still an admirable breakthrough. Bravo! :)Anonymousnoreply@blogger.com