Representing boolean function by a polynomial Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are some interesting classes of boolean functions for which the minimal degree of $p(x)$ is known? Do we have concrete examples?
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.