TR10-039 Authors: Gil Cohen, Amir Shpilka

Publication: 10th March 2010 12:04

Downloads: 1525

Keywords:

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.