Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-131 | 27th July 2026 20:57

From Nondeterministic to Modular Branching Programs, Uniformly and in Logspace

RSS-Feed




TR26-131
Authors: Benny Applebaum
Publication: 2nd August 2026 09:34
Downloads: 32
Keywords: 


Abstract:

A branching program is a labeled directed graph that, on each input $x$, induces an $s$-$t$ connectivity instance. Nondeterministic branching programs (NBPs) accept an input if there exists an accepting path, whereas parity branching programs ($\oplus$BPs) accept if the number of accepting paths is odd. Wigderson (Structure in Complexity Theory Conference, 1994) showed that NBPs can be simulated by $\oplus$BPs with the aid of nonuniform advice, establishing
\[
NL/poly\subseteq\oplus L/poly.
\]

In this short note, we observe that the recent breakthrough of Chatterjee, Ghosh, Gurjar, Raj, and Thierauf, placing bipartite perfect matching in deterministic NC, yields a uniform version of Wigderson's theorem. Specifically, we show that every nondeterministic branching program can be transformed, in deterministic logspace, into an equivalent polynomial-size parity branching program. More generally, for every fixed prime $p$, every nondeterministic branching program admits a logspace-uniform simulation by a polynomial-size mod-$p$ branching program. In complexity-theoretic terms, this establishes
$NL\subseteq\oplus L$ and, more generally, $NL\subseteq \text{Mod}pL$ for every fixed prime $p$.



ISSN 1433-8092 | Imprint