zbMATH — the first resource for mathematics

On the complexity of decoding Boolean cube splitting into cube faces. (English. Russian original) Zbl 1192.68230
Discrete Math. Appl. 18, No. 2, 155-172 (2008); translation from Diskretn. Mat. 20, No. 2, 46-62 (2008).
Summary: 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.

68P20 Information storage and retrieval of data
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Full Text: DOI
[1] Deerwester S., J. Amer. Soc. Information Sci. 41 pp 391– (1990)
[2] Papadimitriou C. H., J. Comput. Syst. Sci. 61 pp 217– (2000) · Zbl 0963.68063
[3] Korobkov V. K., Probl. Cybern. 13 pp 5– (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.