New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

Dion Gijswijt; Alexander Schrijver; Hajime Tanaka

doi:10.1016/j.jcta.2006.03.010

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

Dion Gijswijt, Alexander Schrijver, Hajime Tanaka

INF - Computer and Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

36 Citations (Scopus)

Abstract

We give a new upper bound on the maximum size A_q (n, d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q ≥ 3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q = 3, 4, 5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.

Original language	English
Pages (from-to)	1719-1731
Number of pages	13
Journal	Journal of Combinatorial Theory. Series A
Volume	113
Issue number	8
DOIs	https://doi.org/10.1016/j.jcta.2006.03.010
Publication status	Published - 2006 Nov

Keywords

Block-diagonalization
Codes
Delsarte bound
Nonbinary codes
Semidefinite programming
Terwilliger algebra
Upper bounds

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jcta.2006.03.010

Cite this

@article{062a7f926d9a42daaf976422f492d96f,

title = "New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming",

abstract = "We give a new upper bound on the maximum size Aq (n, d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q ≥ 3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q = 3, 4, 5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.",

keywords = "Block-diagonalization, Codes, Delsarte bound, Nonbinary codes, Semidefinite programming, Terwilliger algebra, Upper bounds",

author = "Dion Gijswijt and Alexander Schrijver and Hajime Tanaka",

year = "2006",

month = nov,

doi = "10.1016/j.jcta.2006.03.010",

language = "English",

volume = "113",

pages = "1719--1731",

journal = "Journal of Combinatorial Theory - Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "8",

}

TY - JOUR

T1 - New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

AU - Gijswijt, Dion

AU - Schrijver, Alexander

AU - Tanaka, Hajime

PY - 2006/11

Y1 - 2006/11

N2 - We give a new upper bound on the maximum size Aq (n, d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q ≥ 3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q = 3, 4, 5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.

AB - We give a new upper bound on the maximum size Aq (n, d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q ≥ 3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q = 3, 4, 5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.

KW - Block-diagonalization

KW - Codes

KW - Delsarte bound

KW - Nonbinary codes

KW - Semidefinite programming

KW - Terwilliger algebra

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=33748413306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748413306&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2006.03.010

DO - 10.1016/j.jcta.2006.03.010

M3 - Article

AN - SCOPUS:33748413306

SN - 0097-3165

VL - 113

SP - 1719

EP - 1731

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

IS - 8

ER -

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this