期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
