Abstract of Paper

Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs
by Henrik Brosenne, Matthias Homeister and Stephan Waack

Abstract:

We prove the first exponential lower bounds on the size of graph-driven
read-once parity branching programs. The functions used are linear
codes, permutation matrices and a function that has small unrestricted
read-once parity branching programs.

How to interpret this lower bounds?

It is supposed that certain linear code functions do not have 
polynomially bounded  unrestricted parity read-once branching programs.
Our lower bound for linear codes supports this supposition.

Read-once projections are projections of multiplicity one for each
variable. They are an appropriate reduction notion for all branching
program classes C subject to the read-once condition, since they preserve
polynomial size. It is known that an exponential lower bound for
permutation matrices on the size of read-once branching programs belonging
to C proves that projections with multiplicity two may lead to an
exponential blow-up of the C-size. Such a lower bound is known on the size
of OBDDs and OR-OBDDs. We prove it for graph-driven read-once parity
branching programs.

Moreover, we characterize all read-once branching programs that are
guided by graph orderings. The latter is the case if and only if for each
input there is a variable ordering that is compatible with each
computation path for the input. This shows that the condition of being
guided by a graph ordering is in fact a very natural combinatorial one.