Semidefinite lower bounds for covering codes

Journal Article (2026)
Author(s)

Dion Gijswijt (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Sven Polak (Tilburg University)

Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.1109/TIT.2026.3706793 Final published version
More Info
expand_more
Publication Year
2026
Language
English
Research Group
Discrete Mathematics and Optimization
Journal title
IEEE Transactions on Information Theory
Issue number
9
Volume number
72
Pages (from-to)
6599-6614
Page Views
42
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Let Kq(n,r) denote the minimum size of a q-ary covering code of word length n and covering radius r. In other words, Kq(n,r) is the minimum size of a set of q -ary codewords of length n such that the Hamming balls of radius r around the codewords cover the Hamming space {0,ldots ,q-1}n. The special case K3(n,1) is often referred to as the football pool problem, as it is equivalent to finding a set of forecasts on n football matches that is guaranteed to contain a forecast with at most one wrong outcome. In this paper, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on Kq(n,r) via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of q , n , and r.

Files

– Personal use only – Dutch Copyright Act (Article 25fa)
warning

File under embargo until 28-12-2026