Multi view linear programming improves bounds on locally recoverable codes
Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability
Information Theory
Summary
Locally recoverable codes help store data so that lost parts can be fixed by looking at small pieces of the data. This paper improves how we measure the best possible size of such codes when multiple recovery options are available. The authors create a new mathematical method using several ‘views’ of the code’s structure that gives tighter limits than previous models. They prove these new limits with exact calculations on small example codes, showing this method gives better results than older ones.
What this means in practice
- •For data storage engineers: Design error-correcting codes with better trade-offs on redundancy and repair options for distributed storage systems by using improved bounds on code size.
- •For communication protocol designers: Create more efficient data transmission codes featuring multiple local repair methods informed by tighter theoretical size limits.
Authors
Ming-Hsuan Kang, Maosheng Xiong, Yu Hsuan Hsieh, Po-Wei Lai
Abstract
We develop a multi-view linear-programming framework for locally recoverable codes with arbitrary fixed availability $a$. For any retained order $1 \le s \le a$, the selected helper sets, the recovered coordinate, and their complement form an $(s+2)$-part partition. Recording the Hamming distance on all blocks preserves both compatibility among the selected repair alternatives and their coupling with the remaining coordinates. The resulting joint distribution satisfies centered counting identities, product-Krawtchouk positivity, and collision inequalities from the local-distance condition; for fixed $s$, these constraints give a polynomial-size relaxation for arbitrary, possibly nonlinear, codes over any finite field. Retaining one view recovers the three-block model of our companion paper. We develop the first genuinely multi-view case, $s=2$, in detail and specialize the exact computations to availability $a=2$. The resulting four-block LP projects to both the one-view three-block model and a globally conditioned two-view relaxation, making explicit the information lost by each coarsening. Exact rational primal-dual certificates together with checked constructions prove $M_{\max}(2,8,4,2,2,2)=8$, $M_{\max}(3,7,3,2,2,2)=27$, and $M_{\max}(4,7,3,2,2,2)=64$; in all three cases the four-block bound is strictly stronger than both coarsenings.