Abstract:
It is shown that for an arbitrary Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with complexity
$L(f)\le2^{n-5}/n$ there exist four domains $D_1,D_2,D_3,D_4\subseteq\{0,1\}^n$
such that $f$ is completely specified by its values on these domains.
If $L(f)=o(2^n)$ for $i\in\{1,\dots,4\}$, then $D_i=o(2^n)$.