Lower Bound on Weights of Large Degree Threshold Functions

Details Lower Bound on Weights of Large Degree Threshold Functions Lower Bound on Weights of Large Degree Threshold Functions

2012-04-12

arxiv.org/abs/1204.2652v1

Computer Science

Computational Complexity

23 pages, an extended abstract of this paper to appear in the proceedings of CiE 2012 conference

Scientific paper

An integer polynomial $p$ of $n$ variables is called a \emph{threshold gate} for the Boolean function $f$ of $n$ variables if for all $x \in \{0,1\}^n$ $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 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.

Affiliated with

Also associated with

No associations

Rating

Lower Bound on Weights of Large Degree Threshold Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bound on Weights of Large Degree Threshold Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bound on Weights of Large Degree Threshold Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312143