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?


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$ – Ryan O'Donnell May 27 '10 at 4:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.