Publications

New 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.

BibTeX:
@inproceedings{InProc-Woe2001a, author = {Philipp Woelfel}, title = {New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing}, booktitle = {18th International Symposium on Theoretical Aspects of Computer Science (STACS)}, pages = {563-574}, year = {2001}, series = {LNCS}, volume = {2010}, doi = {10.1007/3-540-44693-1_49}, }