Let the polynomial be in $f$ be a map from $\Bbb{Z}_2^k \to \Bbb{Z}_2$, defined by
$f = 1 + \sum_{i=1}^k x_i + \sum_{i\neq j; i,j = 1}^k x_i x_j + \dots + x_1 x_2 \cdots x_k$
Then I want to show that $f$ can be evaluated in polynomial time in $k$.
For instance. $k= 1$:
$f = 1 + x_1$
For $k = 2$:
$f = 1 + x_1( 1 + x_2)$
$k = 3$:
$f = 1 + x_3 + x_2(x_3 + 1) + x_1(x_3 + x_2(x_3 + 1) + 1) = \\ 1 + E_1 + x_1 (E_1 + 1),$
where $E_1 = x_3 + x_2(x_3 + 1)$
See Wolfram Alpha for $k= 4$ case.
$f = 1 + E_2 + x_2(E_2 + 1), \ \ \ E_2 = \dots$