×

Lower bound on weights of large degree threshold functions. (English) Zbl 1297.68086

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.

MSC:

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

Citations:

Zbl 1171.68585
PDFBibTeX XMLCite
Full Text: DOI