A Caltech Library Service

Algebraic techniques for constructing minimal weight threshold functions

Bohossian, Vasken and Bruck, Jehoshua (2003) Algebraic techniques for constructing minimal weight threshold functions. SIAM Journal on Discrete Mathematics, 16 (1). pp. 114-126. ISSN 0895-4801. doi:10.1137/S0895480197326048.

See Usage Policy.


Use this Persistent URL to link to this item:


A linear threshold element computes a function that is a sign of a weighted sum of the input variables. The best known lower bounds on the size of threshold circuits are for depth-2 circuits with small (polynomial-size) weights. However, in general, the weights are arbitrary integers and can be of exponential size in the number of input variables. Namely, obtaining progress in lower bounds for threshold circuits seems to be related to understanding the role of large weights. In the present literature, a distinction is made between the two extreme cases of linear threshold functions with polynomial-size weights, as opposed to those with exponential-size weights. Our main contributions are in devising two novel methods for constructing threshold functions with minimal weights and filling up the gap between polynomial and exponential weight growth by further refining the separation. Namely, we prove that the class of linear threshold functions with polynomial-size weights can be divided into subclasses according to the degree of the polynomial. In fact, we prove a more general result — that there exists a minimal weight linear threshold function for any arbitrary number of inputs and any weight size.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2003 Society for Industrial and Applied Mathematics. Received by the editors August 13, 1997; accepted for publication (in revised form) July 22, 2002; published electronically January 3, 2003. Part of this work was presented in Proceedings of Neural Information Processing Systems 8, 1995, under the title On Neural Networks with Minimal Weights, by the authors of this paper.
Subject Keywords:threshold functions, computational complexity, neural networks
Issue or Number:1
Record Number:CaltechAUTHORS:BOHsiamjdm03
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:563
Deposited By: Tony Diaz
Deposited On:08 Aug 2005
Last Modified:08 Nov 2021 19:03

Repository Staff Only: item control page