Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds for parity read-once branching
programs is still open. In this paper restricted parity read-once
branching programs are considered. Parity graph-driven read-once
branching programs have been investigated intensively by Brosenne,
Homeister, and Waack (2001). Here, an exponential lower bound on
the size of well-structured parity graph-driven read-once branching
programs for integer multiplication is proven. This is the first
strongly exponential lower bound on the size of a parity
nonoblivious read-once branching program model for an explicitly
defined Boolean function. In addition, more insight into the
structure of integer multiplication is yielded.

Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds for parity read-once
branching programs is still open. In this paper restricted parity
read-once branching programs are considered.
Parity graph-driven read-once branching programs introduced by
Bollig (2000) have been investigated intensively by
Brosenne, Homeister, and Waack (2001)
Here, the first strongly exponential lower bound for integer multiplication
on the size of a parity nonoblivious read-once branching program model
is proven.