Optimal Almost-Balanced Sequences
<|reference_start|>Optimal Almost-Balanced Sequences: This paper presents a novel approach to address the constrained coding challenge of generating almost-balanced sequences. While strictly balanced sequences have been well studied in the past, the problem of designing efficient algorithms with small redundancy, preferably constant or even a single bit, for almost balanced sequences has remained unsolved. A sequence is $\varepsilon(n)$-almost balanced if its Hamming weight is between $0.5n\pm \varepsilon(n)$. It is known that for any algorithm with a constant number of bits, $\varepsilon(n)$ has to be in the order of $\Theta(\sqrt{n})$, with $O(n)$ average time complexity. However, prior solutions with a single redundancy bit required $\varepsilon(n)$ to be a linear shift from $n/2$. Employing an iterative method and arithmetic coding, our emphasis lies in constructing almost balanced codes with a single redundancy bit. Notably, our method surpasses previous approaches by achieving the optimal balanced order of $\Theta(\sqrt{n})$. Additionally, we extend our method to the non-binary case considering $q$-ary almost polarity-balanced sequences for even $q$, and almost symbol-balanced for $q=4$. Our work marks the first asymptotically optimal solutions for almost-balanced sequences, for both, binary and non-binary alphabet.<|reference_end|>
@article{bar-lev2024optimal,
    title={Optimal Almost-Balanced Sequences},
    author={Daniella Bar-Lev, Adir Kobovich, Orian Leitersdorf, Eitan Yaakobi},
    journal={arXiv preprint arXiv:2405.08625},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08625},
    primaryClass={cs.IT math.IT}
}