Geodesic
Fast algorithm for recovering the true solution with fixed weight of a~system of linear Boolean equations with noised right-hand side
Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 59-70

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

A system of linear Boolean equations with noised right-hand side is considered. It is assumed that the true solution of the system has a predetermined weight that is independent of the number of variables in the system. A probabilistic algorithm for finding this solution is proposed. The time complexity of our algorithm is less than the time complexity of maximum likelihood method, and in contrast to the known algorithms with this property, our algorithm uses only comparisons and (bitwise and arithmetic) additions of binary integers. The proposed algorithm can be used in practice in some cases when other algorithms are less efficient.
Keywords: system of Boolean linear equations with noised right-hand side, probabilistic algorithm. 
@article{PDM_2013_2_a6,
     author = {A. N. Alekseychuk and A. Yu. Gryaznukhin},
     title = {Fast algorithm for recovering the true solution with fixed weight of a~system of linear {Boolean} equations with noised right-hand side},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {59--70},
     publisher = {mathdoc},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_2_a6/}
}
TY  - JOUR
AU  - A. N. Alekseychuk
AU  - A. Yu. Gryaznukhin
TI  - Fast algorithm for recovering the true solution with fixed weight of a~system of linear Boolean equations with noised right-hand side
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 59
EP  - 70
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_2_a6/
LA  - ru
ID  - PDM_2013_2_a6
ER  - 
%0 Journal Article
%A A. N. Alekseychuk
%A A. Yu. Gryaznukhin
%T Fast algorithm for recovering the true solution with fixed weight of a~system of linear Boolean equations with noised right-hand side
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 59-70
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_2_a6/
%G ru
%F PDM_2013_2_a6
A. N. Alekseychuk; A. Yu. Gryaznukhin. Fast algorithm for recovering the true solution with fixed weight of a~system of linear Boolean equations with noised right-hand side. Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 59-70. http://geodesic.mathdoc.fr/item/PDM_2013_2_a6/