Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

# Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem
Source: [https://arxiv.org/html/2607.09688](https://arxiv.org/html/2607.09688)
[![[Uncaptioned image]](https://arxiv.org/html/2607.09688v1/x1.png)Blaž Pšeničnik](https://orcid.org/0009-0000-1598-8056) Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor blaz\.psenicnik1@um\.si &[![[Uncaptioned image]](https://arxiv.org/html/2607.09688v1/x2.png)Borko Bošković](https://orcid.org/0000-0002-7595-2845) Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor borko\.boskovic@um\.si &[![[Uncaptioned image]](https://arxiv.org/html/2607.09688v1/x3.png)Jan Popič](https://orcid.org/0000-0002-7156-7050) Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor jan\.popic1@um\.si &[![[Uncaptioned image]](https://arxiv.org/html/2607.09688v1/x4.png)Janez Brest](https://orcid.org/0000-0001-5864-3533) Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor janez\.brest@um\.si

###### Abstract

Low autocorrelation binary sequences problem \(LABS\) is a hard combinatorial optimization challenge with important applications in communications, signal processing, and satellite navigation\. This paper proposes a hybrid search framework that combines Thompson sampling with parallel self\-avoiding walks to adaptively allocate computational effort across restriction classes of the LABS search space\. By modeling partitions as arms in a multi\-armed bandit setting, the proposed method dynamically shifts search resources toward partitions that empirically produce higher merit factors while maintaining exploration of less\-sampled regions\. The approach is further accelerated through GPU\-parallel execution, shared posterior updates, efficient neighborhood evaluation, and a Bloom filter for cycle prevention\. In addition, we use a two\-stage optimization strategy that first searches constrained partitioned skew\-symmetric spaces and then refines the best candidates in the unrestricted space\. Experiments on long binary sequences show that the proposed method improves the previously best\-known results for 35 sequence lengths in the range450≤L≤527450\\leq L\\leq 527and forL=573L=573\. In particular, we report a new longest sequence with merit factor exceeding8\.08\.0, obtained forL=451L=451\. The results also show that Thompson sampling effectively prioritizes partitions with better observed performance, confirming the value of online, data\-driven resource allocation in LABS optimization\. Overall, the proposed framework provides a scalable and effective strategy for high\-performance merit factor maximization\.

*K*eywordsLABS, merit factor, reinforcement learning, Thompson sampling

## Introduction

The study of low autocorrelation binary sequences \(LABS\) is recognized as a highly challenging computational problem, belonging to the class of hard binary combinatorial problems\. It was formally introduced in 1972 by Golay\[[20](https://arxiv.org/html/2607.09688#bib.bib14)\]\. Earlier groundwork was laid by Littlewood\[[30](https://arxiv.org/html/2607.09688#bib.bib15)\], a mathematician, who examined polynomials with coefficients restricted to±1\\pm 1on the unit circle in the complex plane, a problem closely related to LABS\. Sequences with low autocorrelation are valuable across a range of practical contexts\. In digital communications, they help distinguish signals from background noise more effectively\[[26](https://arxiv.org/html/2607.09688#bib.bib16),[28](https://arxiv.org/html/2607.09688#bib.bib18)\]and are critical for packet detection and bit alignment\[[43](https://arxiv.org/html/2607.09688#bib.bib53)\], especially for low‑power Internet of Things receivers\. Beyond that, their usefulness extends to areas such as physics\[[4](https://arxiv.org/html/2607.09688#bib.bib17)\], chemistry, and cryptography\. A broader overview of additional applications and theoretical developments can be found in the survey literature on this topic\[[26](https://arxiv.org/html/2607.09688#bib.bib16)\]\. A particularly striking application involved their role in highly accurate interplanetary radar experiments designed to test the curvature of space\-time\[[41](https://arxiv.org/html/2607.09688#bib.bib19)\]\. In global navigation satellite systems \(GNSS\), sequences with low autocorrelation play a crucial role; when combined with additional desirable properties, they are known as spreading codes\[[47](https://arxiv.org/html/2607.09688#bib.bib20)\]\. For example, theGlobal Positioning System L1 C/A signaluses a set of6363distinct spreading codes, each of length10231023\[[47](https://arxiv.org/html/2607.09688#bib.bib20)\]\. These types of codes are also important in low Earth orbit \(LEO\) satellite applications\[[48](https://arxiv.org/html/2607.09688#bib.bib21)\]\. In recent years, interest in this problem has grown further with the emergence of quantum computing, as such combinatorial optimization challenges are seen as promising candidates for quantum algorithms\[[40](https://arxiv.org/html/2607.09688#bib.bib22),[42](https://arxiv.org/html/2607.09688#bib.bib24)\]\.

In the literature, binary sequences are commonly analyzed using two forms of autocorrelation: periodic and aperiodic autocorrelation functions\[[39](https://arxiv.org/html/2607.09688#bib.bib26)\]\. The aperiodic autocorrelation is often regarded as a more realistic characterization of sequence behavior in practical systems\[[29](https://arxiv.org/html/2607.09688#bib.bib25)\]\. A binary sequence of lengthLLis defined asS​\(L\)=\{s1,s2,…,sL\}S\(L\)=\\\{s\_\{1\},s\_\{2\},\\ldots,s\_\{L\}\\\}, where element satisfiessi∈\{\+1,−1\}s\_\{i\}\\in\\\{\+1,\-1\\\}\. The aperiodic autocorrelation function is given by:

Ck​\(S\)=∑i=1L−ksi​si\+k,k∈\{1,…,L\}\.C\_\{k\}\(S\)=\\sum\_\{i=1\}^\{L\-k\}s\_\{i\}s\_\{i\+k\},\\quad k\\in\\\{1,\\dots,L\\\}\.\(1\)
The sequence energy is defined asE​\(S\)=∑k=1L−1Ck2​\(S\)E\(S\)=\\sum\_\{k=1\}^\{L\-1\}C\_\{k\}^\{2\}\(S\), i\.e\., the sum of squared aperiodic autocorrelation values over all non\-zero shiftskk\. Sequence search and design methods in the literature typically follow two principal optimization criteria\. The first aims to minimize the peak sidelobe level \(PSL\), while the second seeks to maximize the merit factor \(FF\)\[[32](https://arxiv.org/html/2607.09688#bib.bib27)\], defined as:

F​\(S\)=L22​E​\(S\)\.F\(S\)=\\frac\{L^\{2\}\}\{2E\(S\)\}\.\(2\)These two objectives constitute a trade\-off, making their simultaneous optimization generally infeasible\. Accordingly, practical sequence design does not attempt to balance PSL and MF; instead, it focuses on optimizing either PSL orFF, depending on the application and design requirements\[[11](https://arxiv.org/html/2607.09688#bib.bib28)\]\. The goal of the LABS problem is to identify a binary sequenceS∗S^\{\*\}that, for a given lengthLL, achieves the maximum possible merit factorFF:

S∗=arg​maxS∈\{−1,1\}L​F​\(S\)\.S^\{\*\}=\\underset\{S\\in\\\{\-1,1\\\}^\{L\}\}\{\\operatorname\{arg\\max\}\}F\(S\)\.\(3\)In other words, the objective is to find a sequence that maximizes the merit factor defined in Equation \([2](https://arxiv.org/html/2607.09688#Sx1.E2)\), thereby minimizing the associated autocorrelation energy\.

Since LABS is a binary combinatorial optimization problem, the size of the search space grows exponentially with the sequence lengthLL, specifically as2L2^\{L\}\. The landscape is characterized by an exponentially increasing number of local minima asLLincreases, while the global minima are extremely rare, highly isolated, and sharply defined, resembling the shape of a golf hole\[[14](https://arxiv.org/html/2607.09688#bib.bib30)\]\. Figure[1](https://arxiv.org/html/2607.09688#Sx1.F1)illustrates the distribution of global and local optima using a two\-dimensional projection of the search space\. This projection is obtained via UMAP \(Uniform Manifold Approximation and Projection\)\[[22](https://arxiv.org/html/2607.09688#bib.bib29)\], a dimensionality reduction technique, for sequence lengthsL=12,15,17L=12,\\,15,\\,17\. The valuesCk​\(S\)C\_\{k\}\(S\)in Equation[1](https://arxiv.org/html/2607.09688#Sx1.E1)remain unchanged if the sign of each sequence element is flipped \(i\.e\., multiplied by−1\-1\) or if the sequence is reversed\. Under these transformations, the sequence energy remains invariant\[[33](https://arxiv.org/html/2607.09688#bib.bib31)\]\. If alternating elements of the sequence are complemented, correlations with odd indiceskkremain unchanged, while correlations with even indices only change sign\. Hence, all sequences of lengthLLcan be can be grouped into eight mutually equivalent classes\. Consequently, the number of nonequivalent sequences is slightly greater than2\(L−3\)2^\{\(L\-3\)\}\[[33](https://arxiv.org/html/2607.09688#bib.bib31)\]\. In Figure[1](https://arxiv.org/html/2607.09688#Sx1.F1), these symmetry classes are visible as distinct clusters for each sequence length\.

![Refer to caption](https://arxiv.org/html/2607.09688v1/x5.png)Figure 1:Two\-dimensional projection of the search space for sequence lengthsL=12,15,17L=12,\\,15,\\,17using the dimensionality reduction method UMAP\[[22](https://arxiv.org/html/2607.09688#bib.bib29)\]\. Red points represent global minima, green points represent local minima, and blue points correspond to all other sequences\.Due to the exponential growth of the problem’s search space, its reduction can be highly advantageous\. A binary sequence of odd lengthL=2​k\+1L=2k\+1is called skew\-symmetric\[[20](https://arxiv.org/html/2607.09688#bib.bib14)\]if it satisfies the following condition:

s\(k\+1\)\+i=\(−1\)i​s\(k\+1\)−i,i=1,2,⋯,k\.s\_\{\(k\+1\)\+i\}=\(\-1\)^\{i\}s\_\{\(k\+1\)\-i\},\\quad i=1,2,\\,\\cdots,k\.\(4\)This constraint effectively reduces the search space to2\(\(L\+1\)/2\)2^\{\(\(L\+1\)/2\)\}and ensures that all sidelobes corresponding to odd shifts vanish, i\.e\.,Ck=0C\_\{k\}=0for all oddkk\. As a consequence, the total energyEEis reduced, which in turn increases the merit factorFF\. For sequence lengthsL≤66L\\leq 66, only2222optimal sequencesS∗S^\{\*\}are also skew\-symmetric\[[33](https://arxiv.org/html/2607.09688#bib.bib31)\]\.

Since exhaustive search becomes computationally intractable for large values ofLL, restriction classes have been introduced\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]\. This approach enables a decomposition of the search space into multiple disjoint regions, which can then be explored in parallel\. The search space can in turn be reduced to2\(L/2−p\)2^\{\(L/2\-p\)\}by fixing the firstppelements of the sequence\. The firstppelements are determined using partitions \(restriction classes\)\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]of lengthgg\(number of summands\) with minimal or normalized potentials\. The nextk−p\+1k\-p\+1elements are free, while the lastkkelements are determined using a skew\-symmetry rule, as shown in Equation[5](https://arxiv.org/html/2607.09688#Sx1.E5)\. This effectively assigns some elements in the autocorrelation function to small values, thereby reducing the total energy\. To order the partitions, the authors in\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]suggested potentials and normalized potentials for each partition\. This reduction of the search space, based on group theory, provides a more efficient approach for finding sequences with desired properties compared to considering all possible restriction classes\.

S​\(L\)=s1​s2​⋯​sp⏟p​sp\+1​sp\+2​⋯​sk−1​sk​sk\+1⏟k−p\+1​sk\+2​sk\+3​⋯​sL−1​sL⏟kS\(L\)=\\underbrace\{s\_\{1\}s\_\{2\}\\cdots s\_\{p\}\}\_\{p\}\\underbrace\{s\_\{p\+1\}s\_\{p\+2\}\\cdots s\_\{k\-1\}s\_\{k\}s\_\{k\+1\}\}\_\{k\-p\+1\}\\underbrace\{s\_\{k\+2\}s\_\{k\+3\}\\cdots s\_\{L\-1\}s\_\{L\}\}\_\{k\}\(5\)
In this work, we address the challenge of efficiently exploring the exponentially large search space of binary sequences in the LABS problem while maintaining a strong balance between exploration and exploitation\. We propose a hybrid framework that combines Thompson sampling–based online decision making with parallel self\-avoiding walks to dynamically allocate computational resources across restriction classes\. Each restriction class is treated as an arm in a multi\-armed bandit setting, enabling adaptive focus toward regions of the search space that empirically yield higher merit factors, while still preserving sufficient exploration of under\-sampled partitions\. The resulting search procedure is further accelerated through GPU\-parallel execution of independent walks, shared global posterior updates, and efficient neighborhood evaluation with linear\-time flip operations and a Bloom filter for cycle prevention\. In addition, we incorporate a two\-stage optimization strategy that first explores constrained partitioned symmetric search spaces and subsequently refines high\-quality candidates in an unconstrained setting, improving solution quality\. Together, these components form a scalable and data\-driven search strategy that leverages stochastic decision\-making and high\-performance parallel computation to significantly enhance the effectiveness of merit factor maximization\.

Accordingly, the main contributions of this paper are as follows:

- •We propose an online method for prioritizing regions of the search space in the low autocorrelation binary sequence problem, in which computational effort is dynamically allocated during the search process\.
- •We develop a novel algorithm that incorporates the proposed prioritization strategy\.
- •We report new best\-known solutions for several sequence lengths\.
- •We present the longest binary sequence with a merit factor exceeding8\.08\.0\.

The remainder of this paper is organized as follows\. We begin with a review of related work and background on low autocorrelation binary sequences\. This is followed by the presentation of the proposed method for prioritizing regions of the search space and the corresponding algorithm\. We then report the experimental results, including improved best\-known solutions and a newly obtained sequence with a merit factor exceeding8\.08\.0\. The paper concludes with a summary of findings and directions for future research\.

## Related work

Finding optimal sequencesS∗S^\{\*\}is computationally feasible only for shorter lengths; nevertheless, several methods have been proposed in literature\. In\[[31](https://arxiv.org/html/2607.09688#bib.bib32)\], the authors introduced a branch\-and\-bound algorithm that systematically explores the solution space\. To reduce its size, they fixed themmleftmost and rightmost elements based on symmetry rules\. The lower bound of the energy function was obtained via relaxation, accounting for interactions between fixed and free elements\. This approach enabled the computation of optimal sequences up toL≤44L\\leq 44, with an estimated time complexity ofO​\(1\.85L\)O\(1\.85^\{L\}\)\. The quality of the lower bound in\[[31](https://arxiv.org/html/2607.09688#bib.bib32)\]depends on random assignments of the centralL−2​mL\-2mfree elements\. To address this,\[[36](https://arxiv.org/html/2607.09688#bib.bib34)\]introduced the concept of free products, where terms are considered only if both elements are unfixed\. This idea was refined in\[[35](https://arxiv.org/html/2607.09688#bib.bib35)\]by incorporating additional interactions between fixed and free elements, reducing the complexity toO​\(1\.80L\)O\(1\.80^\{L\}\)\. In\[[46](https://arxiv.org/html/2607.09688#bib.bib36)\], it was observed that conjugating a sequence element changes the energy sum by±4\\pm 4, leading to a tighter lower bound\. Finally,\[[33](https://arxiv.org/html/2607.09688#bib.bib31)\]introduced a combined lower bound that further improved efficiency toO​\(1\.729L\)O\(1\.729^\{L\}\)\. An exact lower bound was also derived; however, it was not used in practice due to its high computational cost\. Using this method, optimal sequences were obtained up toL≤66L\\leq 66, with an estimated runtime of approximately5555days on a248248\-core system forL=66L=66\. Additionally, optimal skew\-symmetric sequences were reported for lengths up toL≤119L\\leq 119\.

As an alternative, construction methods can be used to efficiently generate sequences of a given quality\. In\[[24](https://arxiv.org/html/2607.09688#bib.bib38)\], it was shown that the merit factor of any rotated Legendre sequence satisfies1\.5≤F≤6\.01\.5\\leq F\\leq 6\.0, attaining its maximum when the rotation parameter is approximatelyr≈14r\\approx\\frac\{1\}\{4\}\. A Legendre sequence, defined for prime lengthLL, whose elements are given by the Legendre symbol and take values±1\\pm 1depending on quadratic residuosity \(cf\. quadratic residue modulo\)\[[6](https://arxiv.org/html/2607.09688#bib.bib37)\]\. Furthermore,\[[6](https://arxiv.org/html/2607.09688#bib.bib37)\]demonstrated that sequences of arbitrary length withF≥6\.0F\\geq 6\.0can be systematically constructed\. Specifically, by appending⌊t^​L⌋\\lfloor\{\\hat\{t\}L\}\\rfloorelements of a rotated Legendre sequence to the end, and tuning parameters within0\.20≤r≤0\.240\.20\\leq r\\leq 0\.24and0\.055≤t^≤0\.0630\.055\\leq\\hat\{t\}\\leq 0\.063, one can achieve sequences with merit factorF≈6\.3421F\\approx 6\.3421\. Further improvements using the steep descent algorithm and modified Jacobi sequences increased the merit factor to approximatelyF≈6\.44F\\approx 6\.44\[[3](https://arxiv.org/html/2607.09688#bib.bib39)\]\. A survey in\[[25](https://arxiv.org/html/2607.09688#bib.bib40)\]unified these results and identified sequence classes with asymptotic merit factors above6\.346\.34\.

Despite these advances in construction methods, there remains a significant gap between asymptotic guarantees and best\-known computationally obtained merit factors\. The literature employed several stochastic approaches, including local search\[[18](https://arxiv.org/html/2607.09688#bib.bib41),[16](https://arxiv.org/html/2607.09688#bib.bib12)\], tabu search\[[21](https://arxiv.org/html/2607.09688#bib.bib42)\], a combination of evolutionary algorithms with tabu search\[[19](https://arxiv.org/html/2607.09688#bib.bib43)\], self\-avoiding walks\[[7](https://arxiv.org/html/2607.09688#bib.bib44),[8](https://arxiv.org/html/2607.09688#bib.bib6)\], and search control using a priority queue\[[9](https://arxiv.org/html/2607.09688#bib.bib45),[10](https://arxiv.org/html/2607.09688#bib.bib46)\], among others\. Local search methods in\[[7](https://arxiv.org/html/2607.09688#bib.bib44),[15](https://arxiv.org/html/2607.09688#bib.bib4)\]have produced sequences with a merit factor exceeding8\.08\.0for172≤L≤268172\\leq L\\leq 268, and exceeding7\.07\.0for172≤L≤527172\\leq L\\leq 527\. In\[[10](https://arxiv.org/html/2607.09688#bib.bib46)\], all skew\-symmetric sequences with lengths in the interval201≤L≤303201\\leq L\\leq 303achieving a merit factor of at leastF≥8\.0F\\geq 8\.0were reported\. Because exhaustive search becomes intractable for large values ofLL, the authors in\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]introduced restriction classes, which allowed the search space to be divided into disjoint regions that can be explored in parallel\. Analysis of a stochastic algorithm on short sequences enables the establishment of a predictive model for stopping conditions\[[23](https://arxiv.org/html/2607.09688#bib.bib47)\]\. Using this and parallel computation on graphics processing units\[[8](https://arxiv.org/html/2607.09688#bib.bib6)\], the stochastic algorithm found some optimal skew\-symmetric sequences with an estimated probability of99%99\\%for171≤L≤223171\\leq L\\leq 223, and skew\-symmetric sequences with a merit factor greater than9\.09\.0for lengths225≤L≤247225\\leq L\\leq 247\.

Using noiseless simulations with up to 40 qubits, the authors in\[[42](https://arxiv.org/html/2607.09688#bib.bib24)\]show that the quantum approximate optimization algorithm \(QAOA\) with fixed parameters achieves a time\-to\-solution scaling ofO​\(1\.46L\)O\(1\.46^\{L\}\)on the problem, which improves toO​\(1\.21L\)O\(1\.21^\{L\}\)when combined with quantum minimum finding, outperforming the best classical heuristic\. These results provide evidence that QAOA can serve as a useful algorithmic component for achieving quantum speedups in optimization problems in a fault\-tolerant setting\. In\[[40](https://arxiv.org/html/2607.09688#bib.bib22)\], the authors extend the Pauli Correlation Encoding \(PCE\) framework to the LABS problem\. Their variational quantum solver achieves a time\-to\-solution scaling of approximatelyO​\(1\.33L\)O\(1\.33^\{L\}\), and they project that quantum advantage could appear for instance sizes on the order of thousands\.

In\[[50](https://arxiv.org/html/2607.09688#bib.bib48)\], GPU parallelization was shown to significantly speed up discrete optimization problems like LABS and the Golomb ruler, achieving about a13×13\\timesspeedup using steepest descent local search for sequences of lengthL=201L=201\. In\[[34](https://arxiv.org/html/2607.09688#bib.bib49)\], a hybrid memetic evolutionary multi\-agent system \(EMAS\) uses GPUs to accelerate fitness evaluation, reaching a46×46\\timesspeedup forL=128L=128compared to CPU\-only execution\. The authors in\[[51](https://arxiv.org/html/2607.09688#bib.bib50)\]used a deep neural network as a tabu support\. They replaced the heuristic selection of the tabu parameter with an LSTM neural network that predicts values of the parameter for a given input sequence and its energy\. In\[[49](https://arxiv.org/html/2607.09688#bib.bib23)\]a framework for the massive parallelization of the memetic algorithm with tabu search was presented\. In\[[12](https://arxiv.org/html/2607.09688#bib.bib51)\], a quantum\-enhanced memetic tabu search achieved the scaling ofO​\(1\.24L\)O\(1\.24^\{L\}\)\. In\[[8](https://arxiv.org/html/2607.09688#bib.bib6)\], the authors presented a new stochastic algorithm for LABS, which organizes the search process as a series of parallel self\-avoiding walks over sequences with skew\-symmetry\. The algorithm achieved a387387\-fold speedup compared to a sequential program, since the individual self\-avoiding walks are trivially parallelizable\. The algorithm achieved a time complexity ofO​\(1\.34L\)O\(1\.34^\{L\}\)andO​\(1\.15L\)O\(1\.15^\{L\}\)for skew\-symmetric sequences\. In\[[37](https://arxiv.org/html/2607.09688#bib.bib10)\], the solver was improved to use partitions \(restriction classes\) and a two\-step targeted refinement strategy was suggested to explore the whole unrestricted search space and mitigate constraints imposed by skew\-symmetry and restriction classes\.

## Method

Achieving high merit factors for long binary sequences requires careful selection of integer partitions, as exhaustively optimizing sequences for all partitions for a given lengthppis computationally infeasible\. Until now, potentials and normalized potentials of partitions have been used as heuristic methods to rank partitions\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\], enabling the prioritization of promising regions of the search space\. In this paper, we propose a novel method for dynamic allocation of search effort, which is modeled as an online decision problem\. The proposed method dynamically allocates computational resources to partitions based on their observed performance, enabling efficient exploration and exploitation of the search space\.

An online decision problem is a setting where a decision\-maker \(often called an agent\) must make decisions sequentially over time without knowing future inputs\. The agent only sees information available at the current time step and must act immediately\. This process happens over discrete time stampst=1,2,3,…,Tt=1,2,3,\\dots,T, where at each time step an action is chosen based on past and current observations\. After taking an actionata\_\{t\}, the agent receives a rewardrtr\_\{t\}\. The effectiveness of online decision\-making algorithms is commonly evaluated and compared using regret plots\. The regret incurred at timettis defined as the difference between the expected reward of the optimal action and the expected reward of the action chosen by the algorithm\[[38](https://arxiv.org/html/2607.09688#bib.bib3)\]\. The objective is therefore to minimize cumulative regret over time\.

We model the partition resource allocation problem as a multi\-armed bandit problem\[[27](https://arxiv.org/html/2607.09688#bib.bib5)\], where each partition corresponds to an arm\. At each decision step, the algorithm selects partitions and allocates computational resources to them\. Feedback is then received in the form of the best merit factor achieved after partitioning the sequence and performing a self\-avoiding walk\[[8](https://arxiv.org/html/2607.09688#bib.bib6)\]on the partitioned sequence\. Since we can only obtain an optimized merit factor of a partitioned sequence after performing the walk \(and spending computation time\), and because its value is random due to the stochastic nature of the search process, this problem involves a balance between exploration and exploitation\. The goal is therefore to allocate resources to partitions, that are likely to yield high merit factors, while still exploring less\-sampled partitions to avoid prematurely discarding potentially promising regions of the search space\. To address this trade\-off, we employ Thompson sampling\[[44](https://arxiv.org/html/2607.09688#bib.bib1),[45](https://arxiv.org/html/2607.09688#bib.bib2)\], which was chosen due to the low computational overhead compared to other reinforcement learning methods and strong empirical performance\[[1](https://arxiv.org/html/2607.09688#bib.bib8),[13](https://arxiv.org/html/2607.09688#bib.bib7)\]\.

Formally, letKKbe the number of available partitions for a given sequence length\. Each armk∈\{1,2,…,K\}k\\in\\\{1,2,\\ldots,K\\\}corresponds to a partition and is associated with an unknown parameterθk\\theta\_\{k\}, representing the expected merit factorFFobtainable from that partition\. We place a prior distributionp​\(θk\)p\(\\theta\_\{k\}\)over eachθk\\theta\_\{k\}to encode our initial belief about the quality of partitionkk\. A common choice for a prior distribution is the Beta distribution:

θk∼B​e​t​a​\(αk,βk\),\\theta\_\{k\}\\sim Beta\(\\alpha\_\{k\},\\beta\_\{k\}\),\(6\)as it provides a convenient conjugate prior for bounded rewards in\[0,1\]\[0,1\]and enables efficient posterior updates\. Here,αk\\alpha\_\{k\}andβk\\beta\_\{k\}correspond to the number of observed successes and failures, respectively, in a Bernoulli bandit framework\. We initialize all arms withαk=1\\alpha\_\{k\}=1andβk=1\\beta\_\{k\}=1, corresponding to a uniform prior\.

However, since the merit factorFFis a continuous quantity, the rewardrtr\_\{t\}at timettcannot be effectively treated as a binary outcome\. To address this, we employ an extension of Thompson sampling, proposed in\[[2](https://arxiv.org/html/2607.09688#bib.bib9)\], which accommodates general reward distributions and thus enables modeling the full stochastic bandit problem\. Specifically, for a rewardrt∈\[0,1\]r\_\{t\}\\in\[0,1\], one can simulate a Bernoulli trial with success probabilityrtr\_\{t\}to map the reward to a binary outcome\. An alternative, more direct approach allows updates with the actual reward valuert∈\[0,1\]r\_\{t\}\\in\[0,1\]without performing a Bernoulli trial\. This method, while not analyzed due to limitations\[[2](https://arxiv.org/html/2607.09688#bib.bib9)\], is adopted here for efficiency\. Under Fractional Thompson sampling, the parameters for armkkare updated as:

\(αk,βk\)←\{\(αk,βk\),if​at≠k\(αk,βk\)\+\(rt,1−rt\),if​at=k\(\\alpha\_\{k\},\\beta\_\{k\}\)\\leftarrow\\begin\{cases\}\(\\alpha\_\{k\},\\beta\_\{k\}\),&\\text\{if \}a\_\{t\}\\neq k\\\\ \(\\alpha\_\{k\},\\beta\_\{k\}\)\+\(r\_\{t\},1\-r\_\{t\}\),&\\text\{if \}a\_\{t\}=k\\end\{cases\}\(7\)Using fractional updates avoids the inefficiency of simulating Bernoulli trials for continuous rewards while preserving the core advantages of Thompson sampling\. We scale the observed merit factor tort∈\[0,1\]r\_\{t\}\\in\[0,1\]for compatibility with the bandit framework, using the formulart=c​l​a​m​p​\(F/7\)r\_\{t\}=clamp\(F/7\)based on the expected range of merit factors\[[37](https://arxiv.org/html/2607.09688#bib.bib10)\]\.

At each decision steptt, a partition is chosen according to Thompson sampling\. For each armk∈\{1,2,…,K\}k\\in\\\{1,2,\\dots,K\\\}, we draw a sampleθ~k\\tilde\{\\theta\}\_\{k\}which represents a plausible estimate of the expected reward for partitionkkunder the current posterior distribution\. The selected arm is then given by

at=arg⁡maxk⁡θ~k\.a\_\{t\}=\\arg\\max\_\{k\}\\tilde\{\\theta\}\_\{k\}\.\(8\)
Once a partition is selected, computational resources are allocated to it by performing a self\-avoiding walk on the corresponding partitioned sequence\. This gives a rewardrtr\_\{t\}, defined as the normalized merit factor obtained during the search\. The parameters of the chosen arm are then updated using the fractional Thompson sampling rule described above\. This process repeats until the stopping condition is achieved\.

Based on the proposed approach, we introduce a new algorithm for generating binary sequences with high merit factors, called TS\-SAW\. The pseudo\-code of the algorithm is presented in Algorithm[1](https://arxiv.org/html/2607.09688#alg1), while a flowchart illustrating the overall procedure is provided in Figure[2](https://arxiv.org/html/2607.09688#Sx3.F2)\. To reduce the time and memory complexity of the proposed method, and to enable efficient use of multi\-threading on modern processors and graphical processing units, the𝙱𝙴𝚂𝚃​\_​𝙽𝙴𝙸𝙶𝙷𝙱𝙾𝚄𝚁\\mathtt\{BEST\\\_NEIGHBOUR\}function employs lightweight flip probing of skew\-symmetric binary sequences with linear time and space complexity, as suggested in\[[16](https://arxiv.org/html/2607.09688#bib.bib12)\]\. This results in a total complexity ofO​\(\(L/2−p\)⋅L\)=O​\(L2\)O\(\(L/2\-p\)\\cdot L\)=O\(L^\{2\}\)for each call, enabling an efficient neighborhood evaluation mechanism requiring minimal memory\. The neighborhood of a binary sequence consists of all sequences that differ from the original by a single element\. Once all neighbors of the current pivot \(current sequence in the self\-avoiding walk\) have been evaluated, the new pivot is selected as the unvisited neighbor with the minimum energy\. In the same work\[[16](https://arxiv.org/html/2607.09688#bib.bib12)\], an in\-memory flip algorithm for skew\-symmetric binary sequences with linear time and space complexity was also proposed, and is adopted here\. The function maintains skew\-symmetry and flips the elements at indexesiiand\(L−q\)−1\(L\-q\)\-1\.

Algorithm 1Pseudocode of the proposed TS\-SAW algorithm for generating binary sequences with high merit factors using search space prioritization\.1:

𝔹​𝔽←e​m​p​t​y\\mathbb\{BF\}\\leftarrow empty⊳\\trianglerightCreate an empty Bloom Filter

2:for

k=1,…,Kk=1,\\dots,Kdo

3:

θ^k∼Beta​\(αk,βk\)\\hat\{\\theta\}\_\{k\}\\sim\\text\{Beta\}\(\\alpha\_\{k\},\\beta\_\{k\}\)
4:endfor

5:

at=arg⁡maxk⁡θ~ka\_\{t\}=\\arg\\max\_\{k\}\\tilde\{\\theta\}\_\{k\}⊳\\trianglerightSelect a promising search region

6:

s​e​q←init\_partitioned\_sequence​\(at\)seq\\leftarrow\\textsc\{init\\\_partitioned\\\_sequence\}\(a\_\{t\}\)
7:

s​e​qb​e​s​t←s​e​qseq\_\{best\}\\leftarrow seq
8:

𝔹​𝔽\.insert​\(s​e​q\)\\mathbb\{BF\}\.\\textsc\{insert\}\(seq\)
9:

e←energy​\(s​e​q\)e\\leftarrow\\textsc\{energy\}\(seq\)
10:

eb​e​s​t←ee\_\{best\}\\leftarrow e
11:

i​t←0it\\leftarrow 0
12:while

i​t<Tiit<T\_\{i\}do⊳\\trianglerightSelf\-avoiding walk of lengthTiT\_\{i\}

13:

i​t←i​t\+1it\\leftarrow it\+1
14:

i,d​e​l​t​a←best\_neighbour​\(s​e​q\)i,delta\\leftarrow\\textsc\{best\\\_neighbour\}\(seq\)
15:if

i=−1i=\-1then

16:break

17:endif

18:

sequence\_flip\_skew​\(s​e​q,i\)\\textsc\{sequence\\\_flip\\\_skew\}\(seq,i\)
19:

𝔹​𝔽\.insert​\(s​e​q\)\\mathbb\{BF\}\.\\textsc\{insert\}\(seq\)
20:

e←e\+d​e​l​t​ae\\leftarrow e\+delta
21:if

e<eb​e​s​te<e\_\{best\}then

22:

s​e​qb​e​s​t←s​e​qseq\_\{best\}\\leftarrow seq
23:

eb​e​s​t←ee\_\{best\}\\leftarrow e
24:endif

25:endwhile

26:

rt←calculate\_reward​\(s​e​qb​e​s​t\)r\_\{t\}\\leftarrow\\textsc\{calculate\\\_reward\}\(seq\_\{best\}\)
27:

\(αat,βat\)←\(αat,βat\)\+\(rt,1−rt\)\(\\alpha\_\{a\_\{t\}\},\\beta\_\{a\_\{t\}\}\)\\leftarrow\(\\alpha\_\{a\_\{t\}\},\\beta\_\{a\_\{t\}\}\)\+\(r\_\{t\},1\-r\_\{t\}\)⊳\\trianglerightUpdate beliefs about the selected search region

![Refer to caption](https://arxiv.org/html/2607.09688v1/x6.png)Figure 2:Flowchart illustrating the main steps of the proposed TS\-SAW algorithm for generating binary sequences with high merit factors\.To prevent cycling in the search process, the algorithm stores sequences’ hashes, which limits the walk lengthTiT\_\{i\}due to memory constraints\. Since high performance depends on a small memory footprint, so the data can fit in fast GPU shared memory and CPU cache, we use a Bloom filter\[[5](https://arxiv.org/html/2607.09688#bib.bib13)\]in the suggested algorithm\. This reduces memory usage and allows longer walks, while still providing a fast lookup for previously visited sequences, with a negligible chance of error\.

Based on our previous research\[[8](https://arxiv.org/html/2607.09688#bib.bib6),[37](https://arxiv.org/html/2607.09688#bib.bib10)\], graphical processing units offer several advantages for the LABS problem\. Each walk is independent, allowing efficient parallelization with minimal synchronization overhead\. In our implementation, each self\-avoiding walk, as described in Algorithm[1](https://arxiv.org/html/2607.09688#alg1), is executed within a CUDA block with multiple threads, enabling multiple walks to run concurrently\. This allows micro and macro parallelization of the algorithm, which improves efficiency and speed\. To share information across walks and reduce entropy, a single global belief, represented byαk\\alpha\_\{k\}andβk\\beta\_\{k\}parameters of each arm, is obtained and updated after each walk\. Each walk can therefore be seen as an independent agent, sampling from the shared posterior and selecting a trajectory accordingly, which promotes exploration diversity\. The global belief is then updated using the aggregated outcomes of all walks\. While updates are delayed due to batching, shared observations accelerate learning and improve overall efficiency\.

In\[[37](https://arxiv.org/html/2607.09688#bib.bib10)\], we showed that combining parallel stochastic search with targeted refinement is an effective strategy for solving extremely challenging combinatorial optimization problems such as LABS\. Statistical tests further confirmed that this two\-step method significantly outperforms single\-step approaches\. In this work, we adopt the same overall approach, but modify the transition between the two steps\. Instead of filtering candidate solutions for the second step using a fixed merit factor threshold, we selectmmbest candidates based on the second\-step capacity\. These candidates are chosen by ranking all parallel self\-avoiding walks according to their merit factor and selecting the top subset using the quickselect algorithm, which operates in expected linear time\. Although the second step itself remains unchanged from the original paper, its pseudocode is provided in Algorithm[2](https://arxiv.org/html/2607.09688#alg2)for completeness\. The purpose of the second step is to explore the full search space without imposing the skew\-symmetry and partition constraints used in the first step in the hopes of improving the solution quality further\. For clarity, the overall approach is depicted in Figure[3](https://arxiv.org/html/2607.09688#Sx3.F3)\. The𝚂𝙴𝚀𝚄𝙴𝙽𝙲𝙴​\_​𝙵𝙻𝙸𝙿\\mathtt\{SEQUENCE\\\_FLIP\}function flips theii\-th element of a sequence in linear time and space complexity\. It differs from the𝚂𝙴𝚀𝚄𝙴𝙽𝙲𝙴​\_​𝙵𝙻𝙸𝙿​\_​𝚂𝙺𝙴𝚆\\mathtt\{SEQUENCE\\\_FLIP\\\_SKEW\}function in that it modifies only a single element and does not preserve skew\-symmetry\. The𝙼𝙰𝙺𝙴​\_​𝚁𝙾𝚃𝙰𝚃𝙸𝙾𝙽𝚂\\mathtt\{MAKE\\\_ROTATIONS\}function generates multiple variants of a given pivoting sequence by rotating it left and right by up toTrT\_\{r\}positions, where each rotation shifts elements cyclically while preserving the sequence length:

s′​\[i\]=s​\[\(i\+r\)modL\]\.s^\{\\prime\}\[i\]=s\[\(i\+r\)\\bmod\\,L\]\.\(9\)
Because these rotations only rearrange the positions of elements without changing their values, the resulting sequences typically have similar energy \(or merit factor\) to the original sequence\. Each rotated sequence is then inserted into the priority queue for further evaluation\. Unlike transformations used in the first step, this function does not preserve skew\-symmetry or the restriction class as well, which allows the algorithm to explore a broader region of the search space\. This design enables continuous and efficient utilization of computational resources, since both steps can run in parallel, allowing the system to maintain high throughput while minimizing idle CPU and GPU time\.

![Refer to caption](https://arxiv.org/html/2607.09688v1/x7.png)Figure 3:Two\-step optimization pipeline combining parallel stochastic search and unconstrained refinement\. The topmmcandidates are selected via quickselect and passed to a second phase for further improvement\.Algorithm 2Second step using a priority queue1:

c​a​n​d​i​d​a​t​ecandidate⊳\\trianglerightCandidate from the first phase \(SAW\)

2:

s​e​qb​e​s​tseq\_\{best\}⊳\\trianglerightBinary sequence with the best merit factor found

3:

ℙ​ℚ,ℍ←e​m​p​t​y,e​m​p​t​y\\mathbb\{PQ\},\\mathbb\{H\}\\leftarrow empty,empty\\⊳\\trianglerightEmpty priority queue and hash set

4:

s​e​qb​e​s​t←c​a​n​d​i​d​a​t​eseq\_\{best\}\\leftarrow candidate
5:

eb​e​s​t←energy​\(c​a​n​d​i​d​a​t​e\)e\_\{best\}\\leftarrow\\textsc\{energy\}\(candidate\)
6:

ℙ​ℚ\.push​\(c​a​n​d​i​d​a​t​e\)\\mathbb\{PQ\}\.\\textsc\{push\}\(candidate\)
7:

u←0u\\leftarrow 0
8:while

u<Tuu<T\_\{u\}do

9:

u←u\+1u\\leftarrow u\+1
10:

seqc​u​r​r​e​n​t←ℙℚ\.pop\(seq\_\{current\}\\leftarrow\\mathbb\{PQ\}\.\\textsc\{pop\}\(\)

11:for

eachi∈0\.\.L\\textbf\{each\}\\ i\\in 0\.\.Ldo⊳\\trianglerightNeighborhood search

12:

h​a​s​h←hash\_flip​\(i\)hash\\leftarrow\\textsc\{hash\\\_flip\}\(i\)
13:if

ℍ\.contains​\(h​a​s​h\)\\mathbb\{H\}\.\\textsc\{contains\}\(hash\)then

14:continue

15:endif

16:

s​e​qc​u​r​r​e​n​t←sequence\_flip​\(s​e​qc​u​r​r​e​n​t,i\)seq\_\{current\}\\leftarrow\\textsc\{sequence\\\_flip\}\(seq\_\{current\},i\)
17:

ℙ​ℚ\.push​\(s​e​qc​u​r​r​e​n​t\)\\mathbb\{PQ\}\.\\textsc\{push\}\(seq\_\{current\}\)
18:

ℍ\.insert​\(h​a​s​h\)\\mathbb\{H\}\.\\textsc\{insert\}\(hash\)
19:

ec​u​r​r​e​n​t←energy​\(s​e​qc​u​r​r​e​n​t\)e\_\{current\}\\leftarrow\\textsc\{energy\}\(seq\_\{current\}\)
20:if

ec​u​r​r​e​n​t<eb​e​s​te\_\{current\}<e\_\{best\}then

21:

s​e​qb​e​s​t←s​e​qc​u​r​r​e​n​tseq\_\{best\}\\leftarrow seq\_\{current\}⊳\\trianglerightNew best sequence found

22:

eb​e​s​t←ec​u​r​r​e​n​te\_\{best\}\\leftarrow e\_\{current\}
23:

u←0u\\leftarrow 0⊳\\trianglerightResetuuto support dynamic depth

24:endif

25:

make\_rotations​\(s​e​qc​u​r​r​e​n​t,ℙ​ℚ,ℍ,Tr\)\\textsc\{make\\\_rotations\}\(seq\_\{current\},\\mathbb\{PQ\},\\mathbb\{H\},T\_\{r\}\)
26:

s​e​qc​u​r​r​e​n​t←sequence\_flip​\(s​e​qc​u​r​r​e​n​t,i\)seq\_\{current\}\\leftarrow\\textsc\{sequence\\\_flip\}\(seq\_\{current\},i\)
27:endfor

28:endwhile

29:return

s​e​qb​e​s​tseq\_\{best\}⊳\\trianglerightBest sequence found

To extend the improvements achieved for odd\-length binary sequences to the even\-length case, sequence operators\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]can be systematically employed\. These operators act by appending or removing elements at either end of a given sequence, thereby generating new candidate sequences of modified length while possibly preserving key properties\. In particular, starting from optimized odd\-length sequences, such transformations enable the construction of both odd\- and even\-length variants with comparable merit factorFF\. The resulting sequences are subsequently reintroduced into the second optimization step, where they serve as promising initial candidates for further refinement\.

In summary, the proposed method integrates adaptive resource allocation with large\-scale parallel stochastic search to efficiently navigate the combinatorial space of binary sequences\. By combining Thompson sampling–based partition selection, GPU\-accelerated self\-avoiding walks, and a two\-step refinement strategy, the approach enables both effective exploration of constrained subspaces and thorough exploitation of promising candidates in the unconstrained domain\. The inclusion of sequence operators further extends the applicability of the method to sequences of arbitrary length, ensuring a unified framework for both odd\- and even\-length cases\. This design provides a practical and scalable foundation for high\-performance optimization in the LABS problem\.

## Results

We implemented the proposed method and Algorithm[1](https://arxiv.org/html/2607.09688#alg1)in the C\+\+ programming language using CUDA Toolkit version 13\.2\. Algorithm[2](https://arxiv.org/html/2607.09688#alg2)was implemented in the Rust programming language \(version 1\.95\)\. All experiments were conducted on the Vega grid computing environment, Slovenia’s petascale supercomputer, usingNVIDIA A100\-SXM4\-40GBGPUs\. Unless stated otherwise, all experimental parameters were adopted from our previous study\[[37](https://arxiv.org/html/2607.09688#bib.bib10)\], in which they were systematically tuned\.

To evaluate the partitions \(restriction classes\) for required values ofpp, we employed the algorithm presented in\[[17](https://arxiv.org/html/2607.09688#bib.bib52)\]\. The potentials and normalized potentials were then computed as described in\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]; by partitioning a sequence of sufficient length and setting the middlek−p\+1k\-p\+1free elements to the neutral element0, as shown in Equation[5](https://arxiv.org/html/2607.09688#Sx1.E5)\. In addition, the number of summandsggfor each partition was recorded\. As a note, the potential and normalized potential are invariant of the sequence lengthLL\. For transparency and reproducibility, top partitions ordered by increasing normalized potential forp=81p=81andq=7q=7together with their corresponding potential and normalized potential values are reported in Table[1](https://arxiv.org/html/2607.09688#Sx4.T1)\.

Table 1:Partitions forp=81p=81andq=7q=7, ordered by increasing normalized potential, together with their corresponding potential and normalized potential values\.To improve the best binary sequences reported in the literature, we applied the proposed approach to all odd\-length binary sequences in the range450≤L≤527450\\leq L\\leq 527, as well as toL=573L=573, using100,000100,\\\!000iterations\. An iteration corresponds to a single execution across all blocks of Algorithm[1](https://arxiv.org/html/2607.09688#alg1), in which block\-size parallel self\-avoiding walks are performed\. Then the bestmmsequences are selected and optimized with the second step\. In this work, we setm=15m=15, mainly considering the computational constraints of a single node in the computing grid and the runtime of an iteration of the first step, without performing any parameter tuning\. To extend the improvements to even lengths, the resulting partitioned skew\-symmetric sequences were transformed to even lengths using sequence operators and then reintroduced to the second step as show in Figure[3](https://arxiv.org/html/2607.09688#Sx3.F3)\. Overall, this procedure led to improvements for3535sequences\. The resulting improved binary sequences and their corresponding merit factors, in comparison with the previously best reported results in literature\[[37](https://arxiv.org/html/2607.09688#bib.bib10),[15](https://arxiv.org/html/2607.09688#bib.bib4)\], are presented in Figure[4](https://arxiv.org/html/2607.09688#Sx4.F4)and summarized in TableLABEL:tab:records\. It should also be noted that in Figure[4](https://arxiv.org/html/2607.09688#Sx4.F4), the x\-axis \(sequence length interval\) is not continuous, as only selected discrete lengths are included for which improvements were obtained\. In TableLABEL:tab:records, each hexadecimal digit is mapped to a44\-bit binary representation \(i\.e\.,0=00000=0000,1=00011=0001,…\\dots,F=1111F=1111\)\. To obtain the correct sequence length, leading zero\-padding introduced by this encoding must be removed\. Finally, the binary sequences are reconstructed by mapping each binary digit to its corresponding bipolar value, specifically by converting every0→−10\\rightarrow\-1\.

![Refer to caption](https://arxiv.org/html/2607.09688v1/x8.png)Figure 4:Record merit factors achieved by the improved sequences, together with the previously best\-known merit factors reported in the literature\[[37](https://arxiv.org/html/2607.09688#bib.bib10),[15](https://arxiv.org/html/2607.09688#bib.bib4)\], for sequence lengths in the interval450≤L≤527450\\leq L\\leq 527and forL=573L=573\.The largest improvement was achieved forL=451L=451, where the previously best\-known merit factor was increased by0\.82480\.8248\. The resulting sequence attains a merit factor ofF=8\.0555F=8\.0555, making it the longest sequence reported in the literature withF≥8\.0F\\geq 8\.0\. Previously, the longest known sequence satisfying this condition was the sequence of lengthL=309L=309reported in\[[15](https://arxiv.org/html/2607.09688#bib.bib4)\]\. In addition,L=573L=573is the longest sequence in the literature with a merit factor above7\.07\.0, for which we achieved an improvement of0\.25640\.2564\. ForL=518L=518, the merit factor was also improved; notably, this was the only sequence in the considered interval that was not improved by the solver in\[[37](https://arxiv.org/html/2607.09688#bib.bib10)\]\. Across all improved sequences, the mean increase in merit factor was0\.19670\.1967\. These results demonstrate the effectiveness of the proposed method in discovering high\-quality binary sequences with large merit factors, particularly for longer sequence lengths\. The consistent improvements observed across a broad range of lengths suggest that prioritizing promising regions of the search space provides a robust, practical, and scalable foundation for high\-performance optimization of the LABS problem\.

To show how Thompson sampling affects partition selection, we conducted an additional experiment with sequence lengthL=461L=461, limiting the proposed optimizer to80,00080,\\\!000iterations\. We selected partition parametersp=67p=67andg=5g=5based on the sequence length\. For that pair, the number of unique partitions is80568056\. The goal of this experiment was to analyze how the probabilistic selection mechanism influences exploration and exploitation of the partition space over time, and whether it leads to a bias toward higher\-quality regions of the search space\. In particular, we tracked the frequency with which individual partitions were sampled and their\(αk,βk\)\(\\alpha\_\{k\},\\beta\_\{k\}\)values during optimization\. Table[2](https://arxiv.org/html/2607.09688#Sx4.T2)presents the most frequently sampled partitions, along with the number of times each partition was selected, its ranking according to normalized potential, and the corresponding normalized potential value\. The table includes the three most frequently sampled partitions and the three highest\-ranked partitions according to normalized potential\. It is evident that a clear mismatch occurs between the number of times a partition was selected and its rank when ordered by the normalized potential\. This result indicates that partitions with the highest normalized potential are not necessarily the most effective during optimization\. Thompson sampling progressively favors partitions that produce better empirical results, even when their normalized potential ranking is lower\. Consequently, the sampling process is guided not only by the heuristic estimate \(in case not every partition of a given pair is used\), but also by the observed optimization performance of each partition\. To provide further insight, we analyzed the probability density functions \(PDFs\) corresponding to the best\-ranked partition, the most frequently sampled partition, and a partition with rank 4, representing average performance\. As a note, a PDF describes the distribution of a continuous random variable by assigning relative likelihoods to its possible values\. Probabilities are obtained by integrating the PDF over an interval, with the total area under the function equal to one\.

Table 2:Most frequently sampled and top ranked partitions by normalized potential forL=461L=461after80,00080,\\\!000iterations for pairp=67p=67andg=5g=5\. The table shows sampling rank, sampling frequency, normalized potential rank, and normalized potential value, comparing empirical selection with heuristic ranking under Thompson sampling\.![Refer to caption](https://arxiv.org/html/2607.09688v1/x9.png)Figure 5:Probability density functions at different iterations for selected partitions forL=461L=461and pairp=67p=67andg=5g=5\.During the early stages of the search, when only a limited number of observations are available, the posterior distributions exhibit substantial overlap, indicating considerable uncertainty regarding the relative quality of the selected partitions\. As additional observations are collected, the distributions become increasingly concentrated and better separated, reflecting reduced uncertainty and more accurate estimates of expected rewards\. By iteration72007200, the posterior distribution corresponding to the most frequently sampled partition is clearly centered at the highest expected value, with minimal overlap with the other distributions, indicating that it is the most promising candidate\. Initially, all three partitions are sampled at similar rates due to the high level of uncertainty\. As the search progresses and confidence in the reward estimates increases, the sampling process gradually shifts toward the partition with the highest estimated reward, illustrating the balance between exploration and exploitation achieved by Thompson sampling\.

In general, the results show that the proposed framework gradually shifts from uniform exploration toward partitions that yield higher observed rewards\. In early iterations, a broad range of partitions is sampled, while later stages focus on a smaller subset of consistently high\-performing partitions\. This effect is most pronounced in regions associated with high\-quality sequences, while less promising partitions are increasingly suppressed, reducing wasted computation\. Overall, this provides a good balance between exploration and exploitation, concentrating search effort on promising regions while maintaining diversity in the early phase\.

Despite the improvements reported in this work, the results also confirm the increasing difficulty of achieving substantial merit\-factor gains as the sequence length grows\. For larger values ofLL, improvements become smaller and less frequent, consistent with the increasingly rugged optimization landscape of the LABS problem\. Nevertheless, obtaining improvements for long sequences, includingL=573L=573, demonstrates the scalability of the proposed framework and its suitability for large\-scale parallel computing environments\. These results further indicate that partition\-guided large\-scale stochastic optimization remains a promising direction for advancing the state\-of\-the\-art in the LABS problem\.

Table 3:Improved binary sequences and their merit factor values in the interval450≤L≤527450\\leq L\\leq 527and forL=573L=573, and the previously best\-known merit factor values reported in\[[37](https://arxiv.org/html/2607.09688#bib.bib10),[15](https://arxiv.org/html/2607.09688#bib.bib4)\]\.LLPreviousFF\[[37](https://arxiv.org/html/2607.09688#bib.bib10),[15](https://arxiv.org/html/2607.09688#bib.bib4)\]OurFFSequence4504507\.02307\.02307\.7831\\mathbf\{7\.7831\}3ffffff8003ff03c3831ce6730c1fe0f187c3e133393e85ce798b1c9b9c93d9a6c85eb1b3316b4a592d6a94d3266c935b4b52ab555aaaaaaa4514517\.23077\.23078\.0555\\mathbf\{8\.0555\}7ffffff8003ff03c3831ce6730c1fe0f187c3e133393e85ce798b1c9b9c93d9a6c85eb1b3316b4a592d6a94d3266c935b4b52ab555aaaaaaa4524527\.34597\.34597\.8134\\mathbf\{7\.8134\}fffffff0007fe07870639cce6183fc1e30f87c266727d0b9cf31639373927b34d90bd636662d694b25ad529a64cd926b696a556aab55555554554557\.78357\.78357\.9362\\mathbf\{7\.9362\}7ffffff0007f83f0664dcd81b31fe30f31e4b253ca6693ce2f06cbd2c4f0bce52f6cb1e67cb073c6932d36a933958c8c6652b5aa5552aaaaaa4564567\.62907\.62907\.8242\\mathbf\{7\.8242\}fffffff0007f83f0664dcd81b31fe30f31e4b253ca6693ce2f06cbd2c4f0bce52f6cb1e67cb073c6932d36a933958c8c6652b5aa5552aaaaaa4574577\.50827\.50827\.7169\\mathbf\{7\.7169\}1ffffffe000ff07e0cc9b9b03663fc61e63c964a794cd279c5e0d97a589e179ca5ed963ccf960e78d265a6d52672b1918cca56b54aaa55555554584587\.42957\.42957\.5798\\mathbf\{7\.5798\}3ffffffc001fe0fc199373606cc7f8c3cc792c94f299a4f38bc1b2f4b13c2f394bdb2c799f2c1cf1a4cb4daa4ce563231994ad6a9554aaaaaaa4594597\.41997\.41997\.4704\\mathbf\{7\.4704\}7ffffffe000ff07e0cc9b9b03663fc61e63c964a794cd279c5e0d97a589e179ca5ed963ccf960e78d265a6d52672b1918cca56b54aaa55555554604607\.53027\.53027\.6280\\mathbf\{7\.6280\}fffffff0007ff803e1e3d83d387661b631e9c6b4cc3cc399390ed99b6363998ed1b19b4cb4cc3e49e936396625b0b58b696b55aaa5552aaaaaa4614617\.64357\.64357\.8282\\mathbf\{7\.8282\}1ffffffe000fff007c3c7b07a70ecc36c63d38d6998798732721db336c6c7331da363369969987c93d26c72cc4b616b16d2d6ab554aaa55555554624627\.50987\.50987\.7273\\mathbf\{7\.7273\}3ffffffc001ffe00f878f60f4e1d986d8c7a71ad330f30e64e43b666d8d8e663b46c66d32d330f927a4d8e59896c2d62da5ad56aa9554aaaaaab4634637\.38857\.38857\.4233\\mathbf\{7\.4233\}7ffffff0007fd80787e13f04f0dc393c8e58276cb978e466c3ce727932731a726cb4e646da1bce27586dcb1b48d2c52b16a5a558aa5552aaaaaa4644647\.26177\.26177\.4569\\mathbf\{7\.4569\}fffffff0007fd80787e13f04f0dc393c8e58276cb978e466c3ce727932731a726cb4e646da1bce27586dcb1b48d2c52b16a5a558aa5552aaaaaa4654657\.38077\.38077\.5413\\mathbf\{7\.5413\}1ffffffe000ffb00f0fc27c09e1b872791cb04ed972f1c8cd879ce4f264e634e4d969cc8db4379c4eb0db963691a58ad62d4b4ab154aaa55555554754757\.37487\.37487\.4233\\mathbf\{7\.4233\}7fffffe0007fe00fc0f1e278f0078cdb90e639e370e5a7331b0f2c6636cbce3664f2d39332786d2369b66d1b8cda552da7692d4ad56aa5556aaaaaa4764767\.30047\.30047\.4976\\mathbf\{7\.4976\}ffffffe0007fe00fc0f1e278f0078cdb90e639e370e5a7331b0f2c6636cbce3664f2d39332786d2369b66d1b8cda552da7692d4ad56aa5556aaaaaa4774777\.29737\.29737\.5732\\mathbf\{7\.5732\}1ffffffc000ffc01f81e3c4f1e00f19b721cc73c6e1cb4e66361e58cc6d979c6cc9e5a72664f0da46d36cda3719b4aa5b4ed25a95aad54aaad5555554784787\.29567\.29567\.5582\\mathbf\{7\.5582\}3ffffffe0007fe00fc0f1e278f0078cdb90e639e370e5a7331b0f2c6636cbce3664f2d39332786d2369b66d1b8cda552da7692d4ad56aa5556aaaaaa4794797\.41527\.41527\.6445\\mathbf\{7\.6445\}7ffffffc000ffc01f81e3c4f1e00f19b721cc73c6e1cb4e66361e58cc6d979c6cc9e5a72664f0da46d36cda3719b4aa5b4ed25a95aad54aaad5555554804807\.39227\.39227\.5989\\mathbf\{7\.5989\}fffffff8001ff803f03c789e3c01e336e4398e78dc3969ccc6c3cb198db2f38d993cb4e4cc9e1b48da6d9b46e336954b69da4b52b55aa9555aaaaaaa4814817\.37017\.37017\.7038\\mathbf\{7\.7038\}1fffffff0003ff007e078f13c7803c66dc8731cf1b872d3998d8796331b65e71b327969c9993c3691b4db368dc66d2a96d3b496a56ab552aab55555554824827\.41547\.41547\.6579\\mathbf\{7\.6579\}3fffffff0003ff007e078f13c7803c66dc8731cf1b872d3998d8796331b65e71b327969c9993c3691b4db368dc66d2a96d3b496a56ab552aab55555554834837\.46917\.46917\.6134\\mathbf\{7\.6134\}7ffffffe0007fe00fc0f1e278f0078cdb90e639e370e5a7331b0f2c6636cbce3664f2d39332786d2369b66d1b8cda552da7692d4ad56aa5556aaaaaaa4844847\.38427\.38427\.4861\\mathbf\{7\.4861\}7ffffffe0007fe00fc0f1e278f0078cdb90e639e370e5a7331b0f2c6636cbce3664f2d39332786d2369b66d1b8cda552da7692d4ad56aa5556aaaaaaa4904907\.42297\.42297\.5008\\mathbf\{7\.5008\}3ffffff8001ff80fc0f0f0f86cd09fe1666487ec3332de794b6c9cf3169b667187b34d8c70f965c3332c568e667a558bcc694b4b4ad4a955aaa955555554914917\.52397\.52397\.5541\\mathbf\{7\.5541\}7ffffff8001ff80fc0f0f0f86cd09fe1666487ec3332de794b6c9cf3169b667186b34d8c70f965c3332c568e667a558bcc694b4b4ad4a955aaa955555554944947\.62477\.62477\.6476\\mathbf\{7\.6476\}3fffffff8001ff80fc0f0f0f86cd09fe1666487ed3332de794b6c9cf3069b667187b34d8c70f965c3332c568e667a558bcc694b4b4ad4a955aaa955555554954957\.47807\.47807\.5836\\mathbf\{7\.5836\}7ffffffe0007fe03f03c3c3e1b3427f8599921fb0cccb79e52db273cc1a6d99c61acd3631c3e5970cccf15a3999e9562f31a52d2d2b52a556aaa555555554964967\.29417\.29417\.5428\\mathbf\{7\.5428\}ffffffff0003ff01f81e1e1f0d9a13fc2ccc90fda6665bcf296d939e60d36cce30d669b18e1f2cb866658ad1cccf4ab1798d2969695a952ab5552aaaaaaa4974977\.32367\.32367\.4544\\mathbf\{7\.4544\}1fffffffe0007fe03f03c3c3e1b3427f8599921fb0cccb79e52db273cc1a6d99c61acd3631c3e5970cccf15a3999e9562f31a52d2d2b52a556aaa555555554984987\.30077\.30077\.3701\\mathbf\{7\.3701\}3fffffffe0007fe03f03c3c3e1b3427f8599921fb0cccb79e52db273cc1a6d99c61acd3631c3e5970cccf15a3999e9562f31a52d2d2b52a556aaa555555555165167\.18607\.18607\.2835\\mathbf\{7\.2835\}fffffff0001ffc007f01fc0f631b1c1cc3c63725a72d92ccc792cc9a58198791b91a5985879ccf1a4ccf18f27872364b4c94939362d4a952a554aa95552aaaaaa5175177\.31987\.31987\.3633\\mathbf\{7\.3633\}1ffffffe0003ff800fe03f81ec6363839878c6e4b4e5b25998f259934b0330f237234b30b0f399e34999e31e4f0e46c9699292726c5a952a54aa9552aaa55555555185187\.20727\.20727\.2665\\mathbf\{7\.2665\}3ffffffe0003ff800fe03f81ec6363839878c6e4b4e5b25998f259934b0330f237234b30b0f399e34999e31e4f0e46c9699292726c5a952a54aa9552aaa55555555735737\.02107\.02107\.2774\\mathbf\{7\.2774\}1fffffffc0003ffc01fc07e1c99a136c3c330e64e485e72d9878c7e1276338c5a1e739273639365a1ec932763a56c9699c365e8e4e64b32d2c73a198da56ad5aad552aaad5555555
## Conclusion

In this work, we addressed the problem of low autocorrelation binary sequences \(LABS\)\. The problem is characterized by an exponentially growing search space and a highly rugged landscape\. We proposed a hybrid framework that combines Thompson sampling–based online decision\-making with parallel self\-avoiding walks to allocate dynamically computational resources across restriction classes \(partitions\)\. The main idea of the proposed approach is to model the partitions as a stochastic decision\-making problem in Thompson sampling\. This allows the framework to dynamically allocate computational resources to promising regions of the search space\. The resulting method effectively balanced exploration and exploitation while maintaining scalability through parallel execution\.

We proposed an algorithm based on the above method to improve the results\. Experimental results on longer binary sequences show improvements over previously best\-known solutions across a wide range of sequence lengths\. We report new best\-known sequences for multiple lengths in the range450≤L≤527450\\leq L\\leq 527andL=573L=573, including the longest sequence with a merit factor exceeding8\.08\.0, forL=451L=451\. We also showed that Thompson sampling effectively shifts search effort toward partitions that yield higher merit factors\. This allowed us to empirically measure partition quality instead of relying on heuristics\. Overall, the results confirm that integrating probabilistic decision\-making with large\-scale parallel stochastic search is an effective strategy for LABS optimization\. Although improvements become more challenging as sequence length increases, the proposed approach remains effective, even in higher dimensions, and continues to yield state\-of\-the\-art results\.

We plan to further investigate the proposed online decision\-based prioritization of search regions by applying it to other difficult combinatorial optimization problems beyond LABS\. A key direction is to study problem classes in which the search space can be meaningfully divided into structured subregions, so that computational effort can be adjusted dynamically according to their observed performance during the search\. We also intend to explore how the design insights obtained from LABS optimization can be adapted for the construction of spreading codes in satellite communication systems\. Since low autocorrelation binary sequences are closely related to spreading code design used in GNSS and similar applications\. As a conclusion, we believe that the proposed framework opens a pathway toward adaptive, data\-driven search strategies for a wider class of combinatorial optimization problems\.

## References

- \[1\]\(2010\)’A modern Bayesian look at the multi\-armed bandit’ by Steven L\. Scott: Discussion\.\.Applied Stochastic Models in Business & Industry26\(6\)\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[2\]S\. Agrawal and N\. Goyal\(2012\)Analysis of thompson sampling for the multi\-armed bandit problem\.InConference on learning theory,pp\. 39–1\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p5.7)\.
- \[3\]J\. M\. Baden\(2011\)Efficient Optimization of the Merit Factor of Long Binary Sequences\.IEEE Transactions on Information Theory57\(12\),pp\. 8084–8094\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2011.2164778)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p2.11)\.
- \[4\]J\. Bernasconi\(1987\-04\)Low autocorrelation binary sequences: statistical mechanics and configuration space analysis\.J\. Physsique48,pp\. 559–567\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[5\]B\. H\. Bloom\(1970\)Space/time trade\-offs in hash coding with allowable errors\.Communications of the ACM13\(7\),pp\. 422–426\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p10.1)\.
- \[6\]P\. Borwein, K\.\-K\.S\. Choi, and J\. Jedwab\(2004\)Binary sequences with merit factor greater than 6\.34\.IEEE Transactions on Information Theory50\(12\),pp\. 3234–3249\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2004.838341)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p2.11)\.
- \[7\]B\. Bošković, F\. Brglez, and J\. Brest\(2017\)Low\-autocorrelation binary sequences: On improved merit factors and runtime predictions to achieve them\.Applied Soft Computing56,pp\. 262–285\.External Links:ISSN 1568\-4946,[Document](https://dx.doi.org/10.1016/j.asoc.2017.02.024)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[8\]B\. Bošković, J\. Herzog, and J\. Brest\(2024\)Parallel self\-avoiding walks for a low\-autocorrelation binary sequences problem\.Journal of Computational Science77,pp\. 102260\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11),[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8),[Method](https://arxiv.org/html/2607.09688#Sx3.p11.2),[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[9\]J\. Brest and B\. Bošković\(2018\)A Heuristic Algorithm for a Low Autocorrelation Binary Sequence Problem With Odd Length and High Merit Factor\.IEEE Access6\(\),pp\. 4127–4134\.External Links:[Document](https://dx.doi.org/10.1109/ACCESS.2018.2789916)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[10\]J\. Brest and B\. Bošković\(2022\-12\)Computational Search of Long Skew\-symmetric Binary Sequences with High Merit Factors\.MENDEL28\(2\),pp\. 17–24\.External Links:[Document](https://dx.doi.org/10.13164/mendel.2022.2.017)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[11\]J\. Brest, A\. Brest, B\. Pšeničnik, J\. Popič, and B\. Borko\(2025\)Oddaljenost neperiodičnih binarnih zaporedij glede na dve meri avtokorelacijskih lastnosti\.Elektrotehniski Vestnik92\(3\),pp\. 97–103\.Note:\(In Slovene\)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p3.7)\.
- \[12\]A\. G\. Cadavid, P\. Chandarana, S\. V\. Romero, J\. Trautmann, E\. Solano, T\. L\. Patti, and N\. N\. Hegade\(2025\)Scaling advantage with quantum\-enhanced memetic tabu search for labs\.arXiv preprint arXiv:2511\.04553\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.48550/arXiv.2511.04553)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8)\.
- \[13\]O\. Chapelle and L\. Li\(2011\)An empirical evaluation of thompson sampling\.Advances in neural information processing systems24\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[14\]V\. M\. de Oliveira, J\. F\. Fontanari, and P\. F\. Stadler\(1999\-12\)Metastable states in short\-ranged p\-spin glasses\.Journal of Physics A: Mathematical and General32\(50\),pp\. 8793\.External Links:[Document](https://dx.doi.org/10.1088/0305-4470/32/50/302)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p4.9)\.
- \[15\]M\. Dimitrov\(2022\)New classes of binary sequences with high merit factor\.arXiv preprint arXiv:2206\.12070\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p6.7),[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11),[Method](https://arxiv.org/html/2607.09688#Sx3.p1.1),[Method](https://arxiv.org/html/2607.09688#Sx3.p14.1),[Figure 4](https://arxiv.org/html/2607.09688#Sx4.F4),[Table 3](https://arxiv.org/html/2607.09688#Sx4.T3),[Table 3](https://arxiv.org/html/2607.09688#Sx4.T3.6.2.2.1.1.1),[Results](https://arxiv.org/html/2607.09688#Sx4.p2.7),[Results](https://arxiv.org/html/2607.09688#Sx4.p3.12),[Results](https://arxiv.org/html/2607.09688#Sx4.p4.10)\.
- \[16\]M\. Dimitrov\(2025\)On the skew\-symmetric binary sequences and the merit factor problem\.Digital Signal Processing156,pp\. 104793\.External Links:ISSN 1051\-2004,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.dsp.2024.104793),[Link](https://www.sciencedirect.com/science/article/pii/S1051200424004184)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11),[Method](https://arxiv.org/html/2607.09688#Sx3.p9.4)\.
- \[17\]D\. Eppstein\(2015\)PADS: python algorithms and data structures\.Note:MIT licensed software libraryExternal Links:[Link](http://www.ics.uci.edu/%CB%9Ceppstein/PADS/)Cited by:[Results](https://arxiv.org/html/2607.09688#Sx4.p2.7)\.
- \[18\]K\. Farnane, K\. Minaoui, and D\. Aboutajdine\(2018\)Local search algorithm for low autocorrelation binary sequences\.In2018 4th International Conference on Optimization and Applications \(ICOA\),Vol\.,pp\. 1–5\.External Links:[Document](https://dx.doi.org/10.1109/ICOA.2018.8370526)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[19\]J\. E\. Gallardo, C\. Cotta, and A\. J\. Fernández\(2009\)Finding low autocorrelation binary sequences with memetic algorithms\.Applied Soft Computing9\(4\),pp\. 1252–1262\.External Links:[Document](https://dx.doi.org/10.1016/j.asoc.2009.03.005)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[20\]M\. Golay\(1972\)A class of finite binary sequences with alternate auto\-correlation values equal to zero \(corresp\.\)\.IEEE Transactions on Information Theory18\(3\),pp\. 449–450\.External Links:[Document](https://dx.doi.org/10.1109/TIT.1972.1054797)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3),[Introduction](https://arxiv.org/html/2607.09688#Sx1.p5.1)\.
- \[21\]S\. Halim, R\. H\. C\. Yap, and F\. Halim\(2008\)Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem\.InPrinciples and Practice of Constraint Programming,P\. J\. Stuckey \(Ed\.\),Berlin, Heidelberg,pp\. 640–645\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[22\]J\. Healy and L\. McInnes\(2024\-11\-21\)Uniform manifold approximation and projection\.Nature Reviews Methods Primers4\(1\),pp\. 82\.External Links:ISSN 2662\-8449,[Document](https://dx.doi.org/10.1038/s43586-024-00363-x),[Link](https://doi.org/10.1038/s43586-024-00363-x)Cited by:[Figure 1](https://arxiv.org/html/2607.09688#Sx1.F1),[Introduction](https://arxiv.org/html/2607.09688#Sx1.p4.9)\.
- \[23\]J\. Herzog, J\. Brest, and B\. Bošković\(2023\)Analysis based on statistical distributions: a practical approach for stochastic solvers using discrete and continuous problems\.Information Sciences633,pp\. 469–490\.External Links:ISSN 0020\-0255,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ins.2023.03.081)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p3.11)\.
- \[24\]T\. Hoholdt and H\.E\. Jensen\(1988\)Determination of the merit factor of legendre sequences\.IEEE Transactions on Information Theory34\(1\),pp\. 161–164\.External Links:[Document](https://dx.doi.org/10.1109/18.2620)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p2.11)\.
- \[25\]J\. Jedwab, D\. J\. Katz, and K\. Schmidt\(2013\)Advances in the merit factor problem for binary sequences\.Journal of Combinatorial Theory, Series A120\(4\),pp\. 882–906\.External Links:[Document](https://dx.doi.org/10.1016/j.jcta.2013.01.010)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p2.11)\.
- \[26\]J\. Jedwab\(2004\)A survey of the merit factor problem for binary sequences\.InInternational Conference on Sequences and Their Applications,pp\. 30–55\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[27\]M\. N\. Katehakis and A\. F\. Veinott Jr\.\(1987\)The multi\-armed bandit problem: decomposition and computation\.Mathematics of Operations Research12\(2\),pp\. 262–268\.External Links:[Document](https://dx.doi.org/10.1287/moor.12.2.262)Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[28\]D\. J\. Katz and M\. E\. Ramirez\(2024\)Moments of autocorrelation demerit factors of binary sequences\.Designs, Codes and Cryptography,pp\. 1–45\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[29\]K\. Kettunen\(1997\)Code selection for CDMA systems\.Department of Information Studies, University of Tampere, Finland\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p2.3)\.
- \[30\]J\. E\. Littlewood\(1966\)On polynomials∑n±zm,∑neam​i​zm,z=e0​i\\sum^\{n\}\\pm z^\{m\},\\sum^\{n\}e^\{a\_\{m\}i\}z^\{m\},z=e^\{0i\}\.Journal of the London Mathematical Societys1\-41\(1\),pp\. 367–376\.External Links:[Document](https://dx.doi.org/10.1112/jlms/s1-41.1.367)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[31\]S\. Mertens\(1996\)Exhaustive search for low\-autocorrelation binary sequences\.Journal of Physics A: Mathematical and General29\(18\),pp\. L473\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p1.13)\.
- \[32\]G\. L\. Mullen and D\. Panario\(2013\)Other correlation measures\.InHandbook of Finite Fields,pp\. 322–324\.External Links:ISBN 143987378XCited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p3.3)\.
- \[33\]T\. Packebusch and S\. Mertens\(2016\)Low autocorrelation binary sequences\.Journal of Physics A: Mathematical and Theoretical49\(16\),pp\. 165001\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p4.9),[Introduction](https://arxiv.org/html/2607.09688#Sx1.p5.9),[Related work](https://arxiv.org/html/2607.09688#Sx2.p1.13)\.
- \[34\]K\. Piętak, D\. Żurek, M\. Pietroń, A\. Dymara, and M\. Kisiel\-Dorohinicki\(2019\)Striving for performance of discrete optimisation via memetic agent\-based systems in a hybrid CPU/GPU environment\.Journal of Computational Science31,pp\. 151–162\.External Links:ISSN 1877\-7503,[Document](https://dx.doi.org/doi.org/10.1016/j.jocs.2019.01.007)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8)\.
- \[35\]S\. D\. Prestwich\(2013\)Improved branch\-and\-bound for low autocorrelation binary sequences\.arXiv preprint arXiv:1305\.6187\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p1.13)\.
- \[36\]S\. Prestwich\(2007\-12\)Exploiting relaxation in local search for labs\.Annals of Operations Research156,pp\. 129–141\.External Links:[Document](https://dx.doi.org/10.1007/s10479-007-0226-9)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p1.13)\.
- \[37\]B\. Pšeničnik, R\. Mlinarič, J\. Brest, and B\. Bošković\(2025\)Dual\-step optimization for binary sequences with high merit factors\.Digital Signal Processing165,pp\. 105316\.External Links:ISSN 1051\-2004,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.dsp.2025.105316),[Link](https://www.sciencedirect.com/science/article/pii/S1051200425003380)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8),[Method](https://arxiv.org/html/2607.09688#Sx3.p11.2),[Method](https://arxiv.org/html/2607.09688#Sx3.p12.6),[Method](https://arxiv.org/html/2607.09688#Sx3.p5.9),[Figure 4](https://arxiv.org/html/2607.09688#Sx4.F4),[Table 3](https://arxiv.org/html/2607.09688#Sx4.T3),[Table 3](https://arxiv.org/html/2607.09688#Sx4.T3.6.2.2.1.1.1),[Results](https://arxiv.org/html/2607.09688#Sx4.p1.1),[Results](https://arxiv.org/html/2607.09688#Sx4.p3.12),[Results](https://arxiv.org/html/2607.09688#Sx4.p4.10)\.
- \[38\]D\. J\. Russo, B\. Van Roy, A\. Kazerouni, I\. Osband, Z\. Wen,et al\.\(2018\)A tutorial on thompson sampling\.Foundations and Trends \(R\) in Machine Learning11\(1\),pp\. 1–96\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p2.4)\.
- \[39\]K\. Schmidt\(2016\-01\)Sequences with small correlation\.Designs, Codes and Cryptography78,pp\.\.External Links:[Document](https://dx.doi.org/10.1007/s10623-015-0154-7)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p2.3)\.
- \[40\]M\. Sciorilli, G\. Camilo, T\. O\. Maciel, A\. Canabarro, L\. Borges, and L\. Aolita\(2025\)A competitive nisq and qubit\-efficient solver for the labs problem\.arXiv preprint arXiv:2506\.17391\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3),[Related work](https://arxiv.org/html/2607.09688#Sx2.p4.3)\.
- \[41\]I\. I\. Shapiro, G\. H\. Pettengill, M\. E\. Ash, M\. L\. Stone, W\. B\. Smith, R\. P\. Ingalls, and R\. A\. Brockelman\(1968\-05\)Fourth test of general relativity: preliminary results\.Phys\. Rev\. Lett\.20,pp\. 1265–1269\.External Links:[Document](https://dx.doi.org/10.1103/PhysRevLett.20.1265)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[42\]R\. Shaydulin, C\. Li, S\. Chakrabarti, M\. DeCross, D\. Herman, N\. Kumar, J\. Larson, D\. Lykov, P\. Minssen, Y\. Sun,et al\.\(2024\)Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem\.Science Advances10\(22\),pp\. eadm6761\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3),[Related work](https://arxiv.org/html/2607.09688#Sx2.p4.3)\.
- \[43\]M\. Skula, M\. Pies, R\. Hajovsky, J\. Velicka, and D\. Vala\(2026\-02\-13\)Multi\-criteria selection of a synchronisation word for low\-power iot receivers based on the iqrf standard\.Scientific Reports16\(1\),pp\. 8777\.External Links:[Document](https://dx.doi.org/10.1038/s41598-026-38142-1),[Link](https://doi.org/10.1038/s41598-026-38142-1)Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[44\]W\. R\. Thompson\(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3/4\),pp\. 285–294\.External Links:ISSN 00063444,[Link](http://www.jstor.org/stable/2332286)Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[45\]W\. R\. Thompson\(1935\)On the theory of apportionment\.American Journal of Mathematics57\(2\),pp\. 450–456\.Cited by:[Method](https://arxiv.org/html/2607.09688#Sx3.p3.1)\.
- \[46\]J\. Wiggenbrock\(2010\)Parallele optimierungsstrategien des labs\-problems in einem gpu\-grid\.Bachelor’s thesis,Fachhochschule Südwestfalen\(German\)\.Note:\(In German\)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p1.13)\.
- \[47\]A\. Yang, T\. Mina, S\. Boyd, and G\. Gao\(2024\)Large\-scale gnss spreading code optimization\.InProceedings of the 37th International Technical Meeting of the Satellite Division of The Institute of Navigation \(ION GNSS\+ 2024\),pp\. 948–957\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[48\]A\. Yang, T\. Mina, and G\. Gao\(2024\)Spreading code optimization for low\-earth orbit satellites via mixed\-integer convex programming\.EURASIP Journal on Advances in Signal Processing2024\(1\),pp\. 67\.Cited by:[Introduction](https://arxiv.org/html/2607.09688#Sx1.p1.3)\.
- \[49\]Z\. Zhang, J\. Shen, N\. Kumar, and M\. Pistoia\(2025\)New improvements in solving large labs instances using massively parallelizable memetic tabu search\.arXiv preprint arXiv:2504\.00987\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8)\.
- \[50\]D\. Żurek, K\. Piętak, M\. Pietroń, and M\. Kisiel\-Dorohinicki\(2017\)Toward hybrid platform for evolutionary computations of hard discrete problems\.Procedia Computer Science108,pp\. 877–886\.External Links:ISSN 1877\-0509,[Document](https://dx.doi.org/doi.org/10.1016/j.procs.2017.05.201)Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8)\.
- \[51\]D\. Żurek, M\. Pietroń, K\. Piętak, and M\. Kisiel\-Dorohinicki\(2022\)A deep neural network as a tabu support in solving labs problem\.InInternational Conference on Computational Science,pp\. 237–243\.Cited by:[Related work](https://arxiv.org/html/2607.09688#Sx2.p5.8)\.