Lower bounds on threshold and related circuits via communication complexity
Vwani Roychowdhury, Alon Orlitsky, Kai-Yeung Sunny Siu · IEEE Transactions on Information Theory · 1994
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.>