CS Paper Radar

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

Rui-Juan Jing, Laigang Guo, Yan-Feng Xie, Chun-Ming Yuan

cs.IT ·submitted 2026-11-13 05:24 UTC · v1
publishedtheory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Storage-Repair-Bandwidth Tradeoffs for $(6,5,5)$ and $(7,6,6)$ Exact-Repair Regenerating Codes

cs.IT ·2026-10-20 ·Chao Tian
similarity 0.73
Abstract

This note provides exact information-theoretic outer bounds that completely characterize the storage-repair-bandwidth tradeoff regions for the cases $(n,k,d)=(6,5,5)$ and $(7,6,6)$. The layered code proposed by Tian et al. achieves the tradeoff and is thus optimal. GPT-6 Astra assisted in the discovery of these bounds, based on a new conditioning argument and a structured search over the restricted subsets of entropy linear program constraints. The proofs are given as exact integer-valued certificates, which are difficult for direct human verification, and a Python verifier is included as part of the package, together with the certificates.

0.46

Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime

cs.IT ·2026-10-11 ·Songping Ge, Han Cai, Xiaohu Tang
similarity 0.66
Abstract · 26 pages, 1 figure

Code conversion changes the parameters of encoded data while avoiding complete decoding and re-encoding. Existing general bounds largely rely on the algebraic structure of linear codes. This paper develops an information-theoretic framework for nonlinear code conversion in the merge regime. Using the entropy/length profile (ELP), we derive upper bounds on the number of unchanged symbols and lower bounds on the number of read symbols for arbitrary $(n,M)_q$ codes, without assuming linearity or requiring $\log_q M$ to be an integer. We also obtain joint bounds for multiple initial codes and consequences involving minimum distance. For linear codes, the proposed bounds reduce to the corresponding generalized Hamming weight (GHW) bounds. The construction based on Hamming codes converts Hamming codes of redundancy two into a Hamming code of any larger redundancy and simultaneously attains the general bounds on unchanged and read symbols. The construction based on quasigroups shows that new bounds remain tight for genuinely nonlinear codes of nonintegral dimension and at a nonintegral entropy threshold, which, to the best of our knowledge, is the first construction of convertible codes for nonlinear codes.

0.29

Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability

cs.IT math.CO ·2026-09-30 ·Ming-Hsuan Kang, Maosheng Xiong, Yu Hsuan Hsieh, Po-Wei Lai
similarity 0.65
Abstract · 16 pages, 2 tables

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.

0.19

On Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.61
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes

cs.IT ·2026-10-21 ·Zihao Zhang, Guodong Li, Sihuang Hu
theory similarity 0.61
Abstract

MDS array codes achieve optimal storage efficiency in distributed storage systems, but their repair bandwidth depends critically on the sub-packetization level. While the theoretically optimal repair bandwidth (i.e., cut-set bound) of a high-rate exact-repair MDS array code is attainable with sufficiently large sub-packetization, the fundamental limits for fixed sub-packetization remain poorly understood. We study this problem for centralized linear exact repair of $h$ failures from $d$ helper nodes over a fixed finite field. We show that the rank profile of any linear repair scheme is constrained by two auxiliary mixed-alphabet codes. The first code is formed from the kernels of the helper projections and exists for all repair degrees; the second is formed from their row spaces and applies in the full-helper regime when $d\ge r$. These codes have complementary alphabet profiles, and their size and minimum-distance requirements are forced solely by the MDS property and repair correctness. This gives a unified route from classical coding-theoretic upper bounds to repair-bandwidth lower bounds. As a consequence, we obtain several explicit lower bounds via Singleton, Hamming, Plotkin, and Griesmer arguments, including known bounds as corollaries. We further formulate a Delsarte-type support-enumerator LP for mixed-alphabet codes and give an exact type-compressed implementation. For fixed sub-packetization \(\ell\), this yields a polynomial-time procedure for evaluating the resulting finite-parameter lower bound.

0.22

Generalized Hamming weights of codes arising from complete intersection

cs.IT math.AC ·2026-08-20 ·Eduardo Camps Moreno, Flavio Salizzoni, Rodrigo San-José
similarity 0.61
Abstract · 5 pages

We provide a positive answer to a conjecture proposed by Tohǎneanu and Van Tuyl regarding the minimum distance of codes whose underlying set of points is a reduced complete intersection. Despite the technical nature of the conjecture, we show that it follows directly from a not-well-known refinement of the classical Bézout bound for overdetermined polynomial systems. For completeness, this paper presents a self-contained proof of this refined bound. Furthermore, we show that using the same approach, it is possible to obtain a bound on the generalized Hamming weights of such a code and, more generally, to control the minimum distance of the codes obtained by evaluating forms of degree $d$ on the points of a zero-dimensional complete intersection.

0.33

Strengthening Recursive Constructions for Zero-Error Shannon Capacity

cs.IT cs.LGmath.CO ·2026-08-31 ·Ravi Tandon
theory similarity 0.60
Abstract

The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle $C_5$, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle $C_7$, we obtain an independent set in $C_7^{\boxtimes 500}$ yielding $Θ(C_7)\ge 3.25883262\ldots$, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.

0.47

Upper Bounds for CSP Non-redundancy via Locally Decodable Codes

cs.DM cs.CCcs.ITmath.CO ·2026-10-28 ·Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie +2 more
similarity 0.60
Abstract · 24 pages

In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.

0.12