Strengthened semidefinite programming bounds for codes
成果类型：
Article
署名作者：
Laurent, Monique
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-006-0030-3
发表日期：
2007
页码：
239-261
关键词：
摘要：
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 de Klerk et al. (Math Program, 2006) 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 (IEEE Trans. Inform. Theory 51:2859-2866, 2005) 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 Terwilliger algebra. We propose two strengthenings of Schrijver's bound with the same computational complexity.
来源URL：