file.pdf (276.22 kB)

New degree bounds for polynomial threshold functions

Download (276.22 kB)
journal contribution
posted on 01.01.1980 by Ryan O'Donnell, Rocco Servedio
We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs


Publisher Statement

All Rights Reserved