Geodesic
Solving systems of linear Boolean equations with noisy right-hand sides over the reals
Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 3-9.

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

The paper is concerned with the problem of solution of a system of linear equations with noisy right-hand side in the following setting: one knows a random $m\times N$-matrix $A$ with entries from $\{-1,1\}$ and a vector $xA+\xi\in \R^N$, where $\xi$ is the noise vector from $\R^N$, whose entries are independent realizations of a normally distributed random variable with parameters $0$ and $\sigma^2$, and $x$ is a random vector with coordinates from $\{-1,1\}$. The sought-for parameter is the vector $x$. We propose a method for constructing a set containing the sought-for vector with probability not smaller than the given one and estimate the cardinality of this set. Theoretical calculations of the parameters of the method are illustrated by experiments demonstrating the practical implementability of the method for cases when direct enumeration of all possible values of $x$ is unfeasible.
Keywords: system of linear equations with noisy right-hand side, additive Gaussian noise. 
@article{DM_2017_29_1_a0,
     author = {E. K. Alekseev and I. B. Oshkin and V. O. Popov and S. V. Smyshlyaev},
     title = {Solving systems of linear {Boolean} equations with noisy right-hand sides over the reals},
     journal = {Diskretnaya Matematika},
     pages = {3--9},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_1_a0/}
}
TY  - JOUR
AU  - E. K. Alekseev
AU  - I. B. Oshkin
AU  - V. O. Popov
AU  - S. V. Smyshlyaev
TI  - Solving systems of linear Boolean equations with noisy right-hand sides over the reals
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 3
EP  - 9
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_1_a0/
LA  - ru
ID  - DM_2017_29_1_a0
ER  - 
%0 Journal Article
%A E. K. Alekseev
%A I. B. Oshkin
%A V. O. Popov
%A S. V. Smyshlyaev
%T Solving systems of linear Boolean equations with noisy right-hand sides over the reals
%J Diskretnaya Matematika
%D 2017
%P 3-9
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2017_29_1_a0/
%G ru
%F DM_2017_29_1_a0
E. K. Alekseev; I. B. Oshkin; V. O. Popov; S. V. Smyshlyaev. Solving systems of linear Boolean equations with noisy right-hand sides over the reals. Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 3-9. http://geodesic.mathdoc.fr/item/DM_2017_29_1_a0/

[1] Lyubashevsky V., “The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem”, Lect. Notes Comput. Sci., 3624, eds. Chekuri C., Jansen K., Rolim J. D. P., Trevisan L., 2005, 378–389 | DOI | MR | Zbl

[2] Blum A., Kalai A., Wasserman H., “Noise-tolerant learning, the parity problem, and the statistical query model”, Proc. $32^{\rm nd}$ Annu. ACM Symp. Theory of Computing, eds. F. Frances Yao, Eugene M. Luks, 2000, 435–440 | MR | Zbl

[3] Balakin G. V., “Sistemy bulevykh uravnenii s iskazhennoi pravoi chastyu pri ogranicheniyakh na znacheniya neizvestnykh i oshibok”, Tr. po diskr. matem., 11, no. 1, Fizmatlit, M., 2008, 5–17

[4] Alekseichuk A. N., Gryaznukhin A. Yu., “Bystryi algoritm vosstanovleniya istinnogo resheniya fiksirovannogo vesa sistemy lineinykh bulevykh uravnenii s iskazhënnoi pravoi chastyu”, Prikl. Diskr. Matem., 2013, no. 2, 59–70 | MR

[5] Sevastyanov B. A., Kurs teorii veroyatnostei i matematicheskoi statistiki, "Nauka", M., 1982

[6] Berlekamp E., McEliece R. J., van Tilborg H. C.A., “On the inherent intractability of certain coding problems”, IEEE Trans. Inf. Theory, 24:3 (1978), 384–386 | DOI | MR | Zbl