Suppose $g\in \mathbb R[x_1,\dots,x_{16}]$ is a polynomial with the same vanishing set as $f$ within $\{0,1\}^{16}$. Define $h\in \mathbb R[x_1,\dots,x_{16}]$ to be the polynomial you obtain by changing every occurrence of $x_i^d$ in the monomials appearing in $g$ to $x_i$. Therefore $h$ is a multilinear polynomial with the same vanishing set as $g$ within $\{0,1\}^{16}$, and moreover $\deg (h)\le \deg(g)$.
Next we can show that any such multilinear polynomial must have degree at least $4$, implying $\deg g\geq 4$. Let's expand $$h=\sum_{S\subset \{1,\dots 16\}}c_Sx_S,$$ where $x_S=\prod_{i\in S} x_i$. You can notice that $c_{\emptyset}=0$, denote by $e_I$ the $\{0,1\}$ characteristic vector of $I$. Suppose $|I|\le 3$ and we have checked the coefficients $c_J=0$ for all $J\subset I$. Since $|I|\le 3$ we have $f(e_I)=0$ so we must also have $h(e_I)=0$. We can check that $h(e_I)=\sum_{J\subseteq I} c_Jx_J=c_I$ and conclude that $c_I=0$. This implies the desired claim.
The argument above is essentially the one used in "Covering the Cube by Affine Hyperplanes", by Alon and Furedi, to answer a question of Komjath.