Low Auto-Correlation Binary Sequences Explored using Warning Propagation

  • O. E. Martínez-Durive University of Havana, Havana, Cuba
  • I. S. Kotsireas Wilfrid Laurier University, Waterloo, Canada
  • R. Mulet-Genicio University of Havana, Havana, Cuba
  • A. Lage-Castellanos University of Havana, Havana, Cuba

Abstract

The search for binary sequences with low auto-correlations (LABS) is a computationally hard discrete combinatorial optimization problem. We explore two physically inspired algorithms to explore the low energy space of this model. The greedy, T = 0, Monte Carlo (MC) method gets trapped in the exponentially many 1-Spin-Flip stable configurations, that are typically low in energy, but still far from the global optimum. The more elaborated Warning Propagation (WP) algorithm also gets trapped in local minima. However, these local minima, are more stable to spin flips than the ones obtained by the greedy MC. We also compare the behavior of both algorithms in randomized versions of LABS, showing that the low energy space of the 4-Spin model is easier to explore than the one of LABS.

Published
Jul 14, 2021
How to Cite
MARTÍNEZ-DURIVE, O. E. et al. Low Auto-Correlation Binary Sequences Explored using Warning Propagation. Revista Cubana de Física, [S.l.], v. 38, n. 1, p. 25-31, july 2021. ISSN 2224-7939. Available at: <https://www.revistacubanadefisica.org/index.php/rcf/article/view/2021v38p025>. Date accessed: 19 sep. 2021.
Section
Original Articles