Geodesic
On the Reconstruction of a~Boolean Function from Its Values on a~Limited Number of Domains
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 108-122.

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

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. 
@article{TM_2003_242_a8,
     author = {A. V. Chashkin},
     title = {On the {Reconstruction} of {a~Boolean} {Function} from {Its} {Values} on {a~Limited} {Number} of {Domains}},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {108--122},
     publisher = {mathdoc},
     volume = {242},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2003_242_a8/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On the Reconstruction of a~Boolean Function from Its Values on a~Limited Number of Domains
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2003
SP  - 108
EP  - 122
VL  - 242
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2003_242_a8/
LA  - ru
ID  - TM_2003_242_a8
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On the Reconstruction of a~Boolean Function from Its Values on a~Limited Number of Domains
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2003
%P 108-122
%V 242
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2003_242_a8/
%G ru
%F TM_2003_242_a8
A. V. Chashkin. On the Reconstruction of a~Boolean Function from Its Values on a~Limited Number of Domains. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 108-122. http://geodesic.mathdoc.fr/item/TM_2003_242_a8/

[1] Chashkin A. V., “Nizhnie otsenki slozhnosti suzhenii bulevykh funktsii”, Diskret. analiz i issled. operatsii. Ser. 1, 1997, no. 2, 75–111 | MR

[2] Chashkin A. V., “Ob odnom razlozhenii bulevykh funktsii”, Diskret. matematika, 2000, no. 3, 114–123 | MR | Zbl