|Abstract of Paper|
Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs
by Henrik Brosenne, Matthias Homeister and Stephan Waack
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.