__
TR00-046 | 19th June 2000 00:00
__

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

**Abstract:**
Ordered binary decision diagrams (OBDDs) belong to the most important

representation types for Boolean functions. Although they allow

important operations such as satisfiability test and equality test to

be performed efficiently, their limitation lies in the fact, that they

may require exponential size for important functions. Bryant has shown

in 1991 that any OBDD-representation of the function MUL[n-1,n], which

computes the middle bit of the product of two n-bit numbers, requires

at least 2^(n/8) nodes. This paper improves this bound to

(1/96)*2^(n/2) by a new technique, using a recently found universal

family of hash functions. As a result, one cannot hope anymore to find

reasonable small OBDDs even for the multiplication of relatively short

integers, since for only a 64-bit multiplication millions of nodes are

required. Further, a first non-trivial upper bound of (7/3)*2^(4n/3)

for the OBDD size of MUL[n-1,n] is provided.