Lower bounds for restricted read-once parity branching programs

摘要

We 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 {direct+}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 Savicky and Sieling (see [P. Savicky, 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.