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

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 OBDD’s as a data structure. They also lend insight into what properties of a Boolean function lead to high complexity under these models