On Boolean functions with a certain number of zeros Given boolean $f(\Bbb x)$, with $\Bbb x\in\{0,1\}^n$, what are good upper/lower bounds, in terms of $|f^{-1}(0)|$, for minimum $deg(p(\Bbb x))$ of a real polynomial satisfying $p(\Bbb x)=f(\Bbb x)$?
One relevant result is that if $\deg f = d$ then $2^d\hat{f}(S)$ is an integer for all $S$ (see for example exercise 12(b) here). In particular, $2^d\hat{f}(\emptyset) = 2^{d-n}|f^{-1}(1)|$ is an integer, and so $|f^{-1}(0)|$ is a multiple of $2^{n-d}$. This gives a lower bound on $d$ given $|f^{-1}(0)|$, which is tight for an AND of $d$ variables.

In terms of corresponding upper bounds you can't expect much, since there are balanced functions of maximal degree (parity for example). Moreover, there are functions with $|f^{-1}(0)| = 2^{n-k}$ of maximal degree for all $1 \leq k \leq n$, for example parity on $n-k+1$ variables ORed with $k-1$ variables; you can probably be a bit more cunning and construct a function of maximal degree for any given $0 &lt; |f^{-1}(0)| &lt; 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.