<ul>
<li>One line of work has shown how to <em>improve the analysis of the classic <a href="https://doi.org/10.1145/195058.195190" rel="noreferrer">INW PRG</a></em> for the special cases of fooling regular and permutation branching programs. The seed length is only <span class="math-container">$\widetilde{O}(\log n)$</span> or <span class="math-container">$O(\log n)$</span> in some cases. <a href="https://doi.org/10.1007/978-3-642-03685-9_46" rel="noreferrer">[LRTV09]</a> <a href="https://www.cs.swarthmore.edu/%7Ebrody/papers/CoinProblemFullVersion.pdf" rel="noreferrer">[BV10]</a> <a href="https://doi.org/10.1109/CCC.2011.23" rel="noreferrer">[De11]</a> <a href="https://doi.org/10.1145/1993636.1993672" rel="noreferrer">[KNP11]</a> <a href="https://eccc.weizmann.ac.il/report/2012/083/" rel="noreferrer">[Ste12]</a> <a href="https://doi.org/10.1137/120875673" rel="noreferrer">[BRRY14]</a> <a href="https://doi.org/10.4230/LIPIcs.ITCS.2021.7" rel="noreferrer">[HPV21]</a></li>
<li>Another line of work has developed a PRG framework based on <em>iterated pseudorandom restrictions.</em> This framework has been used to fool various classes of functions that can be computed by &quot;arbitrary-order&quot; read-once branching programs. Again, in some cases the seed length is <span class="math-container">$\widetilde{O}(\log n)$</span> or even <span class="math-container">$O(\log n)$</span>. <a href="https://doi.org/10.1109/FOCS.2012.77" rel="noreferrer">[GMRTV12]</a> <a href="https://doi.org/10.1109/CCC.2012.37" rel="noreferrer">[GLS12]</a> <a href="https://doi.org/10.1007/978-3-642-40328-6_45" rel="noreferrer">[RSV13]</a> <a href="https://arxiv.org/abs/1504.04675" rel="noreferrer">[CSV15]</a> <a href="https://doi.org/10.4086/toc.2017.v013a012" rel="noreferrer">[SVW17]</a> <a href="https://doi.org/10.1145/3188745.3188800" rel="noreferrer">[CHRT18]</a> <a href="https://doi.org/10.1137/17M1129088" rel="noreferrer">[HLV18]</a> <a href="https://doi.org/10.1109/FOCS.2018.00093" rel="noreferrer">[FK18]</a> <a href="https://doi.org/10.1145/3313276.3316319" rel="noreferrer">[MRT19]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2019.16" rel="noreferrer">[DHH19]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2019.7" rel="noreferrer">[Lee19]</a> <a href="http://doi.org/10.4086/toc.2020.v016a007" rel="noreferrer">[LV20]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2020.6" rel="noreferrer">[DHH20]</a> <a href="https://eccc.weizmann.ac.il/report/2021/018/" rel="noreferrer">[DMRTV21]</a></li>
<li>The paper referenced in the original question is part of a line of work that <em>uses spectral techniques to design graph algorithms</em> for space-bounded derandomization. That line of work, which most famously includes <a href="https://dl.acm.org/doi/10.1145/1391289.1391291" rel="noreferrer">Reingold's algorithm for undirected connectivity</a>, has continued. Recently the focus has been on simulating random walks of length much less than the mixing time of the graph. <a href="https://doi.org/10.1145/1978782.1978785" rel="noreferrer">[CRV11]</a> <a href="https://doi.org/10.1109/FOCS.2017.79" rel="noreferrer">[MRSV17]</a> <a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.42" rel="noreferrer">[MRSV19]</a> <a href="https://doi.org/10.1109/FOCS46700.2020.00123" rel="noreferrer">[AKMPSV20]</a></li>
<li>Finally, there is a line of work designing improved <em>low-error generalized PRGs</em> for polynomial-width read-once branching programs. By &quot;generalized PRGs,&quot; I am referring to (a) hitting set generators and (b) weighted pseudorandom generators, aka pseudorandom pseudodistribution generators. <a href="https://doi.org/10.1137/18M1197734" rel="noreferrer">[BCG20]</a> <a href="https://doi.org/10.1137/19M1268707" rel="noreferrer">[HZ20]</a> <a href="https://doi.org/10.4230/LIPIcs.CCC.2020.25" rel="noreferrer">[CL20]</a> <a href="https://eccc.weizmann.ac.il/report/2021/020/" rel="noreferrer">[CDRSTS21]</a> <a href="https://eccc.weizmann.ac.il/report/2021/019/" rel="noreferrer">[PV21]</a> <a href="https://eccc.weizmann.ac.il/report/2021/048/" rel="noreferrer">[Hoz21]</a></li>
</ul>
<p>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.</p>
<p>See also: Reingold's two-part presentation <a href="http://dimacs.rutgers.edu/events/details?eID=1192" rel="noreferrer">&quot;Recent Developments Related to RL vs. L&quot;</a> at the DIMACS Day of Complexity Tutorials prior to CCC 2019, and the STOC 2020 workshop <a href="https://sites.google.com/site/avishaytal/derandomizing-space-bounded-computation" rel="noreferrer">&quot;Derandomizing Space-Bounded Computation&quot;</a> organized by Meka, Tal, and Zuckerman.</p>

CC BY-SA 4.0
2021-04-27T19:11:50.213Z
2021-04-27T19:11:50.213Z
William Hoza
<p>Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (<a href="http://dl.acm.org/citation.cfm?id=1132583">http://dl.acm.org/citation.cfm?id=1132583</a>) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.</p>

<p>Has any further progress on this problem been made since then?</p>

CC BY-SA 3.0
2014-07-17T19:37:50.110Z
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.](http://dl.acm.org/citation.cfm?id=1978785&CFID=390405357&CFTOKEN=46059609). 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 :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2014-07-19T16:41:08.323Z
There has been a fair amount of work on constant-space derandomization. Some examples:
[BRRY10](http://eccc.hpi-web.de/report/2010/035/),
[BV10](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.173.1241),
[KNP11](http://eccc.hpi-web.de/report/2010/113/),
[De11](http://www.math.ias.edu/~anindya/full-reg.pdf),
[RSV13](http://arxiv.org/abs/1306.3004).
I, for one, like to believe that this represents some sort of progress towards RL=L.
Thomas Steinke
<cc.complexity-theory><reference-request><pseudorandomness>
$RL=L$ Progress Since 2006
ruadath
# $RL=L$ Progress Since 2006

(Asked by: username_0 on 2014-07-17)

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?

**Tags:** cc.complexity-theory, reference-request, pseudorandomness

> **Comments:**
> **username_1**: 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.](http://dl.acm.org/citation.cfm?id=1978785&CFID=390405357&CFTOKEN=46059609). 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 :-) :-)  
> **username_2**: There has been a fair amount of work on constant-space derandomization. Some examples: [BRRY10](http://eccc.hpi-web.de/report/2010/035/), [BV10](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.173.1241), [KNP11](http://eccc.hpi-web.de/report/2010/113/), [De11](http://www.math.ias.edu/~anindya/full-reg.pdf), [RSV13](http://arxiv.org/abs/1306.3004). I, for one, like to believe that this represents some sort of progress towards RL=L.  

---

## 1 answers

### Answer by username_3 on 2021-04-27. Score: 11

* One line of work has shown how to *improve the analysis of the classic [INW PRG](https://doi.org/10.1145/195058.195190)* 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]](https://doi.org/10.1007/978-3-642-03685-9_46) [[BV10]](https://www.cs.swarthmore.edu/%7Ebrody/papers/CoinProblemFullVersion.pdf) [[De11]](https://doi.org/10.1109/CCC.2011.23) [[KNP11]](https://doi.org/10.1145/1993636.1993672) [[Ste12]](https://eccc.weizmann.ac.il/report/2012/083/) [[BRRY14]](https://doi.org/10.1137/120875673) [[HPV21]](https://doi.org/10.4230/LIPIcs.ITCS.2021.7)
* 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]](https://doi.org/10.1109/FOCS.2012.77) [[GLS12]](https://doi.org/10.1109/CCC.2012.37) [[RSV13]](https://doi.org/10.1007/978-3-642-40328-6_45) [[CSV15]](https://arxiv.org/abs/1504.04675) [[SVW17]](https://doi.org/10.4086/toc.2017.v013a012) [[CHRT18]](https://doi.org/10.1145/3188745.3188800) [[HLV18]](https://doi.org/10.1137/17M1129088) [[FK18]](https://doi.org/10.1109/FOCS.2018.00093) [[MRT19]](https://doi.org/10.1145/3313276.3316319) [[DHH19]](https://doi.org/10.4230/LIPIcs.CCC.2019.16) [[Lee19]](https://doi.org/10.4230/LIPIcs.CCC.2019.7) [[LV20]](http://doi.org/10.4086/toc.2020.v016a007) [[DHH20]](https://doi.org/10.4230/LIPIcs.CCC.2020.6) [[DMRTV21]](https://eccc.weizmann.ac.il/report/2021/018/)
* 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](https://dl.acm.org/doi/10.1145/1391289.1391291), has continued. Recently the focus has been on simulating random walks of length much less than the mixing time of the graph. [[CRV11]](https://doi.org/10.1145/1978782.1978785) [[MRSV17]](https://doi.org/10.1109/FOCS.2017.79) [[MRSV19]](https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.42) [[AKMPSV20]](https://doi.org/10.1109/FOCS46700.2020.00123)
* 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]](https://doi.org/10.1137/18M1197734) [[HZ20]](https://doi.org/10.1137/19M1268707) [[CL20]](https://doi.org/10.4230/LIPIcs.CCC.2020.25) [[CDRSTS21]](https://eccc.weizmann.ac.il/report/2021/020/) [[PV21]](https://eccc.weizmann.ac.il/report/2021/019/) [[Hoz21]](https://eccc.weizmann.ac.il/report/2021/048/)

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"](http://dimacs.rutgers.edu/events/details?eID=1192) at the DIMACS Day of Complexity Tutorials prior to CCC 2019, and the STOC 2020 workshop ["Derandomizing Space-Bounded Computation"](https://sites.google.com/site/avishaytal/derandomizing-space-bounded-computation) organized by Meka, Tal, and Zuckerman.


---

