We give a hierarchy of semidefinite upper bounds for the maximum size $A(n,d)$ of a binary code of word length $n$ and minimum distance at least $d$. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in $n$; this is based on a result of Schrijver (2004b) about the regular $*$-representation for matrix $*$-algebras. The Delsarte bound for $A(n,d)$ is the first bound in the hierarchy, and the new bound of Schrijver (2004a) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with $O(n^7)$ variables and thus seems out of reach for interesting values of $n$, Schrijver’s bound can be computed via a semidefinite program of size $O(n^3)$, a result which uses the explicit block-diagonalization of the Terwiliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity.
Citation
Unpublished, preprint, CWI, Amsterdam, January 2005