Trifonov's proof uses techniques based on PRAM algorithms for connectivity completely different from Reingold's zig-zag methods.
Thursday, December 02, 2004
Bad Timing
Texas student Vladimir Trifonov gives An
O(log n log log n) Space Algorithm for Undirected Connectivity. 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. 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.
Subscribe to:
Post Comments (Atom)
Still an admirable breakthrough. Bravo! :)
ReplyDeleteBecause eventually log(log(n)) will become an insurmountably huge multiplier.
ReplyDeleteIf 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.
ReplyDeleteIt still is an amazing result, it still greatly improves the previously best known bound.
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.
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.
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.
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.
ReplyDelete