New degree bounds for polynomial threshold functions (Q5894427): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
(2 intermediate revisions by one other user not shown)
Property / DOI
 
Property / DOI: 10.1007/s00493-010-2173-3 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00493-010-2173-3 / rank
 
Normal rank

Latest revision as of 23:56, 9 December 2024

scientific article; zbMATH DE number 5990558
Language Label Description Also known as
English
New degree bounds for polynomial threshold functions
scientific article; zbMATH DE number 5990558

    Statements

    New degree bounds for polynomial threshold functions (English)
    0 references
    0 references
    0 references
    19 December 2011
    0 references
    A real multivariate polynomial \(p(x_1, \ldots , x_n)\) is said to sign-represent a Boolean function \(f \colon \{0,1\}^n \to \{-1,1\}\) if the sign of \(p(x)\) equals \(f(x)\) for all inputs \(x \in \{0,1\}^n\). This paper provides upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. The upper bounds yield subexponential time learning algorithms for formulas of superconstant depth. The lower bounds for constant-depth circuits and intersections of halfspaces improve results of \textit{M. Minsky} and \textit{S. A. Papert} [Perceptrons. expanded ed. London: MIT Press. xvi, 292 p. (1988; Zbl 0794.68104)]. They are proved constructively; explicit dual solutions to the necessary linear programs are given.
    0 references
    0 references
    polynomial treshold functions
    0 references
    Boolean functions
    0 references
    learning theory
    0 references
    complexity theory
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references