Degree $d$ function with boolean inputs with small range is a junta? Let $f : \{-1,1\}^n \rightarrow \{-1,1\}$ be a boolean function which is of degree at most $d$ when expressed as a multilinear polynomial ($f(x) = \sum_S \hat{f}(S) \prod_{i \in S} x_i$). It is known that such a function is a $d2^{d-1}$-junta - i.e. $f$ depends on at most $d2^{d-1}$ variables. In fact, this should hold for any range of size $2$. Suppose the range of $f$ consisted of $m$ real numbers and $f$ were still of degree $d$. Is it known whether $f$ is a $g_m(d)$-junta for some function $g_m(d) << n$?
 A: This is a nice question.  I have to think that the answer must appear somewhere, but I'm not sure where. 
Here is, I think, a solution for $m = 3$.  I guess it could be generalized to any $m$, but possibly with a bad dependence on $m$.
By scaling and translating, we can assume $f$ takes on the three values $-1$, $+1$, and $c \in (-1, 1)$.  
Case 1: $c \in [-\frac12, \frac12]$. In this case, $f$'s range is sufficiently "discrete" that the "usual" proof for Boolean-valued $f$ should work.  I.e., things should be okay because $f$'s derivatives $D_i f$ take on largish values when they're nonzero.  I can elaborate on this case if you want.
Case 2: $\frac12 < |c| < 1$.  In this case, let $g$ be the Boolean-valued function $\mathrm{sgn}(f)$. Now $f$ is a degree-$d$ "approximating polynomial" for $g$ in the sense of Nisan--Szegedy, so $g$ itself must have degree at most $\mathrm{poly}(d)$; I forget what's best known these days, maybe $d^6$.  Now $fg$ is two-valued and of degree $O(d^6)$.  By a simple translation/scaling we can get an $h$ of degree $O(d^6)$ which is the Boolean indicator function that $f$ takes on the value $c$.  Thus by Nisan--Szegedy $h$ (and also $g$) depend on at most $\widetilde{O}(2^{d^6})$ coordinates.  I think by some simple playing around now you can conclude $f$ also depends on at most  $\widetilde{O}(2^{d^6})$ coordinates.
I wonder if it's possible to get it down to $2^{O(d)}$ coordinates.
