TY - GEN
T1 - Exact Completeness of LP Hierarchies for Linear Codes
AU - Coregliano, Leonardo Nagami
AU - Jeronimo, Fernando Granha
AU - Jones, Chris
N1 - Publisher Copyright:
© Leonardo Nagami Coregliano, Fernando Granha Jeronimo, and Chris Jones; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - 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.
AB - 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.
KW - combinatorial polytopes
KW - Delsarte's LP
KW - linear codes
KW - LP bound
KW - pseudoexpectation
UR - http://www.scopus.com/inward/record.url?scp=85147550656&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147550656&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.40
DO - 10.4230/LIPIcs.ITCS.2023.40
M3 - Conference contribution
AN - SCOPUS:85147550656
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Y2 - 10 January 2023 through 13 January 2023
ER -