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.

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

Let ${\mathbf{x}} \in \mathbb{Z}_q^n$ be a length-n sequence over the alphabet ℤq= {0,1, …,q − 1}. A Fixed Length Levenshtein (FLL) ball with radius t and center x consists of all the length-n sequences that can be obtained from performing t insertions and t deletions on x. Such a ball is denoted as $\mathcal{L}_{t}(x)$, and we are interested in the scenario where x is chosen uniformly at random from $\mathbb{Z}_q^n$. For t = 1, Bar-Lev et al. showed that $\mathbb{E}\left[ {\left| {{\mathcal{L}_1}({\mathbf{x}})} \right|} \right] = \left( {q + \frac{1}{q} - 2} \right){n^2} + O(n)$, and it was further proved by Wang and Wang that with high probability over the choice of x, the size of $\mathcal{L}_{1}(\boldsymbol{x})$ is concentrated around its expectation. In this paper, we first give a simple proof of the concentration bound by Wang and Wang for the case of t = 1. Then we move on to the case of t = 2, showing that $\mathbb{E}\left[ {\left| {{\mathcal{L}_2}({\mathbf{x}})} \right|} \right] = \frac{{{{(q - 1)}^4}}}{{4{q^2}}}{n^4} + O\left( {{n^3}} \right)$, and we also establish the concentration around the expectation in this case.

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.

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 cyclically equivariant neural decoder was recently proposed in [Chen-Ye, International Conference on Machine Learning, 2021] to decode cyclic codes. In the same paper, a list decoding procedure was also introduced for two widely used classes of cyclic codes—BCH codes and punctured Reed-Muller (RM) codes. While the list decoding procedure significantly improves the Frame Error Rate (FER) of the cyclically equivariant neural decoder, the Bit Error Rate (BER) of the list decoding procedure is even worse than the unique decoding algorithm when the list size is small. In this paper, we propose an improved version of the list decoding algorithm for BCH codes and punctured RM codes. Our new proposal significantly reduces the BER while maintaining the same (in some cases even smaller) FER. More specifically, our new decoder provides up to 2dB gain over the previous list decoder when measured by BER, and the running time of our new decoder is 15% smaller. Code available at github.com/improvedlistdecoder/code

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.

Let$W$be a binary-input memoryless symmetric (BMS) channel with Shannon capacity$I(W)$and fix any$\alpha > 0$. We construct, for any sufficiently small$\delta > 0$, binary linear codes of block length$O(1/\delta ^{2+\alpha })$and rate$I(W)-\delta $that enable reliable communication on$W$with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established theexistenceof such codes (without efficient constructions or decoding) with block length$O(1/\delta ^{2})$. This quadratic dependence on the gap$\delta $to capacity is known to be best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

Neural decoders were introduced as a generalization of the classic Belief Propagation (BP) decoding algorithms, where the Trellis graph in the BP algorithm is viewed as a neural network, and the weights in the Trellis graph are optimized by training the neural network. In this work, we propose a novel neural decoder for cyclic codes by exploiting their cyclically invariant property. More precisely, we impose a shift invariant structure on the weights of our neural decoder so that any cyclic shift of inputs results in the same cyclic shift of outputs. Extensive simulations with BCH codes and punctured Reed-Muller (RM) codes show that our new decoder consistently outperforms previous neural decoders when decoding cyclic codes. Finally, we propose a list decoding procedure that can significantly reduce the decoding error probability for BCH codes and punctured RM codes. For certain high-rate codes, the gap between our list decoder and the Maximum Likelihood decoder is less than $0.1$dB. Code available at github.com/cyclicallyneuraldecoder

Consider an m-user multiple access channel (MAC) ($X$1,$X_{2},\ \ldots,\ X_{m})\rightarrow\ Y$, where all the Xi's are Bernoulli-l/2 random variables. It is well known that applying the Arikan transform individually to each user leads to MAC polarization. In general, MAC polarization may include many intermediate extremal configurations, in addition to the “almost perfect” and “completely noisy” configurations, and a major open problem in MAC polarization is to identify the proportion of all the extremal configurations. In this paper, we consider two classes of Multiple Access Erasure Channels (MAEC). For the more general class, we identify a necessary and sufficient condition of two-level polarization in the two-user case. This proves a conjecture in [Nasser-Telatar, IEEE Transactions on Information Theory, 2016]. For the other class, we are able to calculate the proportion of the extremal configurations for the m-user case.

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems.

The stochastic block model (SBM) is a random graph model in which the edges are generated according to the underlying cluster structure on the vertices. The (ferromagnetic) Ising model, on the other hand, assigns ±1 labels to vertices according to an underlying graph structure in a way that if two vertices are connected in the graph then they are more likely to be assigned the same label. In SBM, one aims to recover the underlying clusters from the graph structure while in Ising model, an extensively-studied problem is to recover the underlying graph structure based on i.i.d. samples (labelings of the vertices). In this paper, we propose a natural composition of SBM and the Ising model, which we call the Stochastic Ising Block Model (SIBM). In SIBM, we take SBM in its simplest form, where$n$vertices are divided into two equal-sized clusters and the edges are connected independently with probability$p$within clusters and$q$across clusters. Then we use the graph$G$generated by the SBM as the underlying graph of the Ising model and draw$m$i.i.d. samples from it. The objective is to exactly recover the two clusters in SBM from the samples generated by the Ising model, without observing the graph$G$. As the main result of this paper, we establish a sharp threshold$m^\ast $on the sample complexity of this exact recovery problem in a properly chosen regime, where$m^\ast $can be calculated from the parameters of SIBM. We show that when$m\ge m^\ast $, one can recover the clusters from$m$samples in$O(n)$time as the number of vertices$n$goes to infinity. When$m < m^\ast $, we further show that for almost all choices of parameters of SIBM, the success probability of any recovery algorithms approaches 0 as$n\to \infty $.

We address two aspects of the repair problem of Reed-Solomon codes. First, we propose a new repair scheme for the RS codes constructed in [Tamo-Ye-Barg, IEEE Trans. Inf. Theory, May 2019] which in addition to optimal repair bandwidth is also robust to erroneous information provided by the helper nodes. Next, we construct a new family of RS codes with optimal access for the repair of any single failed node. We also prove that any scalar MDS code with optimal repair bandwidth can be furnished with a repair scheme with the optimal access property.

Let W be a binary-input memoryless symmetric (BMS) channel with Shannon capacity I(W) and fix any α > 0. We construct, for any sufficiently small δ > 0, binary linear codes of block length O(1/δ2+α) and rate I(W)−δ that enable reliable communication on W with quasi-linear time encoding and decoding. Shannon’s noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length O(1/δ2). This quadratic dependence on the gap δ to capacity is known to be the best possible. Our result thus yields a constructive version of Shannon’s theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the binary erasure channel.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms using list-decoding. We run our algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) regime for a wide range of code rates. Simulation results show that in both low code rate and high code rate regimes, the new algorithm outperforms the widely used decoder for polar codes (SCL+CRC) with the same parameters. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix Gm= [1110]⊗mbut using different subset of rows. RM codes 1 1 select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in Gm; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arıkan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this article, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows inGm, the conditional mutual information again polarizes. Here “polarization” means that almost all the conditional mutual information becomes either very close to 0 or very close to 1. Polarization itself is a necessary condition for RM codes to achieve capacity on symmetric channels while polarization together with a strong order on the conditional mutual information gives a sufficient condition, where strong order means that rows with larger weight always correspond to larger conditional mutual information. Although we are not able to prove the strong order, we establish a partial order on the conditional mutual information, which is a subset of the strong order. While the main results of this article-polarization together with the partial order-provide some advances on the capacity-achieving conjecture of RM codes, we emphasize that our results do not allow us to prove the conjecture.

Recently Reed-Solomon (RS) codes were shown to possess a repair scheme that supports repair of failed nodes with optimal repair bandwidth. In this paper, we extend this result in two directions. First, we propose a new repair scheme for the RS codes constructed in [Tamo-Ye-Barg, IEEE Transactions on Information Theory, vol. 65, May 2019] and show that repair is robust to erroneous information provided by the helper nodes while maintaining the optimal repair bandwidth. Second, we construct a new family of RS codes with optimal access for the repair of any single failed node. We also show that the constructed codes can accommodate both features, supporting optimal-access repair with optimal error-correction capability. Going beyond RS codes, we also prove that any scalar MDS code with repair bandwidth attaining the cutset bound affords a repair scheme with optimal access property.

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded k data symbols using an (n, k) code with code length n and dimension k. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an α proportion of the corrupted codeword. For a given α, our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read αn coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any ⌊(αn - k)/2⌋ errors. In this paper we show that we can instead download an α proportion from each of the codeword's coordinates. For a well-designed MDS code, this method can guarantee recovery from ⌊(n - k/α)/2⌋ errors, which is 1/α times more than the naive method, and is also the maximum number of errors that an (n, k) code can correct by downloading only an α proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an α proportion of the corrupted codeword.

We consider the problem of multiple-node repair in distributed storage systems under the cooperative model, where the repair bandwidth includes the amount of data exchanged between any two different storage nodes. Recently, explicit constructions of MDS codes with optimal cooperative repair bandwidth for all possible parameters were given by Ye and Barg (IEEE Transactions on Information Theory, 2019). The node size (or sub-packetization) in this construction scales as exp(Θ(nh)), where h is the number of failed nodes and n is the code length. In this paper, we give new explicit constructions of optimal MDS codes for all possible parameters under the cooperative model, and the node size of our new constructions only scales as exp(O(n)) for any number of failed nodes. Furthermore, it is known that any optimal MDS code under the cooperative model (including, in particular, our new code construction) also achieves optimal repair bandwidth under the centralized model, where the amount of data exchanged between failed nodes is not included in the repair bandwidth. We further show that the node size of our new construction is also much smaller than that of the best known MDS code constructions for the centralized model.

Reed-Muller (RM) codes were introduced in 1954 and have long been conjectured to achieve Shannon's capacity on symmetric channels. The activity on this conjecture has recently been revived with the emergence of polar codes. RM codes and polar codes are generated by the same matrix G_m= [1/1 0/1] ^⊗m but using different subset of rows. RM codes select simply rows having largest weights. Polar codes select instead rows having the largest conditional mutual information proceeding top to down in G_m; while this is a more elaborate and channel-dependent rule, the top-to-down ordering allows Arikan to show that the conditional mutual information polarizes, and this gives directly a capacity-achieving code on any symmetric channel. RM codes are yet to be proved to have such a property, despite the recent success for the erasure channel. In this paper, we connect RM codes to polarization theory. We show that proceeding in the RM code ordering, i.e., not top-to-down but from the lightest to the heaviest rows in G_m, the conditional mutual information again polarizes. We further demonstrate that it does so faster than for polar codes. This implies that G_m contains another code, different than the polar code and called here the twin-RM code, that is provably capacity-achieving on any symmetric channel. This gives in particular a necessary condition for RM codes to achieve capacity on symmetric channels. It further gives a sufficient condition if the rows with largest conditional mutual information correspond to the heaviest rows, i.e., if the twin-RM code is the RM code. We demonstrate here that the two codes are at least similar and give further evidence that they are indeed the same.

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation. We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

The repair problem in distributed storage addresses recovery of the data encoded using an erasure code, for instance, a Reed-Solomon (RS) code. We consider the problem of repairing a single node or multiple nodes in RS-coded storage systems using the smallest possible amount of inter-nodal communication. According to the cut-set bound, communication cost of repairing h ≥ 1 failed nodes for an (n, k = n - r) maximum distance separable (MDS) code using d helper nodes is at least dhl/(d + h - k), where l is the size of the node. Guruswami and Wootters (2016) initiated the study of efficient repair of RS codes, showing that they can be repaired using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality. In this paper, we construct the families of RS codes that achieve the cut-set bound for repair of one or several nodes. In the single-node case, we present the RS codes of length n over the field F(ql), l = exp((1 + o(1))n logn) that meet the cut-set bound. We also prove an almost matching lower bound on l, showing that super-exponential scaling is both necessary and sufficient for scalar MDS codes to achieve the cut-set bound using linear repair schemes. For the case of multiple nodes, we construct a family of RS codes that achieve the cut-set bound universally for the repair of any h = 1,2, . . ., r failed nodes from any subset of d helper nodes, k ≤ d ≤ n - h. For a fixed number of parities r, the node size of the constructed codes is close to the smallest possible node size for codes with such properties.

Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. As our first result, we prove a lower bound on the minimum bandwidth of cooperative repair. We also show that the cooperative model is stronger than the centralized one, in the sense that any maximum distance separable (MDS) code with optimal repair bandwidth under the former model also has optimal bandwidth under the latter one. These results were previously known under the additional “uniform download” assumption, which is removed in our proofs. As our main result, we give explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any n, k, h, d such that 2 ≤ h ≤ n- d ≤ n- k we construct (n, k) MDS codes over the field F of size |F| ≥ (d + 1 - k)n that can optimally repair any h erasures from any d helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This implies that our codes achieve the optimal repair bandwidth using the smallest possible number of rounds.

This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit coding scheme that achieves the optimal tradeoff based on recursive polynomial constructions, coding both across data subsets and vector components. As a result, the proposed scheme allows to minimize the running time for gradient computations. Implementations are made on Amazon EC2 clusters using Python with mpi4py package. Results show that the proposed scheme maintains the same generalization error while reducing the running time by $32%$ compared to uncoded schemes and $23%$ compared to prior coded schemes focusing only on stragglers (Tandon et al., ICML 2017).

Two widely studied models of multiple-node repair in distributed storage systems are centralized repair and cooperative repair. The centralized model assumes that all the failed nodes are recreated in one location, while the cooperative one stipulates that the failed nodes may communicate but are distinct, and the amount of data exchanged between them is included in the repair bandwidth. As our first result, we prove a lower bound on the minimum bandwidth of cooperative repair. We also show that the cooperative model is stronger than the centralized one, in the sense that MDS codes with optimal repair bandwidth under the former model have the same property under the latter one. These results were known under the assumption of uniform download which is removed in our proofs. As our main result, we give explicit constructions of MDS codes with optimal cooperative repair for all possible parameters. More precisely, given any n, k, h, d such that 2\leqslant h\leqslant n-d\leqslant n-k we construct (n, k) MDS codes over the field F of size |F|\geqslant(d+1-k)n that can optimally repair any h erasures from any d helper nodes. The repair scheme of our codes involves two rounds of communication. In the first round, each failed node downloads information from the helper nodes, and in the second one, each failed node downloads additional information from the other failed nodes. This implies that our codes achieve the optimal repair bandwidth using the smallest possible number of rounds.

We consider the minimax estimation problem of a discrete distribution with support size k under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number ∈ measures the privacy level of a privatization scheme. For a given ∈, we consider the problem of constructing optimal privatization schemes with ∈-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where E is very close to 0, and in the low privacy regime where e∈≈ k, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when 1 ≪ e∈≪ k. More concretely, we prove that when 3.822metric and by 30% under ℓ1metric over the existing schemes. We also prove a lower bound for the region e∈≪ k, which implies that our schemes are order optimal in this regime.

The repair problem for an (n, k) error-correcting code calls for recovery of an unavailable coordinate of the codeword by downloading as little information as possible from a subset of the remaining coordinates. Using the terminology motivated by coding in distributed storage, we attempt to repair a failed node by accessing information stored on d helper nodes, where k ≤ d ≤ n - 1, and using as little repair bandwidth as possible to recover the lost information. By the so-called cut-set bound (Dimakis et al., 2010), the repair bandwidth of an (n,k = n - r) MDS code using d helper nodes is at least dl/(d + 1 - k), where l is the size of the node. A number of constructions of MDS array codes have been shown to meet this bound with equality. In a related but separate line of work, Guruswami and Wootters (2016) studied repair of Reed-Solomon (RS) codes, showing that it is possible to perform repair using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality, which has been an open problem in coding theory. In this work we present a solution to this problem, constructing RS codes of length n over the field of size ql, l = exp((1 + o(1))n log n) that meet the cut-set bound. We also prove an almost matching lower bound on l, showing that super-exponential scaling is both necessary and sufficient for achieving the cut-set bound using linear repair schemes. More precisely, we prove that for scalar MDS codes (including the RS codes) to meet this bound, the sub-packetization l must satisfy l ≥ exp((1 + o(1))k log k).

We consider error correction by maximum distance separable (MDS) codes based on a part of the received codeword. Our problem is motivated by applications in distributed storage. While efficiently correcting erasures by MDS storage codes (the “repair problem”) has been widely studied in recent literature, the problem of correcting errors in a similar setting seems to represent a new question in coding theory. Suppose that k data symbols are encoded using an (n, k) MDS code, and some of the codeword coordinates are located on faulty storage nodes that introduce errors. We want to recover the original data from the corrupted codeword under the constraint that the decoder can download only an α proportion of the codeword (fractional decoding). For any (n, k) code we show that the number of correctable errors under this constraint is bounded above by ⌊(n - k/α)/2⌋. Moreover, we present two families of MDS array codes which achieves this bound with equality under a simple decoding procedure. The decoder downloads an α proportion of each of the codeword's coordinates, and provides a much larger decoding radius compared to the naive approach of reading some an coordinates of the codeword. One of the code families is formed of Reed-Solomon (RS) codes with well-chosen evaluation points, while the other is based on folded RS codes. Finally, we show that folded RS codes also have the optimal list decoding radius under the fractional decoding constraint.

We consider the minimax estimation problem of a discrete distribution with support size k under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number ϵ measures the privacy level of a privatization scheme. For a given ϵ, we want to find the optimal privatization scheme which minimizes the expected estimation loss for the worst-case distribution. Two schemes in the literature provide order optimal performance in the high-privacy regime when ϵ is very close to 0, and in the low-privacy regime when eϵ≈ k, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when 1 ≪ eϵ≪ k. More concretely, we prove that when 3.822metric and 30% under ℓ1metric over the existing schemes. We also prove a tight lower bound for the whole region eϵ≪ k, which implies that our schemes are order optimal in this regime.

Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with k information nodes and r = n - k parity nodes is used to encode data in a distributed storage system. It is known that if h out of the n nodes are inaccessible and d surviving (helper) nodes are used to recover the lost data, then we need to download at least h/(d + h - k) fraction of the data stored in each of the helper nodes (Dimakis et al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any h erased nodes from any d helper nodes, we say that the MDS code has the (h, d)-optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any r and n, we present two explicit constructions of MDS array codes with the (h, d)-optimal repair property for all h r and k d n - h simultaneously. Codes in the first family can be constructed over any base field F as long as |F| ≥ sn, where s = lcm(1, 2, . .. , r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field F as long as |F| ≥ n+1. Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.

An (n, k, l) maximum distance separable (MDS) array code of length n, dimension k = n - r, and subpacketization l is formed of l × n matrices over a finite field F, with every column of the matrix stored on a separate node in the distributed storage system and viewed as a coordinate of the codeword. Repair of a failed node (recovery of one erased column) can be performed by accessing a set of d ≤ n - 1 surviving (helper) nodes. The code is said to have the optimal access property if the amount of data accessed at each of the helper nodes meets a lower bound on this quantity. For optimal-access MDS codes with d = n-1, the sub-packetization l satisfies the bound l ≥ r(k-1)/r. In our previous work (IEEE Trans. Inf. Theory, vol. 63, no. 4, 2017), for any n and r, we presented an explicit construction of optimal-access MDS codes with subpacketization l = r⌈n-1⌉. In this paper, we take up the question of reducing the sub-packetization value l to make it to approach the lower bound. We construct an explicit family of optimal-access codes with l = r1.n/rl, which differs from the optimal value by at most a factor of r2. These codes can be constructed over any finite field F as long as |F| ≥ r⌈n/r⌉, and afford low-complexity encoding and decoding procedures. We also define a version of the repair problem that bridges the context of regenerating codes and codes with locality constraints (LRC codes), which we call group repair with optimal access. In this variation, we assume that the set of n = sm nodes is partitioned into m repair groups of size s, and require that the amount of accessed data for repair is the smallest possible whenever the d = s + k - 1 helper nodes include all the other s-1 nodes from the same group as the failed node. For this problem, we construct a family of codes with the group optimal access property. These codes can be constructed over any field F of size |F| ≥ n, and also afford low-complexity encoding and decoding procedures.

It is known that polar codes can be efficiently constructed for binary-input channels. At the same time, existing algorithms for general input alphabets are less practical because of high complexity. We address the construction problem for the general case, and analyze an algorithm that is based on successive reduction of the output alphabet size of the subchannels in each recursion step. For this procedure, we estimate the approximation error as O(μ-1/(q-1)), where q is the input alphabet size and μ is the “quantization parameter,” i.e., the maximum size of the subchannel output alphabet allowed by the algorithm. The complexity of the code construction scales as O(N μ2log μ), where N is the length of the code. We also show that if the polarizing operation relies on modulo-q addition, it is possible to merge subsets of output symbols without any loss in subchannel capacity. Performing this procedure before each approximation step results in a further speed-up of the code construction, and the resulting codes have smaller gap to capacity. We also show that a similar acceleration can be attained for polar codes over finite field alphabets. Experimentation shows that the suggested construction algorithms can be used to construct long polar codes for alphabets of size q = 16 and more with acceptable loss of the code rate for a variety of polarizing transforms.

Given any r and n, we present an explicit construction of high-rate maximum distance separable (MDS) array codes that can optimally repair any d failed nodes from any h helper nodes for all h, 1 ≤ h ≤ r and d, k ≤ d ≤ n - h simultaneously. These codes can be constructed over any base field F as long as |F| ≥ sn; where s = lcm(1, 2,..., r). The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Our results present a significant improvement over earlier results which can only construct explicit codes for the case of at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In the second part of the paper we give an explicit construction of Reed-Solomon codes with asymptotically optimal repair bandwidth.

In the standard polar coding construction, the same kernel is used for every channel transformation. In this paper we propose a new polar coding scheme in which the channel combining transformation is dynamically chosen based on the properties of the virtual channels. We show that for some cases it can improve the finite-length performance of codes. We also show that the dynamic scheme retains some of the main properties of the original polar code construction.