New Degree Bounds for Polynomial Threshold Functions.
R. O'Donnell and R. Servedio.
Combinatorica 30(3), 2010, pp. 327-358.
Preliminary version in 35th Annual Symposium on Theory of Computing (STOC), 2003, pp. 325-334.


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 {\em 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 {\em constructively}; we give explicit dual solutions to the necessary linear programs.

pdf of conference version

pdf of journal version

Back to main papers page