Using communication complexity concepts and techniques, we derive linear (/spl Omega/(n)) and almost-linear (/spl Omega/(n/logn)) lower bounds on the size of circuits implementing certain functions. Our approach utilizes only basic features of the gates used, hence the bounds hold for general families of gates of which the symmetric and threshold gates are special cases. 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 recent results.
展开▼
