Motivated by the derandomization of space-bounded computation, there has been a long line of work on constructing pseudorandom generators (PRGs) against various forms of read-once branching programs (ROBPs), with a goal of improving the $O(\log^{2}n)$ seed length of Nisan’s classic construction [Nis92] to the optimal $O(\log n)$.
In this work, we construct an explicit PRG with seed length $O(\log n)$ for constant-width ROBPs that are monotone, meaning that the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. This result is complementary to a line of work that gave PRGs with seed length $O(\log n)$ for (ordered) permutation ROBPs of constant width [BRRY14, KNP11, De11, Ste12], since the monotonicity constraint can be seen as the “opposite” of the permutation constraint.
Our PRG also works for monotone ROBPs that can read the input bits in any order, which are strictly more powerful than read-once $AC^{0}$ . Our PRG achieves better parameters (in terms of the dependence on the depth of the circuit) than the best previous pseudorandom generator for read-once $AC^{0}$, due to Doron, Hatami, and Hoza [DHH19].
Our pseudorandom generator construction follows Ajtai and Wigderson’s approach of iterated pseudorandom restrictions [AW89, GMR+12]. We give a randomness- efficient width-reduction process which proves that the branching program simplifies to an $O(\log n)$-junta after only $O(\log \log n)$ independent applications of the Forbes–Kelley pseudorandom restrictions [FK18].
The equivalence between AC0 and constant-width MBPs can be deduced from previous works of Barrington, Lu, Miltersen, and Skyum. This revision reflects that.
We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.
We prove that constant-width monotone branching programs of polynomial size are equivalent in power to $AC^{0}$ circuits. This complements the celebrated theorem of Barrington, which states that constant-width branching programs, without the monotonicity constraint, are equivalent in power to $NC^{1}$ circuits.
Next we turn to read-once monotone branching programs of constant width, which we note are strictly more powerful than read-once $AC^0$. Our main result is an explicit pseudorandom generator that $\varepsilon$-fools length $n$ programs with seed length $\widetilde{O}(\log(n/\varepsilon))$. This extends the families of constant-width read-once branching programs for which we have an explicit pseudorandom generator with near-logarithmic seed length.
Our pseudorandom generator construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions [AW89,GMRTV12]. We give a randomness-efficient width-reduction process which allows us to simplify the branching program after only $O(\log\log n)$ independent applications of the Forbes--Kelley pseudorandom restrictions [FK18].
