Abstract:
We prove the first lower bound for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Proving a superpolynomial lower bound for read-once parity branching programs is still a challenging open problem. The following variant of read--once parity branching programs is well-motivated. Let k be a fixed integer. For each input a there are k orderings s_1(a),...,s_k(a) of the variables such that for each computation path activated by a the bits are queried according to s_i(a) for some i, 1<=i<=k. This model strictly generalizes all restricted variants of read-once parity branching programs for that lower bounds are known. We consider a slightly more restricted version, i.e. the sum of k graph-driven parity BPs with polynomial size graph-orderings. We prove lower bounds for linear codes and show that the considered variant strictly generalizes well--structured graph-driven parity BP1s as well as (parity, k)-BPs examined by Savicky and Sieling in 1999.