Perceptrons of Large Weight

Abstract

A threshold gate is a sum of input variables with integer coefficients (weights). It outputs 1 if the sum is positive. The maximal absolute value of coefficients of a threshold gate is called its weight. A perceptron of order d is a circuit of depth 2 having a threshold gate on the top level and any Boolean gates of fan-in at most d on the remaining level.

For every constant d ≥ 2 independent of the number of inputs n we exhibit a perceptron of order d that requires weights at least $n^{\Omega(n^d)}$, that is, the weight of any perceptron of order d computing the same Boolean function is at least $n^{\Omega(n^d)}$. This bound is tight: every perceptron of order d is equivalent to a perceptron of order d and weight $n^{O(n^d)}$. In the case of threshold gates (i.e. d = 1) the result was established by Håstad in [1]; we use Håstad’s techniques.