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/

[1] Balakin G. V., “Vvedenie v teoriyu sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 1–18 | MR | Zbl

[2] Grigorescu E., Reysin L., Vempala S., “On noise-tolerant learning of sparse parities and related problems”, Proc. 22nd Intern. Conf. of Algorithmic Learning Theory, Springer Verlag, Berlin–Heidelberg, 2011, 413–424 | DOI | Zbl

[3] Valiant G., “Finding correlations in subquadratic time, with applications to learning parities and juntas”, Proc. 53rd Annual IEEE Symp. on the Foundations of Computer Science (New Brunswick, New Jersey, October 2–23, 2012), 11–20 | Zbl

[4] Andoni A., Indyk P., “Near-optimal hashing algorithms for approximate nearest neighbor in high dimension”, Proc. 47th Symp. on Foundations of Computer Science (Berkeley, California, October 21–24, 2006), 459–468

[5] Alekseichuk A. N., Gryaznukhin A. Yu., “Metod vosstanovleniya sistematicheskikh lineinykh kodov po naboram iskazhennykh kodovykh slov”, Prikladnaya radioelektronika, 12:2 (2013), 128–132

[6] Greene D., Parnas M., Yao F., “Multi-index hashing for information retrieval”, Proc. 35th Annual IEEE Symp. on the Foundations of Computer Science (Santa Fe, New Mexico, November 20–22, 1994), 722–731

[7] Dolev D., Harari Y., Parnas M., “Finding the neighborhood of a query in a dictionary”, Proc. 2nd Israel Symp. on Theory and Computing Systems (Natanya, Israel, June 7–9, 1993), 33–42

[8] Indyk P., Motwani R., “Approximate nearest neighbors: towards removing the curse of dimensionality”, Proc. Symp. on Theory of Computing, ACM, New York, NY, USA, 1998, 604–613 | MR | Zbl

[9] De Brëin N. G., Asimptoticheskie metody v analize, per. s angl., IL, M., 1961, 247 pp.

[10] Babbage S. H., “Improved “exhaustive search” attacks on stream ciphers”, European Convention on Security and Detection (Brighton, May 16–18, 1995), 161–166

[11] Golić J., “Cryptanalysis of alleged A5 stream cipher”, Advances in Cryptology, Proc. EUROCRYPT' 97, Springer Verlag, 1997, 239–255 | MR

[12] Reingold E., Nivergelt Yu., Deo N., Kombinatornye algoritmy. Teoriya i praktika, per. s angl., Mir, M., 1980, 476 pp. | MR | Zbl

[13] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, per. s angl., Mir, M., 1979, 535 pp. | MR

[14] Shiryaev A. N., Veroyatnost, Ucheb. posobie dlya vuzov, Nauka, M., 1989, 640 pp. | MR