New degree bounds for polynomial threshold functions (Q5894427): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / DOI | |||
Property / DOI: 10.1007/s00493-010-2173-3 / 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
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
polynomial treshold functions
0 references
Boolean functions
0 references
learning theory
0 references
complexity theory
0 references