Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

Philipp Woelfel

Abstract. Bryant [5] has shown that any OBDD for the middle bit of the n-bit multiplication, MUL, requires at least 2^(n/8) nodes. In this paper a stronger lower bound of essentially 2^(n/2) is proven by a new technique, using a universal family of hash functions. As a consequence, one cannot hope anymore to verify e.g. 128-bit multiplication circuits using OBDD-techniques because the representation of the middle bit of such a multiplier requires more than 10^17 OBDD-nodes. Further, a first non-trivial upper bound of essentially 2^(4n/3) for the OBDD-size of MUL is provided.

Notes