CS Paper Radar

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

cs.IT math.CO ·submitted 2026-09-30 08:03 UTC · v1

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.

Comment
16 pages, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Programming Bounds for Locally Recovery Codes II

cs.IT cs.DMmath.CO ·2026-09-12 ·Ming-Hsuan Kang, Maosheng Xiong
similarity 0.80
Abstract · This is a preliminary release. Comments are welcome

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.

0.24

Toward the Minimal Set of Information Inequalities in Regenerating Codes: An Algebraic Approach

cs.IT ·2026-11-13 ·Rui-Juan Jing, Laigang Guo, Yan-Feng Xie, Chun-Ming Yuan
publishedtheory similarity 0.65
Abstract

Information-theoretic outer bounds for exact-repair regenerating codes can be formulated as linear programs, but the associated Shannon-type systems contain many implicit equalities and redundant inequalities. We directly specify a reduced system for the $(n,n-1,n-1)$ exact-repair model using the closure structure induced by its repair dependencies. Nonempty closed sets index the reduced joint-entropy coordinates, and inseparable edges determine the defining inequalities. We prove equivalence with the initial system by characterizing its implicit equalities and establishing sufficient redundancy criteria. We also give an algorithm that constructs the directly defined system for any $n$, count its entropy coordinates, and derive an explicitly computable upper bound on its number of inequalities. For every $n\ge2$, we prove that the reduced system has no implicit equalities and that each distinct defining inequality is nonredundant and defines a facet in the nonempty closed-set coordinate space. Exact enumerations for $n\in\{2,3,4,5\}$ verify the reported system sizes.

0.22

CSS Quantum LRCs with Intersecting Recovery Sets: Constructions and Bounds

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Vinayak Ramkumar, Holger Boche, Rawad Bitar
similarity 0.65
Abstract · Accepted for presentation at the 2026 IEEE Information Theory Workshop (ITW 2026)

In this work, we study $(r,t,x)$ quantum locally recoverable codes (qLRCs) with locality $r$, $t$ recovery sets per qudit, and intersection parameter $x$. We first show that, assuming the underlying classical codes have dual minimum distance at least two, a CSS code is an $(r,t,x)$-qLRC if and only if the underlying classical codes are $(r,t,x)$ classical LRCs (cLRCs) with common recovery sets. We then use subset-inclusion matrices to construct families of binary dual-containing $(r,t,x)$-cLRCs, which yield binary $(r,t,x)$-qLRCs via the CSS construction. For CSS $(r,t,x)$-qLRCs, we derive upper bounds on the dimension and rate, minimum-distance bounds in the pure case, and a Singleton-like dimension bound in the exact case. Finally, we show that these families attain high rates and nontrivial minimum distances.

0.49

On the Length of Maximum Sum-Rank Distance Codes

cs.IT math.CO ·2026-10-16 ·Valentina Astore, Ferdinando Zullo
similarity 0.64
Abstract

The classical theory of arcs in finite projective spaces provides a powerful geometric framework for studying maximum distance separable (MDS) codes and their possible lengths. In this paper, we investigate how this perspective extends to maximum sum-rank distance (MSRD) codes, whose geometric description involves systems of linear sets rather than individual projective points. Our main goal is to understand how the block structure of an MSRD code constrains its length. In dimension three, we determine the possible intersection patterns of lines with the associated linear sets and obtain explicit formulas for their characters and the weight distribution of the corresponding codes. These results lead to new length bounds and show that the block structure comes at a cost: the presence of a block of rank at least two reduces the maximum possible total length by at least $q-1$, and sufficiently long MSRD codes must be classical, that is, MDS codes over $\mathbb F_{q^m}$. We also prove that three-dimensional one-weight MSRD codes do not exist. In arbitrary dimension, we interpret shortening geometrically as projection and establish a general projection bound that extends classical counting arguments for arcs. This yields restrictions depending explicitly on the block profile and, for full-length blocks, identifies parameter ranges in which linearized Reed--Solomon codes attain the maximum possible number of blocks. Finally, we construct an exceptional three-dimensional MSRD code over $\mathbb F_9$ with three blocks of length two and propose a sum-rank analogue of the MDS conjecture.

0.41

Thresholds for Local Coordinate-Wise Linear Properties of Random One-Point AG Codes

cs.IT ·2026-10-08 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.64
Abstract · 37 pages

Local coordinate-wise linear (LCL) properties provide a unified framework for studying list decoding, list recovery and other local properties of linear codes. We prove that random one-point algebraic geometry (AG) codes have the same LCL threshold rates as random linear codes under explicit alphabet and sampling conditions. More precisely, for a family of local profiles with random linear code threshold $R_{\mathcal P}$, a random one-point AG code avoids all such profiles below $R_{\mathcal P}-\varepsilon$ and contains one above $R_{\mathcal P}+\varepsilon$, with explicit failure bounds on both sides. Our proof also removes an auxiliary lower bound on the number of available rational places that arises in a direct adaptation of the Reed--Solomon argument and requires no additional genus-dependent rate gap. We also observe that the previously claimed above threshold proof for random Reed--Solomon codes does not establish the required probability lower bound. The containment relation used in that argument gives the probability comparison in the opposite direction from what is needed. We give a different above threshold argument, which in particular also yields an alternative proof in the genus zero case. Combining our threshold theorem with recent results for random linear codes gives a collection of new list decoding, average weight list decoding and list recovery guarantees for random one-point AG codes. We further obtain new correlated agreement and proximity gap results for polynomial curves. These results extend the LCL threshold framework from random linear and Reed--Solomon codes to random one-point AG codes.

0.18

Entanglement-assisted quantum locally recoverable codes: bounds and constructions with availability

cs.IT quant-ph ·2026-08-10 ·Rutuja Kshirsagar, Gretchen L. Matthews, Julia Shapiro
similarity 0.64
Abstract

In this work, we define entanglement-assisted quantum locally recoverable codes with availability, in which any set of up to $δ-1$ erased qudits can be recovered from any one of $t$ local recovery sets, each of size at most $r+δ-1$, with the recovery sets intersecting exactly in the erased coordinates, where $r$ is a (small) positive integer. We show that shared entanglement permits $t>1$, meaning that multiple local recovery sets can be available for the same set of up to $δ-1$ erasures. We establish a Singleton-like bound for this family of codes and present random constructions based on classical linear codes with Vandermonde parity-check matrices. We also provide explicit constructions of entanglement-assisted quantum locally recoverable codes with availability from several classical code families and their folded versions, including Tamo-Barg codes, fiber-product codes, and algebraic-geometry codes such as one-point Hermitian and Suzuki codes.

0.42

Bounds for Pure Disjoint $(r,δ)$-Quantum Locally Recoverable Codes

cs.IT quant-ph ·2026-08-11 ·Evagoras Stylianou, Holger Boche
publishedtheory similarity 0.64
Abstract · Accepted for presentation at the 2026 IEEE International Symposium on Information Theory (ISIT 2026)

We study pure disjoint $(r,δ)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill--Laflamme conditions for recovery from up to $δ-1$ erasures within a recovery block, and introduce blockwise Shor--Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,δ)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,δ)$-qLRCs.

0.52

Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs

cs.IT ·2026-10-19 ·Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
theory similarity 0.63
Abstract

The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.

0.25