Semidefinite lower bounds for covering codes
Dion Gijswijt (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Sven Polak (Tilburg University)
More Info
expand_more
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
File under embargo until 28-12-2026