ABSTRACT
The nonlinearity NL(f) of a Boolean function f is its minimal distance to affine functions.
9.1.39 Proposition [1992], [523, Section 8.4.1] For every n-variable Boolean function, we have
NL(f) = 2n−1 − 1 2
|Wf (u)|. (9.1.6)
9.1.40 Proposition [1992], [523, Section 8.4.1] Parseval’s relation implies the covering radius bound
NL(f) ≤ 2n−1 − 2n/2−1.
