On the Reconstruction of a Boolean Function from Its Values on a Limited Number of Domains

The problem of recovering an arbitrary Boolean function from its values on a limited number of small-sized domains is considered. For any $n$-place Boolean function $f$, it is shown that there are $\mathcal O(n)$ domains of size $\mathcal O(n\log _2n\cdot 2L(f)\log _2L(f))$ such that $f$ is uniquely determined by its values in these domains.