Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On the Degree of Symmetric Functions on the Boolean Cube
event speaker icon
Gil Cohen (CS, Technion)
event date icon
Wednesday, 17.03.2010, 12:30
event location icon
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.