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.2023.40
URN: urn:nbn:de:0030-drops-175433
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17543/
Go to the corresponding LIPIcs Volume Portal

Coregliano, Leonardo Nagami ; Jeronimo, Fernando Granha ; Jones, Chris

Exact Completeness of LP Hierarchies for Linear Codes

pdf-format:
LIPIcs-ITCS-2023-40.pdf (0.7 MB)

Abstract

Determining the maximum size A₂(n,d) of a binary code of blocklength n and distance d remains an elusive open question even when restricted to the important class of linear codes. Recently, two linear programming hierarchies extending Delsarte’s LP were independently proposed to upper bound A₂^{Lin}(n,d) (the analogue of A₂(n,d) for linear codes). One of these hierarchies, by the authors, was shown to be approximately complete in the sense that the hierarchy converges to A₂^{Lin}(n,d) as the level grows beyond n². Despite some structural similarities, not even approximate completeness was known for the other hierarchy by Loyfer and Linial.
In this work, we prove that both hierarchies recover the exact value of A₂^{Lin}(n,d) at level n. We also prove that at this level the polytope of Loyfer and Linial is integral. Even though these hierarchies seem less powerful than general hierarchies such as Sum-of-Squares, we show that they have enough structure to yield exact completeness via pseudoprobabilities.

BibTeX - Entry

@InProceedings{coregliano_et_al:LIPIcs.ITCS.2023.40,
  author =	{Coregliano, Leonardo Nagami and Jeronimo, Fernando Granha and Jones, Chris},
  title =	{{Exact Completeness of LP Hierarchies for Linear Codes}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17543},
  URN =		{urn:nbn:de:0030-drops-175433},
  doi =		{10.4230/LIPIcs.ITCS.2023.40},
  annote =	{Keywords: LP bound, linear codes, Delsarte’s LP, combinatorial polytopes, pseudoexpectation}
}

Keywords: LP bound, linear codes, Delsarte’s LP, combinatorial polytopes, pseudoexpectation
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI