# $RL=L$ Progress Since 2006

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?

• 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 :-) :-) Jul 17, 2014 at 19:37
• 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. Jul 19, 2014 at 16:41

• 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]