A Read-Once Branching Program Lower Bound of Omega (2 n/4 ) for Integer Multiplication using Universal Hashing

Beate Bollig and Philipp Woelfel

Abstract. Branching programs (BPs) are a well-established computation and representation model for Boolean functions. Especially read-once branching programs (BP1s) have been studied intensively. Exponential lower bounds on the BP1 complexity of explicit functions have been known for a long time. Nevertheless, the proof of exponential lower bounds on the read-once branching program size of selected functions is sometimes difficult. Motivated by the applications the BP1 complexity of fundamental functions is of interest. It took quite a long time until Ponzio (1998) was able to prove a bound of 2Ω(√n) for integer multiplication. Combining results and methods for universal hashing with lower bound techniques for BP1s a lower bound of Ω(2n/4) on the size of BP1s for integer multiplication is presented in this paper.


Notes