CaltechAUTHORS
  A Caltech Library Service

On the Power of Threshold Circuits with Small Weights

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

[img]
Preview
PDF - Published Version
See Usage Policy.

65Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120424-103938302

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 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
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ISIT.1991.695138DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=695138PublisherUNSPECIFIED
Additional Information:© 1991 IEEE. Date of Current Version: 06 August 2002.
Record Number:CaltechAUTHORS:20120424-103938302
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120424-103938302
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.
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