Siu, Kai-Yeung 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 0-7803-0056-4 http://resolver.caltech.edu/CaltechAUTHORS:20120424-103938302
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120424-103938302
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 integers-exponential 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 depth-3, polynomial size network of LTEs with small weights, 2) every depth-d 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 n-bits numbers, and the MAXIMUM and the SORTING of n n-bit numbers.
|Item Type:||Book Section|
|Additional Information:||© 1991 IEEE. Date of Current Version: 06 August 2002.|
|Official Citation:||Kai-Yeung 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.91CH3003-1) , vol., no., pp.82, 24-28 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.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||24 Apr 2012 18:23|
|Last Modified:||26 Dec 2012 15:06|
Repository Staff Only: item control page