Improved semidefinite programming bounds for binary codes by split distance enumerations

Pin Chieh Tseng; Ching Yi Lai; Wei Hsuan Yu

doi:10.1109/ISIT50566.2022.9834515

Improved semidefinite programming bounds for binary codes by split distance enumerations

Pin Chieh Tseng, Ching Yi Lai, Wei Hsuan Yu

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

We study the maximum size of a binary code A(n, d) with code length n and minimum distance d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to upper bound A(n, d). We derive additional semidefinite constraints based on a split Terwilliger algebra so that Schrijver's semidefinite programming bounds on A(n, d) can be improved. In particular, we show that A(18, 4) ≤ 6551 and A(19, 4) 13087.

Original language	English
Title of host publication	2022 IEEE International Symposium on Information Theory, ISIT 2022
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3073-3078
Number of pages	6
ISBN (Electronic)	9781665421591
DOIs	https://doi.org/10.1109/ISIT50566.2022.9834515
State	Published - 2022
Event	2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland Duration: 26 Jun 2022 → 1 Jul 2022

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2022-June
ISSN (Print)	2157-8095

Conference

Conference	2022 IEEE International Symposium on Information Theory, ISIT 2022
Country/Territory	Finland
City	Espoo
Period	26/06/22 → 1/07/22

Keywords

binary codes
semidefinite p≤rogram
Terwilliger algebra

Access to Document

10.1109/ISIT50566.2022.9834515

Optimal Spherical Codes and Designs(2/4)
Yu, W.-H. (PI)
1/08/21 → 31/07/22
Project: Research

Cite this

Tseng, P. C., Lai, C. Y., & Yu, W. H. (2022). Improved semidefinite programming bounds for binary codes by split distance enumerations. In 2022 IEEE International Symposium on Information Theory, ISIT 2022 (pp. 3073-3078). (IEEE International Symposium on Information Theory - Proceedings; Vol. 2022-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT50566.2022.9834515

@inproceedings{73e7f097b2b64bc18538cfcd6d62fb5a,

title = "Improved semidefinite programming bounds for binary codes by split distance enumerations",

abstract = "We study the maximum size of a binary code A(n, d) with code length n and minimum distance d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to upper bound A(n, d). We derive additional semidefinite constraints based on a split Terwilliger algebra so that Schrijver's semidefinite programming bounds on A(n, d) can be improved. In particular, we show that A(18, 4) ≤ 6551 and A(19, 4) 13087.",

keywords = "binary codes, semidefinite p≤rogram, Terwilliger algebra",

author = "Tseng, {Pin Chieh} and Lai, {Ching Yi} and Yu, {Wei Hsuan}",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 2022 IEEE International Symposium on Information Theory, ISIT 2022 ; Conference date: 26-06-2022 Through 01-07-2022",

year = "2022",

doi = "10.1109/ISIT50566.2022.9834515",

language = "???core.languages.en_GB???",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3073--3078",

booktitle = "2022 IEEE International Symposium on Information Theory, ISIT 2022",

}

Tseng, PC, Lai, CY & Yu, WH 2022, Improved semidefinite programming bounds for binary codes by split distance enumerations. in 2022 IEEE International Symposium on Information Theory, ISIT 2022. IEEE International Symposium on Information Theory - Proceedings, vol. 2022-June, Institute of Electrical and Electronics Engineers Inc., pp. 3073-3078, 2022 IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, 26/06/22. https://doi.org/10.1109/ISIT50566.2022.9834515

Improved semidefinite programming bounds for binary codes by split distance enumerations. / Tseng, Pin Chieh; Lai, Ching Yi; Yu, Wei Hsuan.
2022 IEEE International Symposium on Information Theory, ISIT 2022. Institute of Electrical and Electronics Engineers Inc., 2022. p. 3073-3078 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2022-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improved semidefinite programming bounds for binary codes by split distance enumerations

AU - Tseng, Pin Chieh

AU - Lai, Ching Yi

AU - Yu, Wei Hsuan

PY - 2022

Y1 - 2022

N2 - We study the maximum size of a binary code A(n, d) with code length n and minimum distance d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to upper bound A(n, d). We derive additional semidefinite constraints based on a split Terwilliger algebra so that Schrijver's semidefinite programming bounds on A(n, d) can be improved. In particular, we show that A(18, 4) ≤ 6551 and A(19, 4) 13087.

AB - We study the maximum size of a binary code A(n, d) with code length n and minimum distance d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to upper bound A(n, d). We derive additional semidefinite constraints based on a split Terwilliger algebra so that Schrijver's semidefinite programming bounds on A(n, d) can be improved. In particular, we show that A(18, 4) ≤ 6551 and A(19, 4) 13087.

KW - binary codes

KW - semidefinite p≤rogram

KW - Terwilliger algebra

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

U2 - 10.1109/ISIT50566.2022.9834515

DO - 10.1109/ISIT50566.2022.9834515

M3 - 會議論文篇章

AN - SCOPUS:85136317332

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 3073

EP - 3078

BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022

Y2 - 26 June 2022 through 1 July 2022

ER -

Improved semidefinite programming bounds for binary codes by split distance enumerations

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Projects

Optimal Spherical Codes and Designs(2/4)

Cite this