Lower bounds for general graph-driven read-once parity branching programs

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. Moreover, we characterize all BP1s 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.