ECCC-Report TR10-039https://eccc.weizmann.ac.il/report/2010/039Comments and Revisions published for TR10-039en-usSun, 09 Jan 2011 12:11:52 +0200
Comment 1
| TR10-039 |
Gil Cohen,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2010/039#comment1This paper is superseded by the ECCC Technical
Report TR11-002.Sun, 09 Jan 2011 12:11:52 +0200https://eccc.weizmann.ac.il/report/2010/039#comment1
Paper TR10-039
| On the degree of symmetric functions on the Boolean cube |
Gil Cohen,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2010/039In 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.Wed, 10 Mar 2010 12:04:21 +0200https://eccc.weizmann.ac.il/report/2010/039