License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.51
URN: urn:nbn:de:0030-drops-156474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15647/
Coregliano, Leonardo Nagami ;
Jeronimo, Fernando Granha ;
Jones, Chris
A Complete Linear Programming Hierarchy for Linear Codes
Abstract
A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength.
In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features:
1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound.
2) It is a hierarchy of linear programs rather than semi-definite programs potentially making it more amenable to theoretical analysis.
3) It is complete in the sense that the optimum code size can be retrieved from level O(n²).
4) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte’s LP polytopes to approximate the true size of linear codes.
We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higher-order" version taking into account interactions of ? words. Our method also generalizes to translation schemes under mild assumptions.
BibTeX - Entry
@InProceedings{coregliano_et_al:LIPIcs.ITCS.2022.51,
author = {Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris},
title = {{A Complete Linear Programming Hierarchy for Linear Codes}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {51:1--51:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15647},
URN = {urn:nbn:de:0030-drops-156474},
doi = {10.4230/LIPIcs.ITCS.2022.51},
annote = {Keywords: Coding theory, code bounds, convex programming, linear programming hierarchy}
}
|
Keywords: |
|
Coding theory, code bounds, convex programming, linear programming hierarchy |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
