Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-046 | 19th June 2000 00:00

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


Authors: Philipp Woelfel
Publication: 5th July 2000 12:17
Downloads: 2766


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.

ISSN 1433-8092 | Imprint