Title

New code bounds with semidefinite programming

Speaker

Lex Schrijver

CWI and University of Amsterdam

Abstract

The linear programming bound of Delsarte is a classical upper bound on the size of a code of given word length $n$ and minimum distance $d$. We show that with semidefinite programming this bound can be refined, yielding improved upper bounds for concrete values of $n$ and $d$. It corresponds to semidefinite matrix cuts and requires the block-diagonalization of certain algebras.