<p>The central problem is that, on directed graphs, even a <i>truly</i> random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk.  The standard counterexample here is a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex, $t$), and each vertex also has an edge leading all the way back to the leftmost vertex, $s$.  To get from $s$ to $t$ by a random walk then takes ~$2^n$ time.  So, what is the small-space randomized algorithm for directed connectivity that we're hoping to derandomize, analogous to what Reingold did for $USTCON$?  (To put it another way, how do we show $RL=NL$, let alone $L=NL$?)  For directed connectivity, of course there's Savitch's algorithm, but that takes $O(\log^2 n)$ space, and for general graphs no one has managed to improve it for half a century, with or without the use of randomness.</p>

CC BY-SA 3.0
2018-04-27T10:49:50.123Z
For directed connectivity, there is a polynomial-time algorithm using "only" $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ space by Barnes, Buss, Ruzzo and Schieber: _A Sublinear space, Polynomial Time Algorithm for Directed s-t Connectivity_. It's a clever mix of breadth-first search and a recursive Savitch-like algorithm to find the paths between subsequent levels of the BFS. All that is needed now is to go from $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ to $\log n$. So it hasn't improved, not in half a century, but only in the last 20 years :)
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2018-04-10T16:50:55.207Z
2018-04-10T16:50:55.207Z
Scott Aaronson
<p>Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an <strong>U</strong>ndirected graph with special vertices $s$ and $t$, are they <strong>Con</strong>nected?) using only logspace. The basic idea is to build an expander graph from the original graph, and then do the walk in the expander graph. The expander graph is made by squaring the original graph logarithmically many times. In the expander graph, the diameter is only logarithmic, so a DFS search of logarithmic depth suffices.</p>

<p>Extending the result to $L=NL$ would imply the existence of a logspace algorithm for DSTCON -- the same, but for <strong>D</strong>irected graphs. (Sometimes just STCON.) My question, maybe slightly soft, is what are the primary obstructions to extending Reingold's proof to that?</p>

<p>It feels slightly like there should be a sort of "directed expander" graph. A similar sort of construction, where you add in edges corresponding to medium-length directed paths, and then some corresponding to long ones; and then you can traverse the graph with logarithmic depth by moving across short paths to get to a long one; then back to short paths at the end.</p>

<p>Is there a major flaw in this concept? Or is it that there aren't any good constructions of such expanders? Or does it somehow require more memory than the undirected version?</p>

<p>I unfortunately cannot find much at all on directed expander graphs. In fact essentially all I could find was <a href="https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution">https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution</a> (which is unanswered) and <a href="https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&amp;context=cis_papers" rel="noreferrer">https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&amp;context=cis_papers</a> . Is there a different term I should be searching under?</p>

CC BY-SA 3.0
2018-04-10T19:21:32.253Z
This paper gives some insight about extending $L=SL$ to $L=RL$: https://people.seas.harvard.edu/~salil/research/regular-abs.html
sdcvvc
CC BY-SA 3.0
2018-04-10T20:01:30.293Z
See [point 3. here](https://cs.stackexchange.com/questions/79528/a-language-in-nspaceon-and-very-likely-not-in-dspaceon/79615#79615). You may object that it is complete speculation, but notice that Scott's answer basically makes the same point about random exploration of directed graphs.
Thomas Klimpel
<graph-algorithms><nondeterminism><expanders><logspace>
What are the obstructions to extending $L=SL$ to $L=NL$?
Alex Meiburg
# What are the obstructions to extending $L=SL$ to $L=NL$?

(Asked by: username_0 on 2018-04-08)

Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an **U**ndirected graph with special vertices $s$ and $t$, are they **Con**nected?) using only logspace. The basic idea is to build an expander graph from the original graph, and then do the walk in the expander graph. The expander graph is made by squaring the original graph logarithmically many times. In the expander graph, the diameter is only logarithmic, so a DFS search of logarithmic depth suffices.

Extending the result to $L=NL$ would imply the existence of a logspace algorithm for DSTCON -- the same, but for **D**irected graphs. (Sometimes just STCON.) My question, maybe slightly soft, is what are the primary obstructions to extending Reingold's proof to that?

It feels slightly like there should be a sort of "directed expander" graph. A similar sort of construction, where you add in edges corresponding to medium-length directed paths, and then some corresponding to long ones; and then you can traverse the graph with logarithmic depth by moving across short paths to get to a long one; then back to short paths at the end.

Is there a major flaw in this concept? Or is it that there aren't any good constructions of such expanders? Or does it somehow require more memory than the undirected version?

I unfortunately cannot find much at all on directed expander graphs. In fact essentially all I could find was <https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution> (which is unanswered) and <https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers> . Is there a different term I should be searching under?

**Tags:** graph-algorithms, nondeterminism, expanders, logspace
> **Comments:**
> **username_1**: This paper gives some insight about extending $L=SL$ to $L=RL$: https://people.seas.harvard.edu/~salil/research/regular-abs.html  
> **username_2**: See [point 3. here](https://cs.stackexchange.com/questions/79528/a-language-in-nspaceon-and-very-likely-not-in-dspaceon/79615#79615). You may object that it is complete speculation, but notice that Scott's answer basically makes the same point about random exploration of directed graphs.  

---

## 1 answers

### Answer by username_3 on 2018-04-10. Score: 19 | Accepted answer

The central problem is that, on directed graphs, even a *truly* random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex, $t$), and each vertex also has an edge leading all the way back to the leftmost vertex, $s$. To get from $s$ to $t$ by a random walk then takes ~$2^n$ time. So, what is the small-space randomized algorithm for directed connectivity that we're hoping to derandomize, analogous to what Reingold did for $USTCON$? (To put it another way, how do we show $RL=NL$, let alone $L=NL$?) For directed connectivity, of course there's Savitch's algorithm, but that takes $O(\log^2 n)$ space, and for general graphs no one has managed to improve it for half a century, with or without the use of randomness.

> **Comments:**
> **username_4**: For directed connectivity, there is a polynomial-time algorithm using "only" $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ space by Barnes, Buss, Ruzzo and Schieber: _A Sublinear space, Polynomial Time Algorithm for Directed s-t Connectivity_. It's a clever mix of breadth-first search and a recursive Savitch-like algorithm to find the paths between subsequent levels of the BFS. All that is needed now is to go from $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ to $\log n$. So it hasn't improved, not in half a century, but only in the last 20 years :)  

---

