I heard that there is a result which is proved that RL\subseteq L^{4/3}, but I don't which paper have proved it.
Can someone tell me this paper?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I think that the currently best known bound is L^{3/2} in Michael E. Saks, Shiyu Zhou: RSPACE(S) \subseteq DSPACE(S3/2). FOCS 1995 344-353
There was a paper showing Symmetric Log space in L^{4/3}
R. Armoni, A. Ta-Shma, A. Wigderson, S. Zhou. A (log n )^{4/3} space algorithm for (s,t) connectivity in undirected graphs Preliminary version in Proceedings of the 29th STOC, pp. 230-239, 1997. J. ACM, vol. 47, no. 2, 294-311, 2000.
(by now it is known that symmetric log spaces is in log space)
-
$\begingroup$ (And the result that symmetric log spaces is in log space is due to O. Reingold, "Undirected connectivity in log-space", JACM 55(4), 2008.) $\endgroup$ Commented May 27, 2010 at 4:20