__
TR03-068 | 30th July 2003 00:00
__

#### Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs

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