Source-linked AI summary
Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability
Ming-Hsuan Kang, Maosheng Xiong, Yu Hsuan Hsieh, Po-Wei Lai
TL;DR
Existing coarsenings lose either compatibility between repair views or their coupling to coordinates outside those views. The paper develops a multi-view distance-distribution LP and shows that its four-block form is strictly stronger than both comparison relaxations in three availability-two cases.
Problem
Treating repair views independently loses their shared codeword-pair compatibility, while recording only their union loses how local Fourier sectors extend outside the views.
Source: §1 · p. 2Method
The paper organizes repair information in an (s + 2)-block distance distribution, imposing centered identities, product-Krawtchouk positivity, and collision inequalities to obtain a polynomial-size relaxation for fixed s.
Source: §1 · pp. 2–3, §2 · p. 4Results
The four-block LP is strictly stronger than both comparison relaxations in all three availability-two cases, including Mmax(4, 7, 3, 2, 2, 2) = 64.
Source: §1 · p. 3, §4 · p. 12Takeaways & Limitations
At s = 2, both losing a helper block as a separate view and forgetting the positive outside spectrum can weaken the bound.
Source: §5 · p. 14The hierarchy remains a two-codeword relaxation and omits repair-set intersections across recovered coordinates, helper-set coordinate labels, and cross-coordinate compatibility.
Source: §5 · p. 14
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends a single-view distance-distribution LP to a hierarchy that jointly records multiple repair views and their coupling to the remaining coordinates. Its four-block case yields exact availability-two maxima in three alphabets and is strictly stronger than both coarsenings in those examples.
1 Introduction
- For retained order s, the s + 2-block statistic records distances on each helper set, the recovered coordinate, and their complement, with polynomial-size constraints for fixed s.Taking s = 1 recovers the three-block model of [10].Source: §1 · pp. 2–3
- The four-block distribution preserves both same-pair compatibility between two repair views and their coupling to coordinates outside those views.Analyzing views independently loses their shared codeword-pair compatibility; recording only their union loses outside-coordinate coupling.Source: §1 · p. 2
- Centered identities, product-Krawtchouk positivity, and local collision inequalities define the four-block LP and allow objective-preserving projections to two coarser relaxations.The projections are the one-view three-block LP and a conditioned two-view relaxation.Source: §1 · pp. 2–3
- The four-block LP is strictly stronger than both coarsenings in three certified availability-two cases over F2, F3, and F4.Exact rational primal–dual certificates and independently checked constructions determine the maxima.Source: §1 · p. 3
- The bound targets alphabet-dependent finite-length code-size limits for arbitrary, possibly nonlinear codes under local-distance availability, complementing bounds focused on rate, dimension, or minimum distance.The local-distance condition is stronger than functional availability in general, including when δ = 2.Source: §1 · pp. 2–3
2 Code class and preliminaries
The paper studies codes whose disjoint local views each satisfy a local minimum-distance requirement, and develops a retained-order hierarchy of block-distance distributions. For the four-block case, centered identities, spectral positivity, and collision constraints form the LP relaxation.
2 Code class and preliminaries
- For every coordinate, all-symbol local-distance (r, δ, a)-availability requires a selected set of a pairwise disjoint helper sets whose local projections have length at most r + δ − 1 and minimum distance at least δ.Disjointness is required among views for the same recovered coordinate, not between recovery sets attached to different coordinates.Source: §2 · p. 4
- For any retained order 1 ≤ s ≤ a, the natural joint statistic has an s + 2-block distance distribution; s = 1 recovers the three-block model of [10].Taking s = a retains all available repair views.Source: §2 · p. 4
- Each retained local view gives a collision inequality, and every subset of at least two helper sets gives a punctured helper-union inequality.For differing recovered coordinates, each selected helper set contributes at least δ − 1 differences, so a union of at least two has distance at least 2(δ − 1) ≥ δ.Source: §2 · p. 4
- The detailed four-block model assumes a ≥ 2 and fixes an admissible ordered selection of two views; it is valid uniformly for codes with a ≥ 2, while the exact extremal results specialize to a = 2.The code need not be linear, and its minimum distance is at least d.Source: §2 · pp. 3–4
- The four-block LP combines global mass, distance, and transform constraints with nonnegative block variables, centered and support constraints, spectral positivity, and collision rows.The local condition also forces every nonzero codeword difference to have weight at least δ.Source: §2 · pp. 4–5
3 The retained-order s = 2 case: the four-block linear program
The retained-order s = 2 formulation records distances across two helper sets, the recovered coordinate, and the outside block. It combines centered identities, product-Krawtchouk positivity, and local collision inequalities in a four-block LP with projections to two coarser bounds.
3 The retained-order s = 2 case: the four-block linear program
- The four-block LP retains same-pair compatibility between two local views and their extension to coordinates outside the selected views.Its constraints combine exact block distances, the full product-Krawtchouk spectrum, and collision inequalities on both local views and their punctured helper union.Source: §3 · p. 5
3.1 The four-block distribution and centered identities
- Each four-block cell records distances on both helper sets, the recovered coordinate, and the complement, with global distance determined by their sum.Centered counting identities relate these cells to the global distance distribution and impose local and global support zeros.Source: §3.1 · p. 6
3.2 Product-Krawtchouk positivity
- Product-Krawtchouk transforms are nonnegative for every q-ary code, including nonlinear codes, with a separate spectral degree for each block.Positive degrees on the outside block record how a local spectral sector extends globally; setting that degree to zero discards this information.Source: §3.2 · p. 7
3.3 Local collision inequalities
- The LP uses collision constraints for both complete local views and their punctured helper union.The union constraint adds collision information with exponent (t1 + t2 − 2) − δ + 1, reflecting the punctured union's length.Source: §3.3 · p. 9
3.4 The LP and projection hierarchy
- Every eligible code induces a feasible four-block point, and objective-preserving projections yield both the one-view three-block LP and conditioned two-view relaxation.The one-view projection forgets one helper block as a separate view; the conditioned projection retains both helper distances and total distance but discards positive outside spectral degrees.Source: §3.4 · pp. 11–12
4 Exact bounds for availability a = 2
Exact certificates and matching constructions establish availability-two bounds, with the four-block LP strictly stronger than both coarsenings in each certified case. An exploratory scan also found a smaller four-block optimum than the conditioned relaxation in all 20 tested rows, but those values are numerical only.
4 Exact bounds for availability a = 2
- The theorem-level bounds use exact rational primal–dual certificates checked constraint by constraint, with matching constructions checked against the definition and induced constraints.The LP upper bounds do not assume linearity; linearity is used only to describe the attaining constructions compactly.Source: §4 · p. 12
- Mmax(4, 7, 3, 2, 2, 2) = 64, and the four-block LP is strictly stronger than both comparison relaxations in each certified case.The certified LP values and matching construction sizes are summarized in Table 4.1.Source: §4 · p. 12, Table 4.1 · p. 12
- The constructions have row-space sizes 8, 27, and 64, with minimum distances 4, 3, and 4, respectively, and attain the certified four-block upper bounds.The quaternary construction uses Fano columns: each line gives a length-three local projection of distance two, and two lines through a point give disjoint helper pairs.Source: §4 · p. 13
- U4blk < min{UCond, U3blk} holds in all three certified rows.Thus the four-block LP is strictly stronger than either coarsening in these examples.Source: §4 · p. 13
4.1 Broader numerical landscape
- In all 20 exploratory rows, the numerical four-block optimum was strictly smaller than the conditioned optimum.These floating-point outputs are not certified upper bounds; promotion to a theorem requires an exact rational primal–dual certificate and an independently checked construction.Source: §4.1 · pp. 13–14
5 Conclusion
The retained-order hierarchy ranges from the one-view model to retaining all available repair views, while the detailed development centers on two views. The hierarchy remains a two-codeword relaxation and does not retain several forms of cross-coordinate or within-helper compatibility.
5 Conclusion
- At s = 1 the hierarchy is the three-block model, at s = 2 the four-block model, and at s = a it retains all available repair views.The examples show that at s = 2, both the separate helper-block information and the positive outside spectrum can matter.Source: §5 · p. 14
- The detailed treatment focuses on s = 2; larger retained orders have rapidly growing local state spaces and more collision constraints, whose computational effectiveness remains open..Source: §5 · p. 14
- The hierarchy is a two-codeword relaxation that omits intersections across recovered coordinates, helper-set coordinate labels, and compatibility across local configurations at different coordinates.Retaining such data may strengthen the bound but leads to a different, substantially larger optimization problem.Source: §5 · p. 14
Funding
- The work was supported by grants from Taiwan’s National Science and Technology Council and Hong Kong’s Research Grants Council.The listed grants are NSTC 115-2115-M-A49-010 and 16307524, respectively.Source: Funding · p. 14
Data and code availability
The reproducibility repository contains LP builders, exact certificates, construction witnesses, independent checkers, regression tests, and exploratory scans.
Data and code availability
- The repository includes LP builders, exact rational primal–dual certificates, construction witnesses, independent checkers, regression tests, and the complete exploratory scans.Source: Data and code availability · p. 14