Trifonov's proof uses techniques based on PRAM algorithms for connectivity completely different from Reingold's zig-zag methods.
Thursday, December 02, 2004
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.