On the Power of Threshold Circuits with Small Weights
Authors:
- Kai-Yeung SiuKSKai-Yeung Siu
- Jehoshua BruckJBJehoshua Bruck
- 1 August 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 4 (3) , 423-435
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 may be asked is whether there is an efficient way to simulate a network of LTEs with big weights by a network of LTEs with small weights. The following results are proved: (1) every LTE with big weights can be simulated by a depth-3, polynomial size network of LTEs with small weights; and (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, tools from harmonic analysis of Boolean functions are used. The technique is quite general; it provides insights to some other problems. For example, 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 nn-bit numbers are improved.Keywords
This publication has 11 references indexed in Scilit:
- Harmonic Analysis of Polynomial Threshold FunctionsSIAM Journal on Discrete Mathematics, 1990
- Neural computation of arithmetic functionsProceedings of the IEEE, 1990
- The complexity of computations by networksIBM Journal of Research and Development, 1987
- Parallel computation with threshold functions1986
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- HARMONIC ANALYSIS OF SWITCHING FUNCTIONS1971
- Lower Bound of the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1966
- Bounds on the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1966
- A Lower Bound of the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1965
- On the Size of Weights Required for Linear-Input Switching FunctionsIEEE Transactions on Electronic Computers, 1961