Four results on the complexity of VLSI computations

Abstract

We present four results on the complexity of VLSI computations: a) We further justify the Boolean circuit model [Vu, Sa, LS] by showing that it is able to model multi-directional VLSI devices (e.g. pass transistors, pre-charged bus drivers). b) We prove a general cutting theorem for compact regions in R^{d} (d\geq2) that allows us to drop the convexity assumption in lower bound proofs based on the crossing sequence argument. c) We exhibit an \Omega(n^{1/3}) asymptotically tight lower bound on the area of strongly where-oblivious chips for transitive functions. d) We prove a lower bound on the switching energy needed for computing transitive functions.