Exact Completeness of LP Hierarchies for Linear Codes

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Determining the maximum size A2(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 ALin2 (n,d) (the analogue of A2(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 ALin2 (n,d) as the level grows beyond n2. 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 ALin2 (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.

Original languageEnglish (US)
Title of host publication14th Innovations in Theoretical Computer Science Conference, ITCS 2023
EditorsYael Tauman Kalai
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772631
DOIs
StatePublished - Jan 1 2023
Externally publishedYes
Event14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States
Duration: Jan 10 2023Jan 13 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume251
ISSN (Print)1868-8969

Conference

Conference14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/TerritoryUnited States
CityCambridge
Period1/10/231/13/23

Keywords

  • combinatorial polytopes
  • Delsarte's LP
  • linear codes
  • LP bound
  • pseudoexpectation

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Exact Completeness of LP Hierarchies for Linear Codes'. Together they form a unique fingerprint.

Cite this