Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them

Search for binary sequences with a high figure of merit, also known as the low autocorrelation binary sequence (labs) problem, represents a formidable computational challenge. By 2002, a branch-and-bound solver presented optimal solutions for even and odd sequences up to length L = 60 and reported computational complexity of O(1.85 L ). In 2003, two stochastic solvers replicated these solutions, reaching the same figures of merit, and reported computational complexity of O(1.423 L ) and O(1.370 L ), refined to O(1.5097 L ) and O(1.4072 L ) for L odd in this paper. New experiments, with the solver from 2009 and also reported in this paper, demonstrate (a) the average-case asymptotic performance of 114.515 1.3464 L for even-only values, and (b) the average-case asymptotic performance of 320.360 1.3421 L for odd-only values. To mitigate the computational constraints of the labs problem, we consider solvers that accept odd values of L and return solutions for skew-symmetric binary sequences only ‐ with the consequence that not all best solutions under this constraint will also be optimal for each value of L. Specifically, we have instrumented three such solvers for extensive average-case asymptotic performance experiments. Two solvers are based on the version from 2009; both dier only in one respect: the 2009 solver uses an evolutionary algorithm to initialize the tabu search, the modified solver initializes the tabu search with a random binary sequence. What has not been expected is that the asymptotic average-case performance of the first and the second solver are statistically equivalent: for the range 71 <= L <= 127 we observe 150.49 1.1646 L for the memetic-tabu version versus 156.34 1.1646 L for the random-tabu version. Thus, for the labs problem, the evolutionary component of this solver is not eective. Our solver relies on a single contiguous self-avoiding walk until memory constraints induce random restarts. Under random restarts, the solver reaches the target value with a number of independent contiguous self-avoiding walk segments. Under the fixed walk segment compromise and random restarts, we observe 650.07 1.1435 L for the range 71 L 127. We show that the solver with the best average-case asymptotic performance has the best chance of finding new solutions that significantly improve, as L increases, figures of merit reported to date.