Siu, KaiYeung and Bruck, Jehoshua (1991) On the Power of Threshold Circuits with Small Weights. In: 1991 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, p. 82. ISBN 0780300564 http://resolver.caltech.edu/CaltechAUTHORS:20120424103938302

PDF
 Published Version
See Usage Policy. 65Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120424103938302
Abstract
Linear threshold elements (LTEs) are the basic processing elements in artificial neural networks. An LTE computes a function that is a sign of a weighted sum of the input variables. The weights are arbitrary integers; actually they can be very big integersexponential in the number of input variables. However, in practice, it is very difficult to implement big weights. So the natural question that one can ask is whether there is an efficient way to simulate a network of LTEs with big weights by a network of LTEs with small weights. We prove the following results: 1) every LTE with big weights can be simulated by a depth3, polynomial size network of LTEs with small weights, 2) every depthd polynomial size network of LTEs with big weights can be simulated by a depth(2d+1), polynomial size network of LTEs with small weights. To prove these results, we use tools from harmonic analysis of Boolean functions. Our technique is quite general, it provides insights to some other problems. For example, we were able to improve the best known results on the depth of a network of threshold elements that computes the COMPARISON, ADDITION and PRODUCT of two nbits numbers, and the MAXIMUM and the SORTING of n nbit numbers.
Item Type:  Book Section  

Related URLs: 
 
Additional Information:  © 1991 IEEE. Date of Current Version: 06 August 2002.  
Record Number:  CaltechAUTHORS:20120424103938302  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20120424103938302  
Official Citation:  KaiYeung Siu; Bruck, J.; , "On The Power Of Threshold Circuits With Small Weights," Information Theory, 1991 (papers in summary form only received), Proceedings. 1991 IEEE International Symposium on (Cat. No.91CH30031) , vol., no., pp.82, 2428 Jun 1991 doi: 10.1109/ISIT.1991.695138 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=695138&isnumber=4025  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  30278  
Collection:  CaltechAUTHORS  
Deposited By:  Ruth Sustaita  
Deposited On:  24 Apr 2012 18:23  
Last Modified:  26 Dec 2012 15:06 
Repository Staff Only: item control page