• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Lower bound on weights of large degree threshold functions

Logical Methods in Computer Science. 2013. Vol. 9. No. 2. P. 1-17.

An integer polynomial p of n variables is called a threshold gate for a Boolean function f of n variables if for all x∈{0,1}n f(x)=1 if and only if p(x) > 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Ω(22n/5) lower bound on this value. The best previous bound was 2Ω(2n/8) (Podolskii, 2009). In addition we present substantially simpler proof of the weaker 2Ω(2n/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.