Representing boolean function by a polynomial
Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$
then the unique multilinear expansion of $f$ contains the monomial $x_1\cdots x_n$. Indeed, since $(-1)^{x_i} = \frac{1-x_i}{2}$, the Fourier expansion of $f$ (expressed in terms of products of $\frac{1-x_i}{2}$) will contain the term $\prod_i \frac{1-x_i}{2}$, and the corresponding monomial $\prod_i x_i$ doesn't appear in any other term.

Nisan and Szegedy proved that functions of degree $d$ depend on at most $d2^d$ variables. For $d = 1$ we can be more exact: the function must depend on at most one coordinate.