Search Results

Documents authored by Coregliano, Leonardo Nagami

Document
DOI: 10.4230/LIPIcs.ITCS.2023.40
Exact Completeness of LP Hierarchies for Linear Codes

Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.
Cite as

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. Exact Completeness of LP Hierarchies for Linear Codes. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITCS.2023.40},
  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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.51
A Complete Linear Programming Hierarchy for Linear Codes

Authors: Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

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.
Cite as

Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones. A Complete Linear Programming Hierarchy for Linear Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 51:1-51:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITCS.2022.51},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact