In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in
\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our
result shows a surprising threshold phenomenon. The question of
lower bounding the degree of symmetric functions on the Boolean
cube was previously studied by von zur Gathen and Roche who showed the lower bound deg$(f)\geq \frac{n+1}{c+1}$ and so our result greatly improves this bound.
When $c=1$, namely the function maps the Boolean cube to $\{0,1\}$, we show that if $n=p^2$, when $p$ is a prime, then
deg$(f)\geq n-\sqrt{n}$. This slightly improves the previous bound of von zur Gathen and Roche for this case.
This paper is superseded by the ECCC Technical
Report TR11-002.
