Optimization Online


Semidefinite code bounds based on quadruple distances

Dion C. Gijswijt (dion.gijswijt***at***gmail.com)
Hans D. Mittelmann (mittelmann***at***asu.edu)
Alexander Schrijver (lex***at***cwi.nl)

Abstract: Let A(n, d) be the maximum number of 0, 1 words of length n, any two having Hamming distance at least d. We prove A(20, 8) = 256, which implies that the quadruply shortened Golay code is optimal. Moreover, we show A(18, 6) ≤ 673, A(19, 6) ≤ 1237, A(20, 6) ≤ 2279, A(23, 6) ≤ 13674, A(19, 8) ≤ 135, A(25, 8) ≤ 5421, A(26, 8) ≤ 9275, A(21, 10) ≤ 47, A(22, 10) ≤ 84, A(24, 10) ≤ 268, A(25, 10) ≤ 466, A(26, 10) ≤ 836, A(27, 10) ≤ 1585, A(25, 12) ≤ 55, and A(26, 12) ≤ 96. The method is based on the positive semidefiniteness of matrices derived from quadruples of words. This can be put as constraint in a semidefinite program, whose optimum value is an upper bound for A(n, d). The order of the matrices involved is huge. However, the semidefinite program is highly symmetric, by which its feasible region can be restricted to the algebra of matrices invariant under this symmetry. By block diagonalizing this algebra, the order of the matrices will be reduced so as to make the program solvable with semidefinite programming software in the above range of values of n and d.

Keywords: binary codes, upper bounds, semidefinite programming

Category 1: Combinatorial Optimization (Other )

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


Download: [PDF]

Entry Submitted: 05/21/2010
Entry Accepted: 05/21/2010
Entry Last Modified: 01/07/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society