On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication

From bibtex.

Abstract

This paper presents lower bound results on Boolean function complexity under two different models. The first is an abstraction of tradeoffs between chip area and speed in very large scale integrated (VLSI) circuits. The second is the ordered binary decision diagram (OBDD) representation used as a data structure for symbolically representing and manipulating Boolean functions. These lower bounds demonstrate the fundamental limitations of VLSI as an implementation medium, and OBDDs as a data structure. They also lend insight into what properties of a Boolean function lead to high complexity under these models. Related techniques can be used to prove lower bounds in the two models. That is, the same technique used to prove that any VLSI implementation of a single output Boolean function has area-time complexity AT^2 = Omega(n^2) also proves that any OBDD representation of the function has Omega(c^n) vertices for some c > 1. The converse is not true, however. There are functions for which any OBDD representation is of exponential size, but there is a VLSI implementation of complexity AT^2 = O(n^(1+epsilon)). Consider an integer multiplier for word size n with outputs numbered 0 (least significant) through 2n-1 (most significant). For the Boolean function representing either output i-1 or output 2n-i-1, where 1 <= i <= n, the following lower bounds are proved: (1) any VLSI implementation must have AT^2 = Omega(i^2), and (2) any OBDD representation must have Omega(1.09^i) vertices.