The Taub Faculty of Computer Science Events and Talks

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.