Lower bounds for restricted read-once parity branching programs

AbstractWe prove the first lower bounds for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Namely, sums of k graph-driven ⊕BP1s with polynomial size graph-orderings are under consideration. We prove lower bounds for the characteristic function of linear codes. We generalize a lower bound by Savický and Sieling (see [P. Savický, D. Sieling, A hierarchy result for read-once Branching programs with restricted parity nondeterminism, Theoret. Comput. Sci. 340 (2005) 594–605]) and recent results on graph-driven parity branching programs