CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:BOHsiamjdm03

[img]
Preview
PDF
See Usage Policy.

156Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BOHsiamjdm03

Abstract

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
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
Record Number:CaltechAUTHORS:BOHsiamjdm03
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BOHsiamjdm03
Alternative URL:http://dx.doi.org/10.1137/S0895480197326048
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:563
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:08 Aug 2005
Last Modified:26 Dec 2012 08:40

Repository Staff Only: item control page