Exact Completeness of LP Hierarchies for Linear Codes
summary
Shows that the LP hierarchy for linear binary codes recovers the exact maximum code size once the level reaches level n (previously only known to converge by level n^2). Uses a pseudoprobability reformulation, subspace symmetries, Möbius transforms and multivariate Krawtchouk / partial Fourier constraints to rewrite the program over subspace variables and prove every optimum is a convex combination of actual codes, and that the stronger hierarchy yields a true convex hull of codes.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:20Geometry of discrete spaces
- 1:22Coding Theory
- 4:52What is known
- 7:35Upper bound
- 10:13Relaxation
- 11:06Higher Order
- 12:55Why is this interesting
- 21:54Relaxed program
- 23:10Main Theorem
- 23:28Proof Sketch
- 29:42Polytope
related talks
27mA Student's View of Locally Repairable Codes
18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
34mLocally Recoverable Code Constructions and Some Extensions
33mChordal Structure and Polynomial Systems
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
28mA Unified Approach for Reverse Data Management Problems
19mRamsey Quantifiers in Linear Arithmetics