Trudy Matematicheskogo Instituta imeni V.A. Steklova, Mathematical logic and algebra, Tome 242 (2003), pp. 108-122
Citer cet article
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/
@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},
year = {2003},
volume = {242},
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
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
%U http://geodesic.mathdoc.fr/item/TM_2003_242_a8/
%G ru
%F TM_2003_242_a8
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.
