Podolskii, Vladimir V. Lower bound on weights of large degree threshold functions. (English) Zbl 1297.68086 Log. Methods Comput. Sci. 9, No. 2, Paper No. 13, 17 p. (2013). Summary: An integer polynomial \(p\) of \(n\) variables is called a threshold gate for a Boolean function \(f\) of \(n\) variables if, for all \(x\in \{0,1\}^{n}\), \(f(x)=1\) if and only if \(p(x)\geqslant 0\). The weight of a threshold gate is the sum of its absolute values.In this paper we study how large a weight might be needed if we fix some function and some threshold degree. We prove \(2^{\Omega (2^{2n/5})}\) lower bound on this value. The best previous bound was \(2^{\Omega (2^{n/8})}\) [the author, Probl. Inf. Transm. 45, No. 1, 46–53 (2009); translation from Probl. Peredachi Inf. 45, No. 1, 51–59 (2009; Zbl 1171.68585)].In addition we present substantially simpler proof of the weaker \(2^{\Omega (2^{n/4})}\) lower bound. This proof is conceptually similar to other proofs of the bounds on weights of nonlinear threshold gates, but avoids a lot of technical details arising in other proofs. We hope that this proof will help to show the ideas behind the construction used to prove these lower bounds. Cited in 1 Document MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) Keywords:threshold gate; threshold function; perceptron; lower bounds Citations:Zbl 1171.68585 PDFBibTeX XMLCite \textit{V. V. Podolskii}, Log. Methods Comput. Sci. 9, No. 2, Paper No. 13, 17 p. (2013; Zbl 1297.68086) Full Text: DOI