Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

RSS-Feed

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.


Paper:

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.



ISSN 1433-8092 | Imprint