10.1184/R1/6607712.v1 Ryan O'Donnell Ryan O'Donnell Rocco Servedio Rocco Servedio New degree bounds for polynomial threshold functions Carnegie Mellon University 1980 computer sciences 1980-01-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/New_degree_bounds_for_polynomial_threshold_functions/6607712 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