Abstract of Paper

A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
by Petr Savicky, Detlef Sieling

Abstract:

Restricted branching programs are considered in complexity theory in order
to study the space complexity of sequential computations and in applications
as a data structure for Boolean functions. In this paper
$(\oplus,k)$-branching programs and $(\vee,k)$-branching programs are
considered, i.e., branching programs starting with a
$\oplus$- (or $\vee$-)node with a fan-out of k whose successors
are k read-once branching programs. This model is motivated by the
investigation of the power of nondeterminism in branching programs
and of similar variants that have been considered as a data                   
structure.  Lower bound methods for these variants of branching
programs are presented, which allow to prove even hierarchy results
for polynomial size $(\oplus,k)$- and $(\vee,k)$-branching programs
with respect to $k$.