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.
Download file
Counter downloads: 67
- Title Fast algorithm for recovering the true solution with fixed weight of a system of linear Boolean equations with noised right-hand side
- Headline Fast algorithm for recovering the true solution with fixed weight of a system of linear Boolean equations with noised right-hand side
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
probabilistic algorithm, system of Boolean linear equations with noised right-hand side, вероятностный алгоритм. Введение, система булевых уравнений с искаженной правой частьюAuthors
References
Ширяев А. Н. Вероятность: учеб. пособие для вузов. М.: Наука, 1989. 640 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 535 с.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: пер. с англ. М.: Мир, 1980. 476 с.
GolicJ. Cryptanalysis of alleged A5 stream cipher // Advances in Cryptology. Proc. EUROCRYPT'97. Springer Verlag, 1997. P. 239-255.
Babbage S. H. Improved "exhaustive search" attacks on stream ciphers // European Convention on Security and Detection, Brighton, May 16-18, 1995. P. 161-166.
Де Брёйн Н. Г. Асимптотические методы в анализе: пер. с англ. М.: ИЛ, 1961. 247 с.
Indyk P. and Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proc. Symp. on Theory of Computing. New York, NY, USA: ACM, 1998. P. 604-613.
Dolev D., Harari Y., and 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. P. 33-42.
Greene D., Parnas M., and 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. P. 722-731.
Алексейчук А. Н., Грязнухин А. Ю. Метод восстановления систематических линейных кодов по наборам искаженных кодовых слов // Прикладная радиоэлектроника. 2013. T. 12. №2. С. 128-132.
Andoni А. and 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. P. 459-468.
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. P. 11-20.
Grigorescu E., Reysin L., and Vempala S. On noise-tolerant learning of sparse parities and related problems // Proc. 22nd Intern. Conf. of Algorithmic Learning Theory. Berlin, Heidelberg: Springer Verlag, 2011. P. 413-424.
Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике. М.: ТВП, 1997. T. 1. C. 1-18.
Fast algorithm for recovering the true solution with fixed weight of a system of linear Boolean equations with noised right-hand side | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 190