Lower bound on weights of large degree threshold functions

DOI10.1007/978-3-642-30870-3_60MaRDI QIDQ5891704zbMATH OpenOpenAlexFDO

Authors Vladimir V. Podolskii

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.2652

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: An integer polynomial $p$ of $n$ variables is called a emph{threshold gate} for a Boolean function $f$ of $n$ variables if for all $xinzoon$ $f(x)=1$ if and only if $p(x)geq0$. 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.

Recommendations

• Lower bound on weights of large degree threshold functions
• Degree-uniform lower bound on the weights of polynomials with given sign function
• On the Size of Weights for Threshold Gates
• Perceptrons of large weight
• Algebraic Techniques for Constructing Minimal Weight Threshold Functions

Cited in

(11)

• Degree-uniform lower bound on the weights of polynomials with given sign function
• A better upper bound on weights of exact threshold functions
• A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
• Perceptrons of Large Weight
• A Uniform Lower Bound on Weights of Perceptrons
• Weights of exact threshold functions
• On the Size of Weights for Threshold Gates
• Algebraic Techniques for Constructing Minimal Weight Threshold Functions
• Weights of exact threshold functions
• Lower bound on weights of large degree threshold functions
• Perceptrons of large weight

This page was built for publication: Lower bound on weights of large degree threshold functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891704)