• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдены 2 публикации
Сортировка:
по названию
по году
Статья
Podolskii V. V. 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.

Добавлено: 20 октября 2014
Статья
Sergey Slavnov. Logical Methods in Computer Science. 2019. Vol. 15. No. 3. P. 1-25.
Добавлено: 23 октября 2019