__
Revision #1 to TR01-073 | 7th January 2002 00:00
__
#### Parity Graph-driven 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. 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.

__
TR01-073 | 24th October 2001 00:00
__

#### Parity Graph-driven 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. 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.