This paper presents an explicit construction of a class of optimal-access, minimum storage regenerating (MSR) codes, for small values of the number$d$of helper nodes. The construction is valid for any parameter set$(n,k,d)$with$d \in \{k+1, k+2, k+3\}$and employs a finite field$\mathbb {F}_{q}$of size$q=O(n)$. We will refer to the constructed codes as$\text {Small-}\mathsf {d}$MSR codes. The sub-packetization level$\alpha $is given by$\alpha = s^{{\lceil \frac {n}{s}\rceil }}$, where$s=d-k+1$. By an earlier result on the sub-packetization level for optimal-access MSR codes, this is the smallest value possible.

We present two lower bounds on sub-packetization level$\alpha $of MSR codes with parameters$(n, k, d=n-1, \alpha )$where$n$is the block length,$d$is the number of helper nodes contacted during single-node repair,$\alpha $the sub-packetization level and$k\alpha $the scalar dimension. The first bound we present is for any MSR code and is given by$\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by$\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the$\beta $scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code.

This paper considers the natural extension of locally recoverable codes (LRC) to the case of t > 1 erased symbols. While several approaches have been proposed for the handling of multiple erasures, in the approach considered here, the t erased symbols are recovered in succession, each time contacting at most r other symbols for assistance. Under the local-recovery constraint, this sequential approach is the most general and hence offers the maximum possible code rate. We characterize the rate of an LRC with sequential recovery for any r ≥ 3 and any t, by first deriving an upper bound on the code rate and then constructing a binary code achieving this optimal rate. The upper bound derived here proves an earlier conjecture. Our approach permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The derived structure of parity-check matrix leads to a graphical description of the code used in code construction. A subclass of binary codes that are both rate and block-length optimal, are shown to correspond to certain regular graphs known as Moore graphs, that have the smallest number of vertices for a given girth. A connection with Tornado codes is also made.

Codes with locality are a class of codes introduced by Gopalanet al.to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An$[n,k]$systematic code is said to have information locality$r$, if each message symbol can be recovered by accessing$\leq r$other symbols. An$[n,k]$code is said to have all-symbol locality$r$, if each code symbol can be recovered by accessing$\leq r$other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.

The first focus of the present paper, is on lower bounds on the sub-packetization level α of an MSR code that is capable of carrying out repair in help-by-transfer fashion (also called optimal-access property). We prove here a lower bound on α which is shown to be tight for the case d=(n-1) by comparing with recent code constructions in the literature. We also extend our results to an [n, k] MDS code over the vector alphabet. Our objective even here, is on lower bounds on the sub-packetization level α of an MDS code that can carry out repair of any node in a subset of w nodes, 1 ≤ w ≤ (n-1) where each node is repaired (linear repair) by help-by-transfer with minimum repair bandwidth. We prove a lower bound on α for the case of d=(n-1). This bound holds for any w( ≤ n-1) and is shown to be tight, again by comparing with recent code constructions in the literature. Also provided, are bounds for the case . We study the form of a vector MDS code having the property that we can repair failed nodes belonging to a fixed set of Q nodes with minimum repair bandwidth and in optimal-access fashion, and which achieve our lower bound on sub-packetization level α. It turns out interestingly, that such a code must necessarily have a coupled-layer structure, similar to that of the Ye-Barg code.

This paper presents the construction of an explicit, optimal-access, high-rate MSR code for any (n, k, d=k+ 1, k+2, k+3) parameters over the finite field \mathbbFQ having sub-packetization α = q[n/(q)], where q=d-k+1 and Q=O(n). The sub-packetization of the current construction meets the lower bound proven in a recent work by Balaji et al. in [1]. To our understanding the codes presented in this paper are the first explicit constructions of MSR codes with having optimal sub-packetization, optimal access and small field size.

In this paper we investigate bounds on rate and minimum distance of codes with t availability. We present bounds on minimum distance of a code with t availability that are tighter than existing bounds. For bounds on rate of a code with t availability, we restrict ourselves to a sub-class of codes with t availability called codes with strict t availability and derive a tighter rate bound. Codes with strict t availability can be defined as the null space of an (m × n) parity-check matrix H, where each row has weight (r + 1) and each column has weight t, with intersection between support of any two rows at most one. We also present two general constructions for codes with t availability.

An [n, fc] code C is said to be locally recoverable in the presence of a single erasure, and with locality parameter r, if each of the n code symbols of C can be recovered by accessing at most r other code symbols. An [n, k] code is said to be a locally recoverable code with sequential recovery from t erasures, if for any set of s ≤ t erasures, there is an s-step sequential recovery process, in which at each step, a single erased symbol is recovered by accessing at most r other code symbols. This is equivalent to the requirement that for any set of s ≤ t erasures, the dual code contain a codeword whose support contains the coordinate of precisely one of the s erased symbols. In this paper, a tight upper bound on the rate of such a code, for any value of number of erasures t and any value r ≥ 3, of the locality parameter is derived. This bound proves an earlier conjecture due to Song, Cai and Yuen. While the bound is valid irrespective of the field over which the code is defined, a matching construction of binary codes that are rate-optimal is also provided, again for any value of t and any value r ≥ 3.

This paper considers linear, binary codes having locality parameter r, that are capable of recovering from t ≥ 2 erasures and which additionally, possess short block length. Both sequential and parallel (through orthogonal parity checks) recovery are considered. In the case of sequential repair, the results include (a) extending and characterizing minimum-block-length constructions for t = 2, (b) providing improved bounds on block length for t = 3 as well as a general construction for t = 3 having short block length, (c) providing high-rate constructions for (r = 2, t ∈ {4, 5, 6, 7}) and (d) providing short-block-length constructions for general (r, t). In the case of parallel repair, minimum-block-length constructions are characterized whenever t|(r2+ r) and examples examined.

An [n, k] linear code C that is subject to locality constraints imposed by a parity check matrix H0is said to be a maximally recoverable (MR) code if it can recover from any erasure pattern that some k-dimensional subcode of the null space of H0can recover from. The focus in this paper is on MR codes constrained to have all-symbol locality r. Given that it is challenging to construct MR codes having small field size, we present results in two directions. In the first, we relax the MR constraint and require only that apart from the requirement of being an optimum all-symbol locality code, the code must yield an MDS code when punctured in a single, specific pattern which ensures that each local code is punctured in precisely one coordinate and that no two local codes share the same punctured coordinate. We term these codes as partially maximally recoverable (PMR) codes. We provide a simple construction for high-rate PMR codes and then provide a general, promising approach that needs further investigation. In the second direction, we present three constructions of MR codes with improved parameters, primarily the size of the finite field employed in the construction.

A popular approach to solving multiclass learning problems is to reduce them to a set of binary classification problems through some output code matrix: the widely used one-vs-all and all-pairs methods, and the error-correcting output code methods of Dietterich and Bakiri (1995), can all be viewed as special cases of this approach. In this paper, we consider the question of statistical consistency of such methods. We focus on settings where the binary problems are solved by minimizing a binary surrogate loss, and derive general conditions on the binary surrogate loss under which the one-vs-all and all-pairs code matrices yield consistent algorithms with respect to the multiclass 0-1 loss. We then consider general multiclass learning problems defined by a general multiclass loss, and derive conditions on the output code matrix and binary surrogates under which the resulting algorithm is consistent with respect to the target multiclass loss. We also consider \emphprobabilistic code matrices, where one reduces a multiclass problem to a set of \emphclass probability labeled binary problems, and show that these can yield benefits in the sense of requiring a smaller number of binary problems to achieve overall consistency. Our analysis makes interesting connections with the theory of proper composite losses (Buja et al., 2005; Reid and Williamson, 2010); these play a role in constructing the right ‘decoding’ for converting the predictions on the binary problems to the final multiclass prediction. To our knowledge, this is the first work that comprehensively studies consistency properties of output code based methods for multiclass learning.