Strengthened Semidefinite Bounds for Codes

Monique Laurent (moniquecwi.nl)

Abstract: 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.

Keywords: stability number, binary code, semidefinite bound, Terwiliger algebra

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Unpublished, preprint, CWI, Amsterdam, January 2005

Download: [Postscript]

Entry Submitted: 02/01/2005
Entry Accepted: 02/01/2005
Entry Last Modified: 05/24/2005

Modify/Update this entry