Document Open Access Logo

Exact Completeness of LP Hierarchies for Linear Codes

Authors Leonardo Nagami Coregliano , Fernando Granha Jeronimo, Chris Jones

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.40.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Author Details

Leonardo Nagami Coregliano
  • Institute for Advanced Study, Princeton, NJ, USA
Fernando Granha Jeronimo
  • Institute for Advanced Study, Princeton, NJ, USA
Chris Jones
  • University of Chicago, Il, USA

Funding

  • Coregliano, Leonardo Nagami: This material is based upon work supported by the National Science Foundation, and by the IAS School of Mathematics.
  • Jeronimo, Fernando Granha: This material is based upon work supported by the National Science Foundation under Grant No. CCF-1900460.
  • Jones, Chris: This material is based upon work supported by the National Science Foundation under Grant No. CCF-2008920.

Acknowledgements

We thank Avi Wigderson for stimulating discussions during the initial phase of this project.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ITCS.2023.40

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
  • Mathematics of computing → Combinatorial optimization
Keywords
  • LP bound
  • linear codes
  • Delsarte’s LP
  • combinatorial polytopes
  • pseudoexpectation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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, volume 215 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 51, 22. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022. Google Scholar
  2. P. Delsarte. An algebraic approach to the association schemes of coding theory, 1973. Google Scholar
  3. Philippe Delsarte and Vladimir I. Levenshtein. Association schemes and coding theory. IEEE Trans. Inform. Theory, 44(6):2477-2504, 1998. Information theory: 1948-1998. URL: https://doi.org/10.1109/18.720545.
  4. Joel Friedman and Jean-Pierre Tillich. Generalized Alon-Boppana theorems and error-correcting codes. SIAM J. Discrete Math., 19(3):700-718, 2005. URL: https://doi.org/10.1137/S0895480102408353.
  5. E.N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31:504-522, 1952. Google Scholar
  6. Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory, 2019. Google Scholar
  7. Chris Jones. Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems. PhD thesis, University of Chicago, 2022. Draft at URL: http://people.cs.uchicago.edu/~csj/publications/PhDThesis.pdf.
  8. Monique Laurent. Strengthened semidefinite programming bounds for codes. Math. Program., 109(2-3, Ser. B):239-261, 2007. URL: https://doi.org/10.1007/s10107-006-0030-3.
  9. László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1-7, 1979. URL: https://doi.org/10.1109/TIT.1979.1055985.
  10. Elyassaf Loyfer and Nati Linial. New lp-based upper bounds in the rate-vs.-distance problem for linear codes, 2022. Google Scholar
  11. F. J. MacWilliams, N. J. A. Sloane, and J.-M. Goethals. The MacWilliams identities for nonlinear codes. Bell System Tech. J., 51:803-819, 1972. URL: https://doi.org/10.1002/j.1538-7305.1972.tb01947.x.
  12. Jessie MacWilliams. A theorem on the distribution of weights in a systematic code. Bell System Tech. J., 42:79-94, 1963. URL: https://doi.org/10.1002/j.1538-7305.1963.tb04003.x.
  13. Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey, Jr., and Lloyd R. Welch. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Inform. Theory, IT-23(2):157-166, 1977. URL: https://doi.org/10.1109/tit.1977.1055688.
  14. M. Navon and A. Samorodnitsky. On Delsarte’s linear programming bounds for binary codes. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 327-336, 2005. Google Scholar
  15. Michael Navon and Alex Samorodnitsky. Linear programming bounds for codes via a covering argument. Discrete Comput. Geom., 41(2):199-207, 2009. URL: https://doi.org/10.1007/s00454-008-9128-0.
  16. Alex Samorodnitsky. On the optimum of Delsarte’s linear program. J. Combin. Theory Ser. A, 96(2):261-287, 2001. URL: https://doi.org/10.1006/jcta.2001.3176.
  17. Alex Samorodnitsky. One more proof of the first linear programming bound for binary codes and two conjectures, 2021. URL: http://arxiv.org/abs/2104.14587.
  18. Alexander Schrijver. A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inform. Theory, 25(4):425-429, 1979. URL: https://doi.org/10.1109/TIT.1979.1056072.
  19. Alexander Schrijver. New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inform. Theory, 51(8):2859-2866, 2005. URL: https://doi.org/10.1109/TIT.2005.851748.
  20. Frank Vallentin. Semidefinite programming bounds for error-correcting codes. CoRR, abs/1902.01253, 2019. URL: http://arxiv.org/abs/1902.01253.
  21. J. H. van Lint. Introduction to coding theory, volume 86 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 1999. URL: https://doi.org/10.1007/978-3-642-58575-3.
  22. R.R. Varshamov. Estimate of the number of signals in error correcting codes. Doklady Akademii Nauk SSSR, 117:739-741, 1957. Google Scholar
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