Linear Programming Bounds for Locally Recovery Codes II
Abstract
We give a polynomial-size linear programming bound for q-ary all-symbol locally recoverable codes with locality parameters (r,δ), without assuming linearity. The key idea is to keep, for every ordered pair of codewords and every selected recovery view, the joint Hamming weight on the helper set, the recovered coordinate, and the rest of the code -- rather than collapsing this triple into a single distance, as earlier formulations do. Averaging this three-block distribution over recovery views of the same length yields exact identities linking it to the global distance distribution, together with nonnegative product-Krawtchouk constraints that encode locality and spectral positivity simultaneously. The resulting LP has polynomially many variables, its optimum dominates the ordinary Delsarte bound, and an earlier outside-distance formulation, the convex-hull bound of Li--Wei--Xiong, and the dual-based bound of Gruica--Jany--Ravagnani all arise from it as coarser marginals. Exact rational certificates over q=2,3,4 show the bound is strictly stronger than the best of these prior LPs in thirteen of fifteen tested cases, pinning down seven exact maximum code sizes and twelve exact maximum linear dimensions.
Related
- Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability
- Linear programming bounds for binary and ternary LCD Codes
- Alphabet-Dependent Bounds for Pure Quantum (r,ρ)-Locally Recoverable Codes
- Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
- Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
BibTeX
@misc{kang2026linear,
title = {{Linear Programming Bounds for Locally Recovery Codes II}},
author = {Ming-Hsuan Kang and Maosheng Xiong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16044},
eprint = {2609.16044},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16044},
}
RIS
TY - UNPB
TI - Linear Programming Bounds for Locally Recovery Codes II
AU - Ming-Hsuan Kang
AU - Maosheng Xiong
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.16044
UR - https://arxiv.org/abs/2609.16044
AB - We give a polynomial-size linear programming bound for q-ary all-symbol locally recoverable codes with locality parameters (r,δ), without assuming linearity. The key idea is to keep, for every ordered pair of codewords and every selected recovery view, the joint Hamming weight on the helper set, the recovered coordinate, and the rest of the code -- rather than collapsing this triple into a single distance, as earlier formulations do. Averaging this three-block distribution over recovery views of the same length yields exact identities linking it to the global distance distribution, together with nonnegative product-Krawtchouk constraints that encode locality and spectral positivity simultaneously. The resulting LP has polynomially many variables, its optimum dominates the ordinary Delsarte bound, and an earlier outside-distance formulation, the convex-hull bound of Li--Wei--Xiong, and the dual-based bound of Gruica--Jany--Ravagnani all arise from it as coarser marginals. Exact rational certificates over q=2,3,4 show the bound is strictly stronger than the best of these prior LPs in thirteen of fifteen tested cases, pinning down seven exact maximum code sizes and twelve exact maximum linear dimensions.
ER -