Abstract:
We consider the known problem of decoding functions of Boolean algebra, that is, we need to completely restore the table of values of a function defined on an $n$-dimensional Boolean cube $B^n$ using its values on some subset of $B^n$. If the function belongs to some narrower class than the class of all functions of $n$ variables (for example, to the set of monotone or threshold functions), then only vectors of a subset of $n$-dimensional Boolean cube can be required to completely determine the function. In the paper, we consider the class of functions which split the $n$-dimensional Boolean cube into cube faces. An asymptotic estimate for complexity of decoding functions that belong to any subclass of this class with fixed structure is obtained.
Fulltext:
PDF file (211 kB)