Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-039 | 10th March 2010 12:04

On the degree of symmetric functions on the Boolean cube

RSS-Feed




TR10-039
Authors: Gil Cohen, Amir Shpilka
Publication: 10th March 2010 12:04
Downloads: 1525
Keywords: 


Abstract:

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.


Comment(s):

Comment #1 to TR10-039 | 9th January 2011 12:11

TR10-039

Authors: Gil Cohen, Amir Shpilka
Accepted on: 9th January 2011 12:11
Keywords: 


Comment:

This paper is superseded by the ECCC Technical
Report TR11-002.




ISSN 1433-8092 | Imprint