Lower bound on weights of large degree threshold functions

DOI10.2168/LMCS-9(2:13)2013MaRDI QIDQ5891072zbMATH OpenOpenAlexFDO

Authors Vladimir V. Podolskii

Publication date 9 July 2013

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-9(2:13)2013

zbMATH Keywords

lower boundsthreshold functionperceptronthreshold gate

Mathematics Subject Classification ID

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

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

(10)

• Perceptrons of large weight
• Algebraic Techniques for Constructing Minimal Weight Threshold Functions
• Perceptrons of Large Weight
• Degree-uniform lower bound on the weights of polynomials with given sign function
• Weights of exact threshold functions
• Weights of exact threshold functions
• A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
• A better upper bound on weights of exact threshold functions
• Lower bound on weights of large degree threshold functions
• Directed projection graph of \(N\)-dimensional hypercube and subhypercube decomposition of balanced linearly separable Boolean functions

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 Q5891072)