Near-Optimal Covering Sequences

Hoang Ta, Van Khu Vu · 2026

Read Near-Optimal Covering Sequences by Hoang Ta, Van Khu Vu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-29236.txt.

Description

Ta and Vu construct covering sequences that are as short as theory allows, up to a constant factor. A covering sequence is a cyclic string over a finite alphabet whose consecutive windows of fixed length form a covering code. Every possible word lies within a small Hamming distance of some window. Shorter sequences mean more efficient codes.

Earlier probabilistic arguments guaranteed such sequences only with an extra logarithmic factor in length, and earlier explicit constructions covered special cases. Ta and Vu give a deterministic, explicit construction whose length reaches the sphere-covering lower bound within a factor depending only on alphabet size and radius. This holds for every fixed alphabet and radius once the window length is large enough. In the fixed-radius regime, their construction removes the logarithmic factor that random methods left behind.

Catalog record

CREATORHoang Ta, Van Khu Vu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.29236

Browse the full library · About the Tower of Babel