论文标题
线性代码的LP层次结构的确切完整性
Exact Completeness of LP Hierarchies for Linear Codes
论文作者
论文摘要
确定最大尺寸$ a_2（n，d）的二进制代码，即二进制代码$ n $和距离$ d $，即使仅限于重要的线性代码类别，也仍然是一个难以捉摸的打开问题。最近，将两个线性编程层次结构扩展到了Delsarte的LP，将其独立提出到上限$ a_2^{\ text {lin}}}（n，d）$（线性代码的$ a_2（n，d）$的模拟）。这些层次结构之一，作者被证明是近似完成的，因为层次结构收敛到$ a_2^{\ text {lin}}}}（n，d）$，因为级别的增长超过$ n^2 $。尽管有一些结构相似性，但loyfer and Linial的其他层次结构也不是近似完整性。 在这项工作中，我们证明两个层次结构都恢复了$ a_2^{\ text {lin}}}}（n，d）$的确切值。我们还证明，在这个层面上，Loyfer和Linial的多元层是积分的。尽管这些层次结构似乎不如一般的层次结构（如平方之和平方）强大，但我们表明它们具有足够的结构来通过伪预科产生精确的完整性。
Determining the maximum size $A_2(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_2^{\text{Lin}}(n,d)$ (the analogue of $A_2(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_2^{\text{Lin}}(n,d)$ as the level grows beyond $n^2$. 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_2^{\text{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.
