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].

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