A read-once branching program lower bound of Ω(2n/4) for integer multiplication using universal hashing
Beate Bollig, Philipp Woelfel · 2001
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 [16, 17] was able to prove a bound of 2^{Ω(\sqrt{n})} for integer multiplication. Combining results and methods for universal hashing with lower bound techniques for BP1s a lower bound of Ω(2^{n/4}) on the size of BP1s for integer multiplication is presented in this paper.