I define the gap of a polynomial $f \in Z_2[x_1, ..., x_n]$ as
$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|$.
I'm curious about the quantity $\mathbb{E}_i[|gap(f) - gap(f + x_i)|]$. I'm interested in this quantity expressed as a function of whatever properties of $f$ you find salient to its computation. Ones that would be particularly useful for me is $s$, the number of terms in the polynomial, $d$, the maximum number of variables included in a single term.