On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)

Abstract

In this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. Let Γ(f)=min{|2k–n+1|:fk ≠ fk+ 1 and 0 ≤ k ≤ n – 1} where fi is the value of f on inputs with exactly i 1's. We prove that the minimum degree over all the approximating polynomials of f is Θ((n(n-Γ(f))).5). We apply the techniques and tools from approximation theory to derive this result.