What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
$\begingroup$
3$\endgroup$
- 6$\begingroup$Please be more specific. Describe your question in enough detail, and cite the references as appropriate.$\endgroup$– Sadeq DoustiCommentedSep 7, 2010 at 20:07
- 8$\begingroup$I think the question is fairly unambiguous: doi.acm.org/10.1145/1391289.1391291 is the paper.$\endgroup$– András SalamonCommentedSep 7, 2010 at 23:32
- 10$\begingroup$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.$\endgroup$– Robin KothariCommentedSep 8, 2010 at 1:34
Add a comment |
1 Answer
$\begingroup$$\endgroup$
2It 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$.
- 2$\begingroup$next time, don't mark your answer as community wiki. Otherwise you won't get credit for your answer!$\endgroup$CommentedSep 8, 2010 at 20:17
- $\begingroup$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.$\endgroup$CommentedSep 8, 2010 at 20:29
