New Hybrid Search Improves Low Autocorrelation Binary Sequences.

This research tackles the challenging Low Autocorrelation Binary Sequences (LABS) problem, a combinatorial optimization task with significant implications for fields like communications and signal processing. The authors propose a hybrid search framework that intelligently allocates computational resources across different regions of the LABS search space. The core of the method involves using Thompson sampling within a multi-armed bandit setup to dynamically prioritize search efforts towards partitions that empirically yield higher merit factors. This adaptive resource allocation is combined with parallel self-avoiding walks, GPU acceleration, and efficient neighborhood evaluation to enhance performance. A Bloom filter is also employed to prevent cycles during the search. Furthermore, the framework utilizes a two-stage optimization strategy: initially searching constrained skew-symmetric spaces, then refining the best candidates in the unrestricted space. Experiments demonstrate that this approach significantly improves upon previous best-known results for numerous sequence lengths, particularly for L between 450 and 527, and for L=573, including a new record for L=451.