11
$\begingroup$

What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?

$\endgroup$
  • 6
    $\begingroup$ Please be more specific. Describe your question in enough detail, and cite the references as appropriate. $\endgroup$ – M.S. Dousti Sep 7 '10 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 Salamon Sep 7 '10 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 Kothari Sep 8 '10 at 1:34
23
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ next time, don't mark your answer as community wiki. Otherwise you won't get credit for your answer! $\endgroup$ – Ryan Williams Sep 8 '10 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$ – Janne H. Korhonen Sep 8 '10 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy