LOWER BOUNDS ON THRESHOLD AND RELATED CIRCUITS VIA COMMUNICATION COMPLEXITY

Authors
ROYCHOWDHURY VP ORLITSKY A SIU KY
Citation
Vp. Roychowdhury et al., LOWER BOUNDS ON THRESHOLD AND RELATED CIRCUITS VIA COMMUNICATION COMPLEXITY, IEEE transactions on information theory, 40(2), 1994, pp. 467-474
Citations number
14
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
40
Issue
2
Year of publication
1994
Pages
467 - 474
Database
ISI
SICI code
0018-9448(1994)40:2<467:LBOTAR>2.0.ZU;2-B
Abstract
Using communication complexity concepts and techniques, we derive line ar (OMEGA(n)) and almost-linear (OMEGA(n/logn)) lower bounds on the si ze of circuits implementing certain functions. Our approach utilizes o nly basic features of the gates used, hence the bounds hold for genera l families of gates of which the symmetric and threshold gates are spe cial cases. Each of the bounds derived is shown to be tight for some f unctions and some applications to threshold circuit complexity are ind icated. The results generalize and in some cases strengthen recent res ults.