首页    期刊浏览 2025年06月10日 星期二
登录注册

文章基本信息

  • 标题:Lower Bound on Weights of Large Degree Threshold Functions
  • 本地全文:下载
  • 作者:Vladimir Podolskii
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2013
  • 卷号:9
  • 期号:2
  • 页码:1
  • DOI:10.2168/LMCS-9(2:13)2013
  • 出版社:Technical University of Braunschweig
  • 摘要:An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate} for a Boolean function $f$ of $n$ variables if for all $x \in \zoon$ $f(x)=1$ if and only if $p(x)\geq 0$. The \emph{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})}$ (Podolskii, 2009). 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.
  • 其他关键词:threshold gate, threshold function, perceptron, lower bounds.
国家哲学社会科学文献中心版权所有