Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-018 | 20th February 2021 07:44

Monotone Branching Programs: Pseudorandomness and Circuit Complexity



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

ISSN 1433-8092 | Imprint