What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
Asked
Active
Viewed 726 times
11
-
6Please be more specific. Describe your question in enough detail, and cite the references as appropriate. – Sadeq Dousti Sep 07 '10 at 20:07
-
8I think the question is fairly unambiguous: http://doi.acm.org/10.1145/1391289.1391291 is the paper. – András Salamon Sep 07 '10 at 23:32
-
10The 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 08 '10 at 01:34
1 Answers
23
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$.
Janne H. Korhonen
- 1,474
- 11
- 14
-
2next time, don't mark your answer as community wiki. Otherwise you won't get credit for your answer! – Ryan Williams Sep 08 '10 at 20:17
-
I was thinking that someone might want to refine my analysis, and didn't realise that you don't get reputation from community wikis. Oh well. – Janne H. Korhonen Sep 08 '10 at 20:29