Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication

摘要

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs have been studied intensively. Exponential lower bounds for 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 and an exponential lower bound on the size of the so-called 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.