TR21-018 Authors: Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

Publication: 20th February 2021 08:07

Downloads: 120

Keywords:

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