@conference {654175,
	title = {Pseudorandom walks in regular digraphs and the RL vs. L problem},
	booktitle = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC {\textquoteleft}06)},
	year = {2006},
	pages = {457-466},
	abstract = {
	Version History:\&nbsp;Preliminary version\&nbsp;as\&nbsp;ECCC\&nbsp;TR05-22, February 2005 (https://eccc.weizmann.ac.il/report/2005/022/; attached as ECCC2005.pdf).



	We revisit the general \(\mathbf{RL}\) vs. \(\mathbf{L}\) question, obtaining the following results.



	
		Generalizing Reingold{\textquoteright}s techniques to directed graphs, we present a deterministic, log-space algorithm that given a regular directed graph G (or, more generally, a digraph with Eulerian connected components) and two vertices s and t, finds a path between s and t if one exists.
	
	
		If we restrict ourselves to directed graphs that are regular and consistently labelled, then we are able to produce pseudorandom walks for such graphs in logarithmic space (this result already found an independent application).
	
	
		We prove that if (2) could be generalized to all regular directed graphs (including ones that are not consistently labelled) then \(\mathbf{L=RL}\). We do so by exhibiting a new complete promise problem for \(\mathbf{RL}\), and showing that such a problem can be solved in deterministic logarithmic space given a log-space pseudorandom walk generator for regular directed graphs.
	

},
	url = {https://dl.acm.org/doi/10.1145/1132516.1132583},
	author = {Omer Reingold and Luca Trevisan and Salil Vadhan}
}
