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.