# zbMATH — the first resource for mathematics

A uniform lower bound on weights of perceptrons. (English) Zbl 1142.94400
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 261-272 (2008).
Summary: A threshold gate is a linear function of input variables with integer coefficients (weights). It outputs 1 if the value of the function is positive. The sum of absolute values of coefficients is called the total weight of the threshold gate. A perceptron of order $$d$$ is a circuit of depth 2 having a threshold gate on the top level and conjunctions of fan-in at most $$d$$ on the remaining level.
For every $$n$$ and $$d\leq D\leq \varepsilon n^{1/6}$$ we construct a function computable by a perceptron of order $$d$$ but not computable by any perceptron of order $$D$$ with total weight $$2^{o(n^d/D^{4d})}$$. In particular, if $$D$$ is a constant, our function is not computable by any perceptron of order $$D$$ with total weight $$2^{o(n^d)}$$. Previously functions with this properties were known only for $$d = 1$$ (and arbitrary $$D$$) and for $$D = d$$.
For the entire collection see [Zbl 1136.68005].

##### MSC:
 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: