Theory Seminar: On the Degree of Symmetric Functions on the Boolean Cube

Gil Cohen (CS, Technion)

Wednesday, 17.03.2010, 12:30

Taub 201

In the 1997 paper "Polynomials with two values" by von zur Gathen and Roche (Combinatorica), the
authors proved that the degree of any non-constant symmetric function of the form $f:{0,1}^n \rightarrow
{0,1}$ is $n-o(n)$ (where the degree of a function is defined to be the degree of the unique interpolation
polynomial, of degree at most $n$, of the function). In their proof, the authors heavily used the fact that
the function is Boolean. The authors therefore asked what can be said about the degree of functions of
the form $f:{0,1}^n \rightarrow {0,1,2,...,c}$.

While for $c=1$ the result above assures us all such functions have high degree, it is easy to see that for $c=n$ there exist a function with degree 1. The authors proved a lower bound of $(n+1)/(c+1)$ for general $c$.

In this talk we show what we consider to be an interesting threshold phenomenon: For every $c

Joint work with Amir Shpilka.

While for $c=1$ the result above assures us all such functions have high degree, it is easy to see that for $c=n$ there exist a function with degree 1. The authors proved a lower bound of $(n+1)/(c+1)$ for general $c$.

In this talk we show what we consider to be an interesting threshold phenomenon: For every $c

Joint work with Amir Shpilka.