Extremal properties of polynomial threshold functions

摘要

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following:•Almost every Boolean function has PTF degree at most n2+O(nlogn). Together with results of Anthony and Alon, this establishes a conjecture of Wang and Williams [C. Wang, A.C. Williams, The threshold order of a Boolean function, Discrete Appl. Math. 31 (1991) 51–69] and Aspnes, Beigel, Furst, and Rudich [J. Aspnes, R. Beigel, M. Furst, S. Rudich, The expressive power of voting polynomials, Combinatorica 14 (2) (1994) 1–14] up to lower order terms.•Every Boolean function has PTF density at most (1−1O(n))2n. This improves a result of Gotsman [C. Gotsman, On Boolean functions, polynomials and algebraic threshold functions, Technical Report TR-89-18, Department of Computer Science, Hebrew University, 1989].•Every Boolean function has weak PTF density at most o(1)2n. This gives a negative answer to a question posed by Saks [M. Saks, Slicing the hypercube, in: London Math. Soc. Lecture Note Ser., vol. 187, 1993, pp. 211–257].•PTF degree ⌊log2m⌋+1 is necessary and sufficient for Boolean functions with sparsity m. This answers a question of Beigel [R. Beigel, personal communication, 2000]. We also give new extremal bounds on polynomials which approximate Boolean functions in the ℓ∞ norm.