Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Abstract. Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nonde-terministic read-once branching programs, i.e., the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are de ned and a lower bound method is presented. Furthermore, the rst exponential lower bound for integer multiplication on the size of a nonde-terministic nonoblivious read-once branching program model is proven