Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-068 | 30th July 2003 00:00

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


Authors: Matthias Homeister
Publication: 9th September 2003 13:02
Downloads: 1321


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.

ISSN 1433-8092 | Imprint