Semidefinite lower bounds for covering codes

Dion Gijswijt, Sven Polak · 2025

Read Semidefinite lower bounds for covering codes by Dion Gijswijt, Sven Polak (2025) 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-2504-01932.txt.

Description

Dion Gijswijt and Sven Polak sharpen the math that bounds how small a covering code can be, in a 2025 paper. A covering code is a set of words such that every word sits near one of them. The smallest size for a given length and reach is a long-standing puzzle. One famous case maps to football pools: pick forecasts so that one is sure to miss at most one match.

Gijswijt had built a floor for that size with a method called semidefinite programming, back in 2005. The new work adds stronger rules drawn from a known ladder of relaxations, plus symmetry cuts that shrink the search. A richer goal measure helps as well. The upgrades set fresh records for the floor across a wide range of alphabet sizes, lengths, and reaches. Each record trims the hunt for the true best codes.

Catalog record

CREATORDion Gijswijt, Sven Polak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-01932

Browse the full library · About the Tower of Babel