  A central question in derandomization is whether randomized logspace (RL)
equals deterministic logspace (L). To show that RL=L, it suffices to construct
explicit pseudorandom generators (PRGs) that fool polynomial-size read-once
(oblivious) branching programs (roBPs). Starting with the work of Nisan,
pseudorandom generators with seed-length $O(\log^2 n)$ were constructed.
Unfortunately, improving on this seed-length in general has proven challenging
and seems to require new ideas.
  A recent line of inquiry has suggested focusing on a particular limitation of
the existing PRGs, which is that they only fool roBPs when the variables are
read in a particular known order, such as $x_1<\cdots<x_n$. In comparison,
existentially one can obtain logarithmic seed-length for fooling the set of
polynomial-size roBPs that read the variables under any fixed unknown
permutation $x_{\pi(1)}<\cdots<x_{\pi(n)}$. While recent works have established
novel PRGs in this setting for subclasses of roBPs, there were no known
$n^{o(1)}$ seed-length explicit PRGs for general polynomial-size roBPs in this
setting.
  In this work, we follow the "bounded independence plus noise" paradigm of
Haramaty, Lee and Viola, and give an improved analysis in the general roBP
unknown-order setting. With this analysis we obtain an explicit PRG with
seed-length $O(\log^3 n)$ for polynomial-size roBPs reading their bits in an
unknown order. Plugging in a recent Fourier tail bound of Chattopadhyay,
Hatami, Reingold, and Tal, we can obtain a $\widetilde{O}(\log^2 n)$
seed-length when the roBP is of constant width.

Computational Complexity