ECCC-Report TR03-068https://eccc.weizmann.ac.il/report/2003/068Comments and Revisions published for TR03-068en-usTue, 09 Sep 2003 13:02:00 +0300
Paper TR03-068
| Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs |
Matthias Homeister
https://eccc.weizmann.ac.il/report/2003/068We 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.
Tue, 09 Sep 2003 13:02:00 +0300https://eccc.weizmann.ac.il/report/2003/068