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. The weight of a perceptron is the weight of its threshold gate.
For every $d > 1$ we exhibit a perceptron of order $d$ that requires weight 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.d. $d=1$) the result was established by Hastad; we use Hastad's techniques.
© 2006—2007 Kolmogorov seminar
Feedback