Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.

Has any further progress on this problem been made since then?

  • 5
    $\begingroup$ Another step towards closing the gap between s-t connectivity in regular digraphs with arbitrary labelling (L) and poly-mixing s-t connectivity (RL-complete) has been done by Kai-Min Chung, Omer Reingold, and Salil Vadhan. 2011. S-T connectivity on digraphs with a known stationary distribution.. They introduce an intermediate problem in L called "known-stationary s-t connectivity", but - to be honest - I (absolutely) don't understand much of that nice stuff :-) :-) $\endgroup$ Commented Jul 17, 2014 at 19:37
  • 2
    $\begingroup$ There has been a fair amount of work on constant-space derandomization. Some examples: BRRY10, BV10, KNP11, De11, RSV13. I, for one, like to believe that this represents some sort of progress towards RL=L. $\endgroup$
    – Thomas
    Commented Jul 19, 2014 at 16:41

1 Answer 1

  • One line of work has shown how to improve the analysis of the classic INW PRG for the special cases of fooling regular and permutation branching programs. The seed length is only $\widetilde{O}(\log n)$ or $O(\log n)$ in some cases. [LRTV09] [BV10] [De11] [KNP11] [Ste12] [BRRY14] [HPV21]
  • Another line of work has developed a PRG framework based on iterated pseudorandom restrictions. This framework has been used to fool various classes of functions that can be computed by "arbitrary-order" read-once branching programs. Again, in some cases the seed length is $\widetilde{O}(\log n)$ or even $O(\log n)$. [GMRTV12] [GLS12] [RSV13] [CSV15] [SVW17] [CHRT18] [HLV18] [FK18] [MRT19] [DHH19] [Lee19] [LV20] [DHH20] [DMRTV21]
  • The paper referenced in the original question is part of a line of work that uses spectral techniques to design graph algorithms for space-bounded derandomization. That line of work, which most famously includes Reingold's algorithm for undirected connectivity, has continued. Recently the focus has been on simulating random walks of length much less than the mixing time of the graph. [CRV11] [MRSV17] [MRSV19] [AKMPSV20]
  • Finally, there is a line of work designing improved low-error generalized PRGs for polynomial-width read-once branching programs. By "generalized PRGs," I am referring to (a) hitting set generators and (b) weighted pseudorandom generators, aka pseudorandom pseudodistribution generators. [BCG20] [HZ20] [CL20] [CDRSTS21] [PV21] [Hoz21]

Please forgive me for inevitably omitting many excellent papers from this summary, including lots of work that doesn't fit neatly into the four themes above.

See also: Reingold's two-part presentation "Recent Developments Related to RL vs. L" at the DIMACS Day of Complexity Tutorials prior to CCC 2019, and the STOC 2020 workshop "Derandomizing Space-Bounded Computation" organized by Meka, Tal, and Zuckerman.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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