Geodesic
On the complexity of decoding Boolean cube splitting into cube faces
Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 46-62 
V. V. Osokin. On the complexity of decoding Boolean cube splitting into cube faces. Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 46-62. http://geodesic.mathdoc.fr/item/DM_2008_20_2_a4/
@article{DM_2008_20_2_a4,
     author = {V. V. Osokin},
     title = {On the complexity of decoding {Boolean} cube splitting into cube faces},
     journal = {Diskretnaya Matematika},
     pages = {46--62},
     year = {2008},
     volume = {20},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_2_a4/}
}
TY  - JOUR
AU  - V. V. Osokin
TI  - On the complexity of decoding Boolean cube splitting into cube faces
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 46
EP  - 62
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_2_a4/
LA  - ru
ID  - DM_2008_20_2_a4
ER  - 
%0 Journal Article
%A V. V. Osokin
%T On the complexity of decoding Boolean cube splitting into cube faces
%J Diskretnaya Matematika
%D 2008
%P 46-62
%V 20
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2008_20_2_a4/
%G ru
%F DM_2008_20_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Baeza-Yates R., Ribeiro-Neto B., Modern information retrieval, Addison–Wesley, Boston, 1999

[2] Deerwester S., Dumais S. T., Furnas G. W., Landauer T. K., Harshman R., “Indexing by latent semantic analysis”, J. Amer. Soc. Information Sci., 41:6 (1990), 391–407 | 3.0.CO;2-9 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[3] Hofmann T., “Probabilistic latent semantic indexing”, Proc. SIGIR' 99, Berkeley, 1999, 55–57

[4] Gasanov E. E., Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, Fizmatlit, Moskva, 2002 | Zbl

[5] Papadimitriou C. H., Raghavan P., Tamaki H., Vempala S., “Latent semantic indexing: A probabilistic analysis”, J. Comput. Syst. Sci., 61:2 (2000), 217–235 | DOI | MR | Zbl

[6] Korobkov V. K., “O monotonnykh funktsiyakh algebry logiki”, Problemy kibernetiki, 13 (1965), 5–28 | MR | Zbl