Time complexity analysis for Reingold's UST-CONN algorithm What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
It seems that the time complexity of Reingold's algorithm is not treated in either the Reingold's paper or in Arora-Barak textbook. It would also appear that the analysis is rather tedious, as the time complexity depends on the exact expander graph used in the construction and on some constants that are chosen to "sufficiently large".

To get some rough idea on the time complexity, observe that Reingold's algorithm, given graph $G$, transforms it (implicitly) into an expander graph $G'$ and traverses every walk of length $l = O(\log n)$. The $O$-notation hides some quite large constants here. The graph $G'$ has constant degree of $d = 2^b$ for some sufficiently large $b$, meaning that there are $d^l = O(n^c)$ such walks for some rather large constant $c$. Skimming some lecture notes on the topic it would seem that $c \ge 10^9b$.