New degree bounds for polynomial threshold functions (Q5894427)

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.