file.pdf (276.22 kB)
Download file

New degree bounds for polynomial threshold functions

Download (276.22 kB)
journal contribution
posted on 01.01.1980, 00:00 authored 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



Usage metrics