We construct improved pseudorandom generators for read-$k$ oblivious branching programs with a known reading sequence.
For width-$w$ branching programs over $n$ variables, and designated error $\varepsilon$, our generator has seed length
$$\mathcal{O}\left(n^{1-\frac{1}{2k-1}}\log n\left(k\log w+\log\frac{n}{\varepsilon}\right)\right).$$
This improves upon the previous state-of-the-art due to Gurjar and Volk (ACM ToCT 2020), that has $1-\frac{1}{2^{k-1}}$ as the exponent of $n$ (and a multiplicative factor of $\exp(k^2)$), whenever $k \ge 4$. In particular, whenever $w$ and $1/\varepsilon$ are not too large, our seed length remains sublinear whenever $k=o(\log n/\log\log n)$, whereas the Gurjar and Volk's bound is sublinear only when
$k=\mathcal{O}(\log\log n)$.

Our main conceptual contribution is a new way of modeling branching programs within the communication network of the classical INW generator of Impagliazzo, Nisan, and Wigderson (STOC 1994). Whereas nearly all applications of the INW generator model communication over a branching program using a simple path graph, we instead design a binary-tree communication network whose leaves correspond to the input variables, that allows substantially more efficient routing between variables that may be read multiple times. Toward this end, we identify a structural condition on the reading sequence under which routing the branching program’s state through this network requires only $\mathcal{O}(k\log w)$ bits of communication per processor.