Abstract
A real multivariate polynomial p(x 1, …, x n ) is said to sign-represent a Boolean function f: {0,1}n→{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1}n. We give new upper and lower bounds on the degree of 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Ambainis, A. Childs, B. Reichardt, R. Spalek and S. Zhang: Any ANDOR formula of size n can be evaluated in time n1/2+o(1) on a quantum computer, in: Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pages 363–372, 2007.
D. Angluin: Queries and concept learning, Machine Learning2 (1988), 319–342.
J. Aspnes, R. Beigel, M. Furst and S. Rudich: The expressive power of voting polynomials, Combinatorica14(2) (1994), 1–14.
R. Beigel: The polynomial method in circuit complexity, in: Proceedings of the Eigth Conference on Structure in Complexity Theory, pages 82–95, 1993.
R. Beigel: Perceptrons, PP, and the Polynomial Hierarchy, Computational Complexity4 (1994), 339–349.
R. Beigel, N. Reingold and D. Spielman: PP is closed under intersection, Journal of Computer & System Sciences50(2) (1995), 191–202.
J. Bruck: Harmonic analysis of polynomial threshold functions, SIAM Journal on Discrete Mathematics3(2) (1990), 168–177.
H. Buhrman, R. Cleve and A. Wigderson: Quantum vs. classical communication and computation, in: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 63–68. ACM Press, 1998.
H. Buhrman and R. de Wolf: Complexity measures and decision tree complexity: a survey; Theoretical Computer Science288(1) (2002), 21–43.
E. Cheney: Introduction to approximation theory, McGraw-Hill, New York, New York, 1966.
L. Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions; Reidel, Dordrecht, Netherlands, 1974.
Y. Freund: Boosting a weak learning algorithm by majority, Information and Computation121(2) (1995), 256–285.
M. Goldmann: On the power of a threshold gate at the top, Information Processing Letters63(6) (1997), 287–293.
A. Hajnal, W. Maass, P. Pudlák, M. Szegedy and Gy. Turán: Threshold circuits of bounded depth, Journal of Computer and System Sciences46 (1993), 129–154.
M. Kearns and U. Vazirani: An introduction to computational learning theory. MIT Press, Cambridge, MA, 1994.
A. Klivans, R. O’Donnell and R. Servedio: Learning intersections and thresholds of halfspaces, in: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, pages 177–186, 2002.
A. Klivans and R. Servedio: Learning DNF in time 2Õ(n1/3), in: Proceedings of the Thirty-Third Annual Symposium on Theory of Computing, pages 258–265, 2001.
M. Krause and P. Pudlák: Computing boolean functions by polynomials and threshold circuits, Computational Complexity7(4) (1998), 346–370.
N. Linial, Y. Mansour and N. Nisan: Constant depth circuits, Fourier transform and learnability; Journal of the ACM40(3) (1993), 607–620.
N. Littlestone: Learning quickly when irrelevant attributes abound: a new linearthreshold algorithm; Machine Learning2 (1988), 285–318.
M. Minsky and S. Papert: Perceptrons: an introduction to computational geometry (expanded edition); MIT Press, Cambridge, MA, 1988.
D. J. Newman: Rational approximation to |x|, Michigan Mathematical Journal11 (1964), 11–14.
N. Nisan and M. Szegedy: On the degree of Boolean functions as real polynomials, in: Proceedings of the Twenty-Fourth Annual Symposium on Theory of Computing, pages 462–467, 1992.
R. O’Donnell and R. Servedio: New degree bounds for polynomial threshold functions, in: Proceedings of the 35th ACM Symposium on Theory of Computing, pages 325–334, 2003.
R. Paturi and M. Saks: Approximating threshold circuits by rational functions, Information and Computation112(2) (1994), 257–272.
M. Saks: Slicing the hypercube, in: Surveys in Combinatorics 1993 (Keith Walker, ed.), London Mathematical Society Lecture Note Series 187, pages 211–257, 1993.
D. Sieling: Minimization of decision trees is hard to approximate, Journal of Computer and System Sciences74(3) (2008), 394–403.
L. Valiant: A theory of the learnable, Communications of the ACM27(11) (1984), 1134–1142.
N. Vereshchagin: Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP, in: Proceedings of the Third Annual Israel Symposium on Theory of Computing and Systems, pages 46–51, 1995.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of these results appeared as [24].
This work was done while at the Department of Mathematics, MIT, Cambridge, MA, and while supported by NSF grant 99-12342.
Supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship and by NSF grant CCR-98-77049. This work was done while at the Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA.
Rights and permissions
About this article
Cite this article
O’Donnell, R., Servedio, R.A. New degree bounds for polynomial threshold functions. Combinatorica 30, 327–358 (2010). https://doi.org/10.1007/s00493-010-2173-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-010-2173-3