A Complete Linear Programming Hierarchy for Linear Codes
summary
Constructs a family of polynomial-size linear programs (after factoring translation and permutation symmetries) that encode L‑point interactions via configuration profile variables and higher-order Krawtchouk polynomials, proving the hierarchy is complete for linear codes: at roughly level poly(n,1/ε) (sketched as about n^2 times precision factors) the Lth-root of the LP optimum is within 1+ε of the true maximum code size, and exact completeness holds by level n. The non‑linear version collapses and gives no improvement.
AI-written summary · about