Bounds on the OBDD-size of integer multiplication via universal hashing

Bryant [On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication, IEEE Trans. Comput. 40 (1991) 205-213] has shown that any OBDD for the function MUL_n-1,n, i.e. the middle bit of the n-bit multiplication, requires at least 2^n/8 nodes. In this paper a stronger lower bound of essentially 2^n/2/61 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 3·10¹⁷OBDD-nodes. Further, a first non-trivial upper bound of 7/3·2^4n/3 for the OBDD-size of MUL_n-1,n is provided.