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
| CREATOR | Dion Gijswijt, Sven Polak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01932