We propose several new lower bounds on the bandwidth cost of MDS convertible codes using a linear-algebraic framework. The derived bounds improve previous results in certain parameter regimes and match the bandwidth cost of the construction proposed by Maturana and Rashmi (2022 IEEE International Symposium on Information Theory) for rF≤rI≤kF, implying that our bounds are tight in this case.

Maximum distance separable (MDS) codes are widely used in distributed storage systems as they provide optimal fault tolerance for a given amount of storage overhead. The seminal work of Dimakis~\emph{et al.} first established a lower bound on the repair bandwidth for a single failed node of MDS codes, known as the \emph{cut-set bound}. MDS codes that achieve this bound are called minimum storage regenerating (MSR) codes. Numerous constructions and theoretical analyses of MSR codes reveal that they typically require exponentially large sub-packetization levels, leading to significant disk I/O overhead. To mitigate this issue, many studies explore the trade-offs between the sub-packetization level and repair bandwidth, achieving reduced sub-packetization at the cost of suboptimal repair bandwidth. Despite these advances, the fundamental question of determining the minimum repair bandwidth for a single failure of MDS codes with fixed sub-packetization remains open. In this paper, we address this challenge for the case of two parity nodes ($n-k=2$) and sub-packetization $\ell=2$. Under these parameters, we establish a correspondence between repair schemes and point sets on the projective line $\mathbb{P}^1$, and then derive a lower bound on repair bandwidth utilizing the sharply 3-transitive action of $\text{PGL}_2(\Fq)$. Furthermore, we extend this lower bound to the repair I/O, and construct two classes of explicit MDS array codes that achieve these bounds, offering practical code designs with provable repair efficiency.

The error coefficient of a linear code, defined as the number of its minimum weight codewords, is a key performance metric to evaluate codes with a given length, dimension, and minimum distance. In this paper, we propose novel approaches, different from existing methods, to produce three new families of binary optimal linear codes with the smallest possible error coefficients. These codes are known as asymptotic frame error rate (AFER)-optimal codes, achieving the best known performance in the additive white Gaussian noise channel and under maximum-likelihood decoding. In particular, we solve a conjecture originally proposed by Li et al. in (IEEE Trans. Inf. Theory 71(7): 5144-5153, 2025).

The error coefficient of a linear code, defined as the number of minimum-weight codewords, plays a central role in evaluating the performance of the code. In this paper, we establish two recursive bounds on the minimum possible error coefficient among optimal linear codes with prescribed parameters. We prove that these bounds are tight in infinitely many cases by constructing two explicit infinite families of optimal linear codes that attain them with equality, and we further show that MDS codes also meet one of the proposed bounds with equality. Beyond the recursive-bound framework, we determine the minimum possible error coefficient for three explicit families of optimal linear codes: two families arising from simplex codes and one family associated with MacDonald codes. Moreover, employing tools from combinatorial design theory, we solve a problem proposed by Guanet al.[12] on the eventual constancy of the minimum error coefficient of optimal codes.

In this paper, we focus on Singleton-optimal$(r,\delta)$LRCs with disjoint local repair groups. We provide an improved bound for the length of q-ary Singleton-optimal$(r,\delta)$LRCs based on the parity-check matrix approach. Specifically, for$d \geq 3\delta $, we prove that$n\le O(q^{\delta })$when$d-3\delta \lt r\le d-2\delta +1$. We also show that the code length$n\le q+\delta +2$when$r=2$and$d=3\delta +2$. We present a sufficient and necessary condition for the existence of Singleton-optimal$(n,k,d;r,\delta)$LRCs with disjoint local repair groups, where the minimum distance satisfies$3\delta +1\le d \le 3\delta +2$and locality$r=2$. This condition imposes an upper bound on the code length,$n\le O(q^{2})$, and indicates the existence of a code length approximately given by$n\approx \sqrt {2}q$when$d=3\delta +1$and$r=2$. Finally, we utilize blocking sets to provide a general construction of Singleton-optimal$(n,k,d=2\delta +2,r=2,\delta)$LRC with code length$n\approx O\left ({{q^{\frac {h+1}{h}}}}\right)$for any$h\ge 3$. To the best of our knowledge, this is the first family of Singleton-optimal$(n,k,d=2\delta +2,r=2,\delta)$LRC with super-linear code length.

We address the multi-node failure repair challenges for MDS array codes. Presently, two primary models are employed for multi-node repairs: the centralized model where all failed nodes are restored in a singular data center, and the cooperative model where failed nodes acquire data from auxiliary nodes and collaborate amongst themselves for the repair process. This paper focuses on the cooperative model, and we provide explicit constructions of optimal MDS array codes withdhelper nodes under this model. The sub-packetization level of our new codes is$(d-k+h)(d-k+1)^{\lceil n/2 \rceil }$wherehis the number of failed nodes,kthe number of information nodes, andnthe code length. This improves upon recent constructions by Liu et al. (IEEE Transactions on Information Theory, Vol. 69, 2023).

The sub-packetization$\ell$and the field size$q$are of paramount importance in MSR code constructions. For optimal-access MSR codes, Balaji et al. proved that$\ell\geq s^{\lceil n/s\rceil}$, where$s= d-k+1$. Rawat et al. showed that this lower bound is attainable for all admissible values of$d$when the field size is exponential in$n$. After that, tremendous efforts have been devoted to reducing the field size. However, so far, reduction to a linear field size is only available for$d\in\{k+1, k+2, k+3\}$and$d=n-1$. In this paper, we construct the first class of explicit ontimal-access MSR codes with the smallest sub-packetization$\ell=s^{\lceil n/s\rceil}$for all$d$between$k+1$and$n-1$, resolving an open problem in the survey (Ramkumar et al., Foundations and Trends in Communications and Information Theory: Vol. 19: No. 4). We further propose another class of explicit MSR code constructions (not optimal-access) with an even smaller sub-packetization$s^{\lceil n/(s+1)\rceil}$for all admissible values of$d$, making significant progress on another open problem in the survey. Previously, MSR codes with$\ell= s^{\lceil n/(s+1)\rceil}$and$q=O(n)$were only known for$d=k+1$and$d=n-1$. The key insight that enables a linear field size in our construction is to reduce$\binom{n}{r}$global constraints of non-vanishing determinants to$O_{s}(n)$local ones, which is achieved by carefully designing a group of kernel matrices and then blowing them up to get parity check submatrices.

We address the multi-node failure repair challenges for MDS array codes. Presently, two primary models are employed for multi-node repairs: the centralized model where all failed nodes are restored in a singular data center, and the cooperative model where failed nodes acquire data from auxiliary nodes and collaborate amongst themselves for the repair process. This paper focuses on the cooperative model, and we provide explicit constructions of optimal MDS codes with$d=k+1$helper nodes under this model. The sub-packetization level of our new codes is$(h+1)2^{\lceil n/2\rceil}$where$h$is the number of failed nodes and$n$is the code length. This improves upon recent constructions given by Liu et. al. (IEEE Transactions on Information Theory, Vol. 69, 2023).

An$(n, k, \ell)$array code has k information coordinates and$r = n - k$parity coordinates, where each coordinate is a vector in$\mathbb {F}_{q}^{\ell }$for some finite field$\mathbb {F}_{q}$. An$(n, k, \ell)$MDS array code has the additional property that any k out of n coordinates suffice to recover the whole codeword. Dimakis et al. considered the problem of repairing the erasure of a single coordinate and proved a lower bound on the amount of data transmission that is needed for the repair. A minimum storage regenerating (MSR) code with repair degree d is an MDS array code that achieves this lower bound for the repair of any single erased coordinate from any d out of$n-1$remaining coordinates. An MSR code has the optimal access property if the amount of accessed data is the same as the amount of transmitted data in the repair procedure. The sub-packetization$\ell $and the field size q are of paramount importance in MSR code constructions. For optimal-access MSR codes, Balaji et al. proved that$\ell \geq s^{\left \lceil {{ n/s }}\right \rceil }$, where$s = d-k+1$. Rawat et al. showed that this lower bound is attainable for all admissible values of d when the field size is exponential in n. After that, tremendous efforts have been devoted to reducing the field size. However, so far, reduction to a linear field size is only available for$d\in \{k+1,k+2,k+3\}$and$d=n-1$. In this paper, we construct the first class of explicit optimal-access MSR codes with the smallest sub-packetization$\ell = s^{\left \lceil {{ n/s }}\right \rceil }$for all d between$k+1$and$n-1$, resolving an open problem in the survey (Ramkumar et al., Foundations and Trends in Communications and Information Theory: Vol. 19: No. 4). We further propose another class of explicit MSR code constructions (not optimal-access) with an even smaller sub-packetization$s^{\left \lceil {{ n/(s+1)}}\right \rceil }$for all admissible values of d, making significant progress on another open problem in the survey. Previously, MSR codes with$\ell =s^{\left \lceil {{ n/(s+1)}}\right \rceil }$and$q=O(n)$were only known for$d=k+1$and$d=n-1$. The key insight that enables a linear field size in our construction is to reduce$\binom {n}{r}$global constraints of non-vanishing determinants to$O_{s}(n)$local ones, which is achieved by carefully designing the parity check matrices.

ABS polar codes were recently proposed to speed up polarization by swapping certain pairs of adjacent bits after each layer of polar transform. In this paper, we observe that applying the Arıkan transform$(U_{i}, U_{i+1}) \mapsto (U_{i}+U_{i+1}, U_{i+1})$on certain pairs of adjacent bits after each polar transform layer leads to even faster polarization. In light of this, we propose ABS+ polar codes which incorporate the Arıkan transform in addition to the swapping transform in ABS polar codes. In order to efficiently construct and decode ABS+ polar codes, we derive a new recursive relation between the joint distributions of adjacent bits through different layers of polar transforms. Simulation results over a wide range of parameters show that the CRC-aided SCL decoder of ABS+ polar codes improves upon that of ABS polar codes by$0.1 \mathop {\mathrm {dB}}\nolimits $–$0.25 \mathop {\mathrm {dB}}\nolimits $while maintaining the same decoding time. Moreover, ABS+ polar codes improve upon standard polar codes by$0.2 \mathop {\mathrm {dB}}\nolimits $–$0.45 \mathop {\mathrm {dB}}\nolimits $when they both use the CRC-aided SCL decoder with list size 32. The implementations of all the algorithms in this paper are available athttps://github.com/PlumJelly/ABS-Polar

ABS polar codes were recently proposed to speed up polarization by swapping certain pairs of adjacent bits after each layer of polar transform. In this paper, we observe that applying the Arıkan transform (Ui, Ui+1) ↦ (Ui+ Ui+1, Ui+1) on certain pairs of adjacent bits after each polar transform layer leads to even faster polarization.In light of this, we propose ABS+ polar codes which incorporate the Arıkan transform in addition to the swapping transform in ABS polar codes. In order to efficiently construct and decode ABS+ polar codes, we derive a new recursive relation between the joint distributions of adjacent bits through different layers of polar transforms. Simulation results over a wide range of parameters show that the CRC-aided SCL decoder of ABS+ polar codes improves upon that of ABS polar codes by 0.1 dB–0.25 dB while maintaining the same decoding time. Moreover, ABS+ polar codes improve upon standard polar codes by 0.2 dB–0.45 dB when they both use the CRC-aided SCL decoder with list size 32.

Locally repairable codes (LRCs) have attracted a lot of attentions due to their applications in distributed storage systems. In this paper, we provide new constructions of optimal (2, δ)-LRCs. Firstly, by the techniques of finite geometry, we present a sufficient condition to guarantee a punctured simplex code to be a (2, δ)-LRC. Secondly, by using characteristic sums over finite fields and Krawtchouk polynomials, we construct several families of LRCs with new parameters. All of our new LRCs are optimal with respect to the generalized Cadambe-Mazumdar bound.

Let${\mathbb F}_{p}$be a prime field and let$\mathbb {F}_{q}$be a larger finite field obtained from adjoining an element$\alpha $to${\mathbb F}_{p}$, i.e.,$\mathbb {F}_{q}= {\mathbb F}_{p}(\alpha)$. We consider polar codes constructed from the$2\times 2$kernel$\begin{aligned} \begin{bmatrix} 1 & 0 \\ \alpha & 1 \end{bmatrix} \end{aligned}$over$\mathbb {F}_{q}$. We prove that for any$\mathbb {F}_{q}$-symmetric memoryless channel, any code length, and any code dimension, all the codeword symbols in such polar codes have the same symbol error rate (SER) under the successive cancellation (SC) decoder.

The construction of polar codes with code length$n=2^{m}$involves$m$layers of polar transforms. In this paper, we observe that after each layer of polar transforms, one can swap certain pairs of adjacent bits to accelerate the polarization process. More precisely, if the previous bit is more reliable than its next bit under the successive decoder, then switching the decoding order of these two adjacent bits will make the reliable bit even more reliable and the noisy bit even noisier. Based on this observation, we propose a new family of codes called the Adjacent-Bits-Swapped (ABS) polar codes. We add a permutation layer after each polar transform layer in the construction of the ABS polar codes. In order to choose which pairs of adjacent bits to swap in the permutation layers, we rely on a new polar transform that combines two independent channels with 4-ary inputs. This new polar transform allows us to track the evolution of every pair of adjacent bits through different layers of polar transforms, and it also plays an essential role in the successive cancellation list (SCL) decoder for the ABS polar codes. Extensive simulation results show that ABS polar codes consistently outperform standard polar codes by$0.15 \mathop {\mathrm {dB}}\nolimits $—$0.3 \mathop {\mathrm {dB}}\nolimits $when we use CRC-aided SCL decoder with list size 32 for both codes. The implementations of all the algorithms in this paper are available athttps://github.com/PlumJelly/ABS-Polar

Wang et al. (IEEE Transactions on Information Theory, vol. 62, no. 8, 2016) proposed an explicit construction of an$(n=k+2,k)$Minimum Storage Regenerating (MSR) code with 2 parity nodes and subpacketization$2^{k/3}$. The number of helper nodes for this code is$d=k+1=n-1$, and this code has the smallest subpacketization among all the existing explicit constructions of MSR codes with the same$n,k$and$d$. In this paper, we present a new construction of MSR codes for a wider range of parameters. More precisely, we still fix$d=k+1$, but we allow the code length$n$to be any integer satisfying$n\ge k+2$. The field size of our code is linear in$n$, and the subpacketization of our code is$2^{n/3}$. This value is slightly larger than the subpacketization of the construction by Wang et al. because their code construction only guarantees optimal repair for all the systematic nodes while our code construction guarantees optimal repair for all nodes.

The famous Barnes–Wall lattices can be obtained by applying Construction D to a chain of Reed–Muller codes. By applying Construction${\text {D}}^{\text {(cyc)}}$to a chain of extended cyclic codes sandwiched between Reed–Muller codes, Hu and Nebe (J. London Math. Soc.(2)101 (2020) 1068-1089) constructed new series of universally strongly perfect lattices sandwiched between Barnes–Wall lattices. In this paper, we first extend their construction to generalized Reed–Muller codes, and then explicitly determine the minimum vectors of those new sandwiched Reed–Muller codes for some special cases.

Wang et al. (IEEE Transactions on Information Theory, vol. 62, no. 8, 2016) proposed an explicit construction of an (n = k + 2, k) Minimum Storage Regenerating (MSR) code with 2 parity nodes and subpacketization 2k/3. The number of helper nodes for this code is d = k + 1 = n − 1, and this code has the smallest subpacketization among all the existing explicit constructions of MSR codes with the same n, k and d. In this paper, we present a new construction of MSR codes for a wider range of parameters. More precisely, we still fix d = k+1, but we allow the code length n to be any integer satisfying n ⩾ k + 2. The field size of our code is linear in n, and the subpacketization of our code is 2n/3. This value is slightly larger than the subpacketization of the construction by Wang et al. because their code construction only guarantees optimal repair for all the systematic nodes while our code construction guarantees optimal repair for all nodes.

The construction of polar codes with code length n = 2minvolves m layers of polar transforms. In this paper, we observe that after each layer of polar transforms, one can swap certain pairs of adjacent bits to accelerate the polarization process. More precisely, if the previous bit is more reliable than its next bit under the successive decoder, then switching the decoding order of these two adjacent bits will make the reliable bit even more reliable and the noisy bit even noisier.Based on this observation, we propose a new family of codes called the Adjacent-Bits-Swapped (ABS) polar codes. We add a permutation layer after each polar transform layer in the construction of the ABS polar codes. In order to choose which pairs of adjacent bits to swap in the permutation layers, we rely on a new polar transform that combines two independent channels with 4-ary inputs. This new polar transform allows us to track the evolution of every pair of adjacent bits through different layers of polar transforms, and it also plays an essential role in the Successive Cancellation List (SCL) decoder for the ABS polar codes. Extensive simulation results show that ABS polar codes consistently outperform standard polar codes by 0.15 dB—0.6 dB when we use CRC-aided SCL decoder with list size 32 for both codes.

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovász theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding.

We investigate the maximal asymptotic rates of length-$n$ binary codes with VC-dimension at most $dn$ and minimum distance at least $\delta n$. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining the Sauer--Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert--Varshamov-type arguments over constant-weight and Markov-type sets.

Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We also show that our bound can be better than Lovász theta number and Haemers minimum rank bound.

We investigate the asymptotic rates of length-n binary codes with VC-dimension at most dn and minimum distance at least δn. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining Sauer-Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert-Varshamov type arguments over constant-weight and Markov-type sets.

Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed ρ-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the p-capacity of arbitrary graphs, and provide a Lovász-type upper bound for regular graphs. We study the behavior of the ρ-capacity under two graph operations: the strong product and the disjoint union. Finally, we investigate the connection between the structure of a graph and its ρ-capacity.

A phase detection sequence is a length-n cyclic sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length-k contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed.

Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed ρ-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the ρ-capacity of arbitrary graphs, and provide a tighter upper bound for regular graphs. The ρ-capacity is employed to characterize the zero-error capacity region of the degraded broadcast channel.

A locally recoverable (LRC) code is a code that enables a simple recovery of an erased symbol by accessing only a small number of other symbols. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature.

We consider the problem of designing a length-n binary sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. We derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. Both adversarial and probabilistic noise models are addressed. Two applications of the problem include fast positioning and card tricks.

The determination of weight distribution of cyclic codes involves the evaluation of Gauss sums and exponential sums. Despite some cases where a neat expression is available, the computation is generally rather complicated. In this note, we determine the weight distribution of a class of reducible cyclic codes whose dual codes may have arbitrarily many zeros. This goal is achieved by building an unexpected connection between the corresponding exponential sums and the spectra of Hermitian forms graphs.