Abstract
Communication-complexity definitions and arguments are used to derive linear (Q(n)) and almost-linear (Q(n/ log n)) lower bounds on the size of circuits implementing certain functions. The techniques utilize only basic features of the gates used and of the functions implemented hence apply to a large class of gates (including unbounded fan-in AND/OR, threshold, symmetric, and generalized symmetric) and to a large class of functions (including equality, comparison, and inner product mod 2). Each of the bounds derived is shown to be tight for some functions and some applications to threshold-circuit complexity are indicated. The results generalize and in some cases strengthen results in [1, 2]
Keywords
Linear/Almost-Linear Circuit-size Lower Bounds; Communication Complexity, Threshold gates/circuits; Symmetric gates/circuits; Equality, Comparison and Inner Product mod 2 Boolean functions
Date of this Version
July 1992