Abstract of Paper

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication
by Beate Bollig


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 nondeterministic
read-once branching programs, i.e., the class of functions representable in
polynomial size, is investigated. For that reason two restricted models of
nondeterminitic read-once branching programs are defined and a lower bound
method is presented. Furthermore, the first exponential lower bound for
integer multiplication on the size of a nondeterministic nonoblivious
read-once branching program model is proven.