A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications

Abstract. We present a new lower bound technique for a well-studied 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 OR, AND, and XOR. We apply the technique in order to prove an exponential lower bound for integer multiplication for omega-nondeterministic well-structured g.d.-BP1s for all these acceptance modes. (Note that for the acceptance mode XOR, an exponential lower bound was already obtained by Bollig, Waack and Woelfel (2002) by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined function which can be represented by polynomial size nondeterministic BP1s that it has exponential complexity in the nondeterministic well-structured g.d. BP1 model for the acceptance modes OR and XOR. This answers an open question from Brosenne, Homeister, and Waack (2001), whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant

Notes

• Appeared in Theory of Computing Systems, Vol. 38, No. 6, pp. 671-685. Springer, 2005.


• Article available from Springer Online


• Preliminary journal version as ps or pdf file (© Springer).


• Extended abstract appeared in Mathematical Foundations of Computer Science 2002; 27th International Symposium,
  Lecture Notes in Computer Science 2420, Springer, pp. 131-142, 2002