# 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 ?

• Please be more specific. Describe your question in enough detail, and cite the references as appropriate. – M.S. Dousti Sep 7 '10 at 20:07
• I think the question is fairly unambiguous: doi.acm.org/10.1145/1391289.1391291 is the paper. – András Salamon Sep 7 '10 at 23:32
• The question is fairly unambiguous to those who work in the area, but it's probably a good idea to ask posters to give more information so that a wider audience can understand the question. – Robin Kothari Sep 8 '10 at 1:34

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$.