Treffer: A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications.

We present a new lower bound technique for a restricted Branching Program model, namely for nondeterministic graph-driven read-once Branching Programs (g.d.-BP1s). The technique is derived by drawing a connection between ω-nondeterministic g.d.-BP1s and ω-nondeterministic communication complexity (for the nondeterministic acceptance modes $$ \omega \in \{ \vee , \wedge , \oplus \} ) $$ We apply the technique in order to prove an exponential lower bound for integer multiplication for ω-nondeterministic well-structured g.d.-BP1s. (For ω = ⊕ an exponential lower bound was already obtained in [5] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined fnction which can be represented by polynomial size ω-nondeterministic BP1s that it has exponential complexity in the ω-nondeterministic well-structured g.d.-BP1 model for $$ \omega \in \{ \vee , \oplus \} $$ .This answers an open question from Brosenne, Homeister, and Waack [7], whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant. [ABSTRACT FROM AUTHOR]