ECCC-Report TR01-073https://eccc.weizmann.ac.il/report/2001/073Comments and Revisions published for TR01-073en-usMon, 07 Jan 2002 00:00:00 +0200
Revision 1
| Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication |
Beate Bollig,
Stephan Waack,
Philipp Woelfel
https://eccc.weizmann.ac.il/report/2001/073#revision1Branching 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.
Mon, 07 Jan 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/073#revision1
Paper TR01-073
| Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication |
Beate Bollig,
Philipp Woelfel,
Stephan Waack
https://eccc.weizmann.ac.il/report/2001/073
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.
Mon, 29 Oct 2001 17:02:58 +0200https://eccc.weizmann.ac.il/report/2001/073