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 ...
more >>>