In this paper, we study theRandom Access Problemin DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented bykinformation strands which represent the data and are encoded intonstrands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case whenk= 2, showing that the best possible code attains a random access expectation of 1 + 2/ √2+1 ≈ 0.914 · 2 forqlarge enough. Moreover, we extend a previous construction, originally developed fork= 3, to arbitrary values ofk. Our construction usesBk−1sequences overZq−1, that always exist over large finite fields. We show that for everyk≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.

In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at mostrfiles. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.

In this work, we consider the problem of variable packet-error coding, which emerges in network communication scenarios where a source transmits information to a destination through multiple disjoint paths. The objective is to design codes with dynamic error-correcting capabilities that adapt to a varying number of errors. Specifically, we first provide a bound on the rate-distortion trade-off for general variable packet-error coding schemes. Then, we present a construction that uses higherorder MDS codes and provides a variable packet-error coding scheme that achieves a better rate-distortion trade-off compared to known results for general parameter regimes.

Let$n_{q}(M, d)$be the minimum length of a$q$-ary code of size$M$and minimum distance$d$. Bounding$n_{q}(M, d)$is a fundamental problem that lies at the heart of coding theory. This work considers a generalization$n_{q}^{\bullet}(M, d)$of$n_{q}(M, d)$corresponding to codes in which codewords have protected and unprotected entries; where (analogs of) distance and of length are measured with respect to protected entries only. Such codes, here referred to as box codes, have seen prior studies in the context of bipartite graph covering. Upper and lower bounds on$n_{q}^{\bullet \bullet}(M, d)$are presented.

Abstract. Incidence problems between geometric objects is a key area of focus in the field of discrete geometry. Among them, the study of incidence problems over finite fields has received a considerable amount of attention in recent years. In this paper, by characterizing the singular values and singular vectors of the corresponding incidence matrix through group algebras, we prove a bound on the number of incidences between points and varieties of a certain form over finite fields. Our result leads to a new incidence bound for points and flats in finite geometries, which improves previous results for certain parameter regimes. As another application of our point-variety incidence bound, we extend a result on pinned distance problems by Phuong, Thang, and Vinh, and independently by Cilleruelo et al. under a weaker condition.

Abstract. This paper focuses on incidences over finite fields, extending to higher degrees a result by Vinh [ Eur. J. Combin., 32 (2011), pp. 1177–1181] on the number of point-line incidences in the plane [Formula: see text], where [Formula: see text] is a finite field. Specifically, we present a bound on the number of incidences between points and polynomials of bounded degree in [Formula: see text]. Our approach employs a singular value decomposition of the incidence matrix between points and polynomials and an analysis of the related group algebras. This bound is then applied to coding theory, specifically to the problem of average-radius list decoding of Reed–Solomon (RS) codes. We demonstrate that RS codes of certain lengths are average-radius list-decodable with a constant list size that depends only on the code rate and the distance from the Johnson radius. While a constant list size for list-decoding of RS codes in this regime was previously established, its existence for the stronger notion of average-radius list-decoding was not known to exist.

In this paper, we introduce an explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. The codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield. Alternatively, the codes can be constructed by the evaluation of bivariate polynomials over orbits generated bytwoaffine transformations with coprime orders, extending the earlier use of a single affine transformation in folded RS codes and the recent affine folded RS codes introduced by Bhandari et al. (IEEE T-IT, Feb. 2024). While our codes require large, yet constant characteristic, the two affine transformations facilitate achieving code length equal to the field size, without the restriction of the field being prime, contrasting with univariate multiplicity codes.

The purpose of this note is to correct an error made by Con et al. (2023), specifically in the proof of Theorem 9. Here we correct the proof but as a consequence we get a slightly weaker result. In Theorem9, we claimed that for integers k and n such that$k \lt n/9$, there exists an$[n,k]_{q}$RS code that can decode from$n-2k+1$insdel errors where$q = O\left ({{k^{5} \left ({{ \frac {en}{k-1} }}\right)^{4k-4}}}\right)$. Here we prove the following. Theorem 1: For integers n and$k \lt n/9$, there exists an$[n,k]_{q}$RS-code, where$q=O\left ({{k^{4} \cdot \left ({{\frac {4en}{4k-3}}}\right)^{4k-3}}}\right)$is a prime power, that can decode from$n - 2k + 1$adversarial insdel errors. Note that the exponent of n is$4k-3$whereas in Theorem 9 it is$4k-4$. For constant dimensional codes, the field size is of order$O(n^{4k-3})$, and in particular, for$k=2$the field size is of order$O(n^{5})$.

Error-correcting codes resilient to synchronization errors such as insertions and deletions are known as insdel codes. In this paper, we present several new combinatorial upper and lower bounds on the maximum size ofq-ary insdel codes. Our main upper bound is a sphere-packing bound obtained by solving a linear programming (LP) problem. It improves upon previous results for cases when the distancedor the alphabet sizeqis large. Our first lower bound is derived from a connection between insdel codes and matchings in special hypergraphs. This lower bound, together with our upper bound, shows that for fixed block lengthnand edit distanced, whenqis sufficiently large, the maximum size of insdel codes is$ \frac {q^{n-\frac {d}{2}+1}}{\binom {n}{\frac {d}{2}-1}}(1 \pm o(1))$. The second lower bound refines Alon et al.’s recent logarithmic improvement on Levenshtein’s GV-type bound and extends its applicability to largeqandd.

Minimum storage regenerating (MSR) codes are a class of maximum distance separable (MDS) array codes capable of repairing any single failed node by downloading the minimum amount of information from each of the helper nodes. However, MSR codes require large sub-packetization levels, which hinders their usefulness in practical settings. This led to the development of another class of MDS array codes called ε-MSR codes, for which the repair information downloaded from each helper node is at most a factor of (1 + ε) from the minimum amount for some ε > 0. The advantage of ε-MSR codes over MSR codes is their small sub-packetization levels. In previous constructions of epsilon-MSR codes, however, several specific nodes are required to participate in the repair of a failed node, which limits the performance of the code in cases where these nodes are not available. In this work, we present a construction of ε-MSR codes without this restriction. For a code withnnodes, out of whichkstore uncoded information, and for any numberdof helper nodes (k≤dn), the repair of a failed node can be done by contacting any set ofdsurviving nodes. Our construction utilizes group algebra techniques, and requires linear field size. We also generalize the construction to MDS array codes capable of repairinghfailed nodes using d helper nodes with a slightly sub-optimal download from each helper node, for allh≤n−kandk≤d≤n−hsimultaneously.

In this paper, we introduce a novel explicit family of subcodes of Reed-Solomon (RS) codes that efficiently achieve list decoding capacity with a constant output list size. Our approach builds upon the idea of large linear subcodes of RS codes evaluated on a subfield, similar to the method employed by Guruswami and Xing (STOC 2013). However, our approach diverges by leveraging the idea of permuted product codes, thereby simplifying the construction by avoiding the need of subspace designs. Specifically, the codes are constructed by initially forming the tensor product of two RS codes with carefully selected evaluation sets, followed by specific cyclic shifts to the codeword rows. This process results in each codeword column being treated as an individual coordinate, reminiscent of prior capacity-achieving codes, such as folded RS codes and univariate multiplicity codes. This construction is easily shown to be a subcode of an interleaved RS code, equivalently, an RS code evaluated on a subfield.11Due to space limitation the proofs are omitted and can be found in [1].

Given a real dataset and a computation family, we wish to encode and store the dataset in a distributed system so that any computation from the family can be performed by accessing a small number of nodes. In this work, we focus on the families of linear computations where the coefficients are restricted to a finite set of real values. For two-valued computations, a recent work presented a scheme that gives good feasible points on the access-redundancy tradeoff. This scheme is based on binary covering codes having a certain closure property. In a follow-up work, this scheme was extended to all finite coefficient sets, using a new additive-combinatorics notion called coefficient complexity. In the present paper, we explore non-binary covering codes and develop schemes that outperform the state-of-the-art for some coefficient sets. We provide a more general coefficient complexity definition and show its applicability to the access- redundancy tradeoff.

This paper focuses on incidences over finite fields, extending to higher degrees a result by Vinh [1] on the number of point-line incidences in the plane$\mathbb{F}^{2}$, where$\mathbb{F}$is a finite field. Specifically, we present a bound on the number of incidences between points and polynomials of bounded degree in$\mathbb{F}^{2}$. Our approach employs a singular value decomposition of the incidence matrix between points and polynomials, coupled with an analysis of the related group algebras. This bound is then applied to coding theory, specifically to the problem of average-radius list decoding of Reed-Solomon (RS) codes. We demonstrate that RS codes of certain lengths are average-radius list-decodable with a constant list size, which is dependent on the code rate and the distance from the Johnson radius. While a constant list size for list-decoding of RS codes in this regime was previously established, its existence for the stronger notion of average-radius list-decoding was not known to exist.

Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the code length, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the list-decoding capacity. In particular, we show that for any [Formula: see text] there exist RS codes with rate [Formula: see text] that are list-decodable from radius of [Formula: see text]. We generalize this result to list-recovery, showing that there exist [Formula: see text]-list-recoverable RS codes with rate [Formula: see text]. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree packing theorem to hypergraphs and show that if this conjecture holds, then there would exist RS codes that are optimally (nonasymptotically) list-decodable.

We present$O(m^{3})$algorithms for specifying the support of minimum-weight codewords of extended binary BCH codes of length$n=2^{m}$and designed distance$d(m,s,i):=2^{m-1-s}-2^{m-1-i-s}$for some values of$m,i,s$, where m may grow to infinity. Here, the support is specified as the sum of two sets: a set of$2^{2i-1}-2^{i-1}$elements, and a subspace of dimension$m-2i-s$, specified by a basis. In some detail, for designed distance$6\cdot 2^{j}$,$j\in \{0,\ldots ,m-4\}$, we have a deterministic algorithm for even$m\geq 4$, and a probabilistic algorithm with success probability$1-O(2^{-m})$for odd$m\gt 4$. For designed distance$28\cdot 2^{j}$,$j\in \{0,\ldots , m-6\}$, we have a probabilistic algorithm with success probability$\geq \frac {1}{3}-O(2^{-m/2})$for even$m\geq 6$. Finally, for designed distance$120\cdot 2^{j}$,$j\in \{0,\ldots , m-8\}$, we have a deterministic algorithm for$m\geq 8$divisible by 4. We also show how Gold functions can be used to find the support of minimum-weight words for designed distance$d(m,s,i)$(for$i\in \{0,\ldots ,\lfloor m/2\rfloor \}$, and$s\leq m-2i$) whenever$2i|m$. Our construction builds on results of Kasami and Lin, who proved that for extended binary BCH codes of designed distance$d(m,s,i)$(for integers$m\geq 2$,$0\leq i\leq \lfloor m/2\rfloor $, and$0\leq s\leq m-2i$), the minimum distance equals the designed distance. The proof of Kasami and Lin makes use of a non-constructive existence result of Berlekamp, and a constructive “down-conversion theorem” that converts some words in BCH codes to lower-weight words in BCH codes of lower designed distance. Our main contribution is in replacing the non-constructive counting argument of Berlekamp by a low-complexity algorithm. In one aspect, the current paper extends the results of Grigorescu and Kaufman, who presented explicit minimum-weight codewords for extended binary BCH codes of designed distance exactly 6 (and hence also for designed distance$6\cdot 2^{j}$, by a well-known “up-conversion theorem”), as we cover more cases of the minimum distance. In fact, we prove that the codeword constructed by Grigorescu and Kaufman is a special case of the current construction. However, the minimum-weight codewords we construct do not generate the code, and are not affine generators, except, possibly, for a designed distance of 6.

Constructing Reed–Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. Our focus in this paper is on the special case of two-dimensional RS-codes that can correct fromn- 3 insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known (by settingk= 2 in the lower bound [10, Proposition 37]) that an [n, 2]qRS-code that can correct fromn-3 insdel errors satisfies thatq= Ω(n3). On the other hand, there are several known constructions of [n, 2]qRS-codes that can correct fromn-3 insdel errors, where the smallest field size isq=O(n4). In this short paper, we construct [n, 2]qReed–Solomon codes that can correctn-3 insdel errors withq=O(n3), thereby resolving the minimum field size needed for such codes.

This paper presents two repair schemes for low-rate Reed-Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The total bandwidth resulting from these schemes is greater than that incurred during trivial repair; however, this is particularly relevant in the context of leakage-resilient secret sharing. In that framework, our results provide attacks showing that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage-resilient, even when the parties leak only a constant number of bits. To the best of our knowledge, these are the first such attacks. Our results are derived from a novel connection between exponential sums and the repair of RS codes. Specifically, we establish that non-trivial bounds on certain exponential sums imply the existence of explicit nonlinear repair schemes for RS codes over prime fields.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations that are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), have gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where a smaller access parameter requires more redundancy in the system, and vice versa. In this paper, we study this tradeoff and provide several explicit low-access schemes for$\{\pm 1\}$quantized linear computations based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art for two-valued linear computations. We further show that the same storage scheme can be used to retrieve any linear combination with two distinct coefficients—regardless of what those coefficients are—with the same access parameter. This universality result is then extended to all possible quantizations with any number of values; while the storage remains identical, the access parameter increases according to a new additive-combinatorics property we call coefficient complexity. We then turn to study the coefficient complexity—we characterize the complexity of small sets of coefficients, provide bounds, and identify coefficient sets having the highest and lowest complexity. Interestingly, arithmetic progressions have the lowest possible complexity, and some geometric progressions have the highest possible complexity, the former being particularly attractive for its common use in uniform quantization.

Folded Reed-Solomon (FRS) and univariate multiplicity codes are prominent polynomial codes over finite fields renowned for achieving list decoding capacity. These codes have found many applications beyond the traditional scope of coding theory. In this paper, we introduce improved bounds on the list size for list decoding these codes, achieved through a more streamlined proof method. Additionally, we refine an existing randomized algorithm to output the codewords on the list, which enhances its success probability and reduces its running time. Lastly, we establish list-size bounds for a fixed decoding parameter. Notably, our results demonstrate that FRS codes asymptotically attain the generalized Singleton bound for a list of size 2 over a relatively small alphabet, marking the first explicit instance of a code with this property.

This paper presents several repair schemes for lowrate Reed Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The resulting total bandwidth is higher than the bandwidth incurred during the trivial repair; however, this is still interesting in the context of leakage-resilient secret sharing. In that language, our results give attacks that show that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage resilient, even if the parties only leak a constant number of bits. To the best of our knowledge, these are the first such attacks.As another application, we provide decoding schemes for RS codes over prime fields, where the entire RS codeword is recovered by transmitting a constant number of bits from each node.Our results follow from a novel connection between exponential sums and repair of RS codes. In particular, we show that nontrivial bounds on certain exponential sums imply the existence of efficient nonlinear repair schemes for RS codes over prime fields.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations which are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks, and reduces the overall communication in the system. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where smaller access parameter requires more redundancy in the system, and vice versa. In this paper we study this tradeoff, and provide several explicit code constructions based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art, and extend the framework to new families of computations.

Abstract. In this paper we take a combinatorial approach to the problem of list-decoding, which allows us to determine the precise relation (up to the exact constant) between the decoding radius, list size, and code rate. We prove a generalized Singleton bound for a given list size, and conjecture that the bound is tight for most Reed–Solomon (RS) codes over large enough finite fields. We also show that the conjecture holds true for list sizes 2 and 3, and as a by product show that most RS codes with a rate of at least 1/9 are list-decodable beyond the Johnson radius. Last, we give the first explicit construction in the literature of such RS codes. The main tools used in the proof are a new type of linear dependency between codewords of a code that are contained in a small Hamming ball, and a surprising connection between list-decoding and the notion of cycle space in graph theory. Both of them are new, and may be of independent interest.

In the private information retrieval (PIR) problem, a user wants to retrieve a file from a database without revealing any information about the desired file’s identity to the servers that store the database. In this paper, we study the PIR capacity of a graph-based replication system, in which each file is stored on two distinct servers according to an underlying graph. This paper aims to provide upper and lower bounds to the PIR capacity of graphs via various graph properties. In particular, we provide several upper bounds on the PIR capacity that apply to all graphs. We further improve the bounds for specific graph families (which turn out to be tight in certain cases) by utilizing the underlying graph structure. For the lower bounds, we establish optimal rate PIR schemes for star graphs via edge-coloring techniques. Lastly, we provide an improved PIR scheme for complete graphs, implying an improved general lower bound on all graphs’ PIR capacity.

In this work, we study the performance of Reed–Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size$n^{O(k)}$there are$[n,k]$Reed-Solomon codes that can decode from$n-2k+1$insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size$n^{k^{O(k)}}$). Nevertheless, for$k=O(\log n /\log \log n)$our construction runs in polynomial time. For the special case$k=2$, which received a lot of attention in the literature, we construct an$[n], [2]$Reed-Solomon code over a field of size$O(n^{4})$that can decode from$n-3$insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size$\Omega (n^{3})$.

Understanding the limits of list-decoding and list-recovery of Reed-Solomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are list-decodable or list-recoverable beyond the Johnson radius foreveryrate, with a polynomial field size in the block length. In particular, we show that for every$\epsilon \in (0,1)$there exist RS codes that are list-decodable from radius$1-\epsilon $and rate less than$\frac {\epsilon }{2-\epsilon }$, with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code’s linearity.

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [Guruswami and Wootters, 2017] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). Specifically, we show that almost all 2 dimensional RS codes over prime fields (for large enough prime) are asymptotically MSR codes. This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Moreover, we construct several RS codes over prime fields that exhibits efficient repair properties. We also show that unlike the problem of repairing RS codes over field extensions, over prime fields, one can not achieve the cut-set bound with equality. Concretely, by using ideas from additive combinatorics, we improve the cut-set bound by an additive factor, hence showing that every node must transmit more bits than the cut-set bound during a repair. Lastly, we discuss the implications of our results on repairing RS codes for leakage-resilient of Shamir’s secret sharing scheme over prime fields.

In this work, we study the performance of Reed-Solomon codes against adversarial insertion-deletion (insdel) errors.We prove that over fields of size nO(k)there are [n, k] Reed-Solomon codes that can decode from n – 2k + 1 insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size ${n^{{k^{O(k)}}}}$). Nevertheless, for k = O(log n/ log log n) our construction runs in polynomial time. For the special case k = 2, which received a lot of attention in the literature, we construct an [n, 2] Reed-Solomon code over a field of size O(n4) that can decode from n – 3 insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size Ω(n3).

We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an$\mathbb {F}_{q}$-linear subspace$U\subseteq \mathbb {F}_{q^{m}} $of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb {F}_{q}$is the Galois field of size$q$. For$q>2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}$,$s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb {F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least$1/3$) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme. Our result extend the construction of Dau–Milenkovic to the range$r < m-s$, for a wide range of parameters.

In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over$\mathbb {F}_{q}$, for$q= {\mathrm {poly}}(1/\varepsilon)$, that can efficiently decode from a$\delta $fraction of insdel errors and have rate$(1-4\delta)/8-\varepsilon $. We also show that by allowing codes over$\mathbb {F}_{q^{2}}$that are linear over$\mathbb {F}_{q}$, we can improve the rate to$(1-\delta)/4-\varepsilon $while not sacrificing efficiency. Using this latter result, we construct fully linear codes over$\mathbb {F}_{2}$that can efficiently correct up to$\delta < 1/54$fraction of deletions and have rate$R = (1-54\cdot \delta)/1216$. Chenget al.(2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a$\delta < 1/400$fraction of insdel errors. They also posed the problem of constructing linear codes that get close to thehalf-Singleton bound[proved in Chenget al.(2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound.

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised by Guruswami and Wootters, 2017, on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate$\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist$(1-\varepsilon,\ell, O(\ell/\varepsilon))$-list-recoverable RS codes with rate$\Omega\left(\frac{\varepsilon}{\sqrt{\ell}(\log(1/\varepsilon)+1)}\right)$. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable.11A full version of this paper is available online at https://arxiv.org/abs/2011.04453.

We consider the repair problem for Reed-Solomon (RS) codes, evaluated on an$\mathbb{F}_{q}$-linear subspace$U \subseteq \mathbb{F}_{q^{m}}$of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb{F}_{q}$is the Galois field of size$q$. For$q > 2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}, s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb{F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least 1/3) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme.

In the private information retrieval (PIR) problem, a user wants to retrieve a file from a database without revealing any information about the desired file's identity to the servers that store the database. In this paper, we study the PIR capacity of a graph-based replication system, in which each file is stored on two distinct servers according to an underlying graph. This paper aims to provide upper and lower bounds to the PIR capacity of graphs via various graph properties. In particular, we provide several upper bounds on the PIR capacity that apply to all graphs. We further improve the bounds for specific graph families (which turn out to be tight in certain cases) by utilizing the underlying graph structure. For the lower bounds, we establish optimal rate PIR retrieval schemes for star graphs via edge-coloring techniques. Lastly, we provide an improved PIR scheme for complete graphs, which implies an improved general lower bound on all graphs' PIR capacity.

Let G be a connected graph on n vertices and C be an (n,k,d) code with d ≥ 2, defined on the alphabet {0,1} m . Suppose that for 1 ≤ i ≤ n, the i-th vertex of G holds an input symbol x i ∈{0,1}mand let x⃗ = (x1,...,xn) ∈{0,1}mnbe the input vector formed by those symbols. Assume that each vertex of G can communicate with its neighbors by transmitting messages along the edges, and these vertices must decide deterministically, according to a predetermined communication protocol, that whether x⃗ ∈ C. Then what is the minimum communication cost to solve this problem? Moreover, if x⃗ ∉ C, say, there is less than ⌊(d-1)/2⌋ input errors among the x i 's, then what is the minimum communication cost for error correction? We initiate the study of the two problems mentioned above. For the error detection problem, we obtain two lower bounds on the communication cost as functions of n,k,d,m, and our bounds are tight for several graphs and codes. For the error correction problem, we design a protocol which can efficiently correct a single input error when G is a cycle and C is a repetition code. We also present several interesting problems for further research. Full version is available at.

List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius has been one of the main open questions in coding theory and theoretical computer science since the work of Guruswami and Sudan. It is now known by the work of Rudra and Wootters, using techniques from high dimensional probability, that over large enough alphabets there exist RS codes that are indeed list-decodable beyond this radius.

For fixed integers $r\ge 3,e\ge 3,v\ge r+1$, an $r$-uniform hypergraph is called $\mathscr{G}_r(v,e)$-free if the union of any $e$ distinct edges contains at least $v+1$ vertices. Brown, Erdös, and Sós showed that the maximum number of edges of such a hypergraph on $n$ vertices, denoted as $f_r(n,v,e)$, satisfies $\Omega(n^{\frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{\lceil\frac{er-v}{e-1}\rceil})$. For sufficiently large $n$ and $e-1\mid er-v$, the lower bound matches the upper bound up to a constant factor, which depends only on $r,v,e$; whereas for $e-1\nmid er-v$, in general it is a notoriously hard problem to determine the correct exponent of $n$. Among other results, we improve the above lower bound by showing that $f_r(n,v,e)=\Omega(n^{\frac{er-v}{e-1}}(\log n)^{\frac{1}{e-1}})$ for any $r,e,v$ satisfying $\gcd(e-1,er-v)=1$. The hypergraph we constructed is in fact $\mathscr{G}_r(ir-\lceil\frac{(i-1)(er-v)}{e-1}\rceil,i)$-free for every $2\le i\le e$, and it has several interesting applications in coding theory. The proof of the new lower bound is based on a novel application of the lower bound on the hypergraph independence number due to Duke, Lefmann, and Rödl.

An $r$-uniform hypergraph is called $t$-cancellative if for any $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$. It is called $t$-union-free if for any two distinct subsets $\mathcal{A}, \mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in \mathcal{A}} A\neq \cup_{B\in \mathcal{B}} B$. Let $C_t(n,r)$ (resp., $U_t(n,r)$) denote the maximum number of edges of a $t$-cancellative (resp., $t$-union-free) $r$-uniform hypergraph on $n$ vertices. Among other results, we show that for fixed $r\ge 3,t\ge 3$ and $n\rightarrow\infty$, $\Omega(n^{\lfloor\frac{2r}{t+2}\rfloor+\frac{2r\pmod{t+2}}{t+1}})=C_t(n,r)=O(n^{\lceil\frac{r}{\lfloor t/2\rfloor+1}\rceil})\text{ and } \Omega(n^{\frac{r}{t-1}})=U_t(n,r)=O(n^{\lceil\frac{r}{t-1}\rceil}),$ thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Turán exponent of $C_t(n,r)$ when $2\mid t \text{ and } (t/2+1)\mid r$, and of $U_t(n,r)$ when $(t-1)\mid r$. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.

We study a guessing game where Alice holds a discrete random variable X, and Bob tries to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is however unreliable, and is incorrect with probability ϵ. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question simultaneously minimizes all the guessing moments for any value of ϵ. In particular, this result settles a conjecture of Burin and Shayevitz. We further consider a more general setup where Bob can ask a multiple-choice M-ary question, and then observe Carole's answer through a noisy channel. When the channel is completely symmetric, i.e., when Carole decides whether to lie regardless of Bob's question and has no preference when she lies, a similar question about the ordered index of X (modulo M) is optimal. Interestingly however, the problem of testing whether a given question is optimal appears to be generally difficult in other symmetric channels. We provide supporting evidence for this difficulty, by showing that a core property required in our proofs becomes NP-hard to test in the general M-ary case. We establish this hardness result via a reduction from the problem of testing whether a system of modular difference disequations has a solution, which we prove to be NP-hard for M ≥ 3.

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the ℓ2error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called t-private if the identity of the file remains concealed even if t of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases.

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.

Erasure codes in large-scale storage systems allow recovery of data from a failed node. A recently developed class of codes, locally repairable codes (LRCs), offers tradeoffs between storage overhead and repair cost. LRCs facilitate efficient recovery scenarios by adding parity blocks to the system. However, these additional blocks may eventually increase the number of blocks that must be reconstructed. Existing LRCs differ in their use of the parity blocks, in their locality semantics, and in their parameter space. Thus, existing theoretical models cannot directly compare different LRCs to determine which code offers the best recovery performance, and at what cost. We perform the first systematic comparison of existing LRC approaches. We analyze Xorbas, Azure’s LRCs, and Optimal-LRCs in light of two new metrics: average degraded read cost and normalized repair cost. We show the tradeoff between these costs and the code’s fault tolerance, and that different approaches offer different choices in this tradeoff. Our experimental evaluation on a Ceph cluster further demonstrates the different effects of realistic system bottlenecks on the benefit from each LRC approach. Despite these differences, the normalized repair cost metric can reliably identify the LRC approach that would achieve the lowest repair cost in each setup.

For fixed integers r ≥ 2, e ≥ 2, v ≥ r + 1, an r-uniform hypergraph is called Gr(v, e)-free if the union of any e distinct edges contains at least v+1 vertices. Let Gr(n, v, e) denote the maximum number of edges in a Gr(v, e)-free r-uniform hypergraph on n vertices. Brown, Erdós and Sós showed in 1973 that there exist constants c1, c2depending only on r, e, v such that c1ner-v/e-1≤ fr(n,v,e) ≤ c2n[er-v/e-1]For e - 1|er - v, the lower bound matches the upper bound up to a constant factor; whereas for e - 1 t er - v, it is a notoriously hard problem to determine the correct exponent of n. Our main result is an er-v improvement fr(n, v, e) = Ω(n e-1 (log n) 1 e-1 ) for any r, e, v satisfying gcd(e - 1, er - v) = 1. Moreover, the hypergraph we constructed is not only gr(v, e)-free but also universally Gr(ir - Γ (i-1)(-1er-v) 1 + i)-free for every 2 <; i <; e. Interestingly, e our new lower bound provides improved constructions for several seemingly unrelated topics in Coding Theory, namely, Parent-Identifying Set Systems, uniform Combinatorial Batch Codes and optimal Locally Recoverable Codes.

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.

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favourably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that the normalized adjacency matrix of an expander graph can yield excellent approximate gradient codes, and that this approach allows us to perform significantly less computation compared to exact gradient coding. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

We study a guessing game where Alice holds a discrete random variable X, and Bob is trying to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is unreliable, and is incorrect with probability ε. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question minimizes all the guessing moments for any value of ε. This in particular settles a conjecture of Burin and Shayevitz. We further count the number of optimal questions, and discuss some extensions including asymmetric channels from Carole to Bob and to multiple-choice questions.

Replication is prevalent in both theory and practice as a means for obtaining robustness in distributed storage systems. A system in which every data entry is stored on two separate servers gives rise to a graph structure in a natural way, and the combinatorial properties of this graph shed light on the possible features of the system. One possible feature of interest, that has recently gained renewed attention, is private information retrieval (PIR). A PIR protocol enables a user to obtain a data entry from a storage system without revealing the identity of the requested entry to sets of colluding servers. In this paper we suggest a simple PIR protocol for graph based replication systems, which guarantees perfect secrecy against any set of colluding servers that does not induce a cycle. Furthermore, it is shown that the secrecy deteriorates gracefully with the number of cycles in the colluding set, and that the upload complexity can be reduced for graphs of certain specialized structure.

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.

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word.

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.

This paper addresses the problem of constructing maximum distance separable (MDS) codes that enable exact reconstruction (repair) of each code block by downloading a small amount of information from the remaining code blocks. The total amount of information flow from the remaining code blocks during this reconstruction process is referred to as repair bandwidth of the underlying code. Existing constructions of exact-repairable MDS codes with optimal repair bandwidth require working with large subpacketization levels, which restrict their applicability in practice. This paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required subpacketization level at the cost of slightly suboptimal repair bandwidth. The first approach provides MDS codes that have repair bandwidth at most twice the optimal repair bandwidth. In addition, these codes also have the smallest possible subpacketization level O(r), where r denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair bandwidth at the cost of graceful increment in the required subpacketization level. The second approach transforms an MDS code with optimal repair bandwidth and large subpacketization level into a longer MDS code with small subpacketization level and near-optimal repair bandwidth. For a given r, the codes constructed using this approach have their subpacketization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block.

A subspace of a finite extension field is called a Sidon space if the product of any two of its elements is unique up to a scalar multiplier from the base field. Sidon spaces were recently introduced by Bachoc et al. as a means to characterize multiplicative properties of subspaces, and yet no explicit constructions were given. In this paper, several constructions of Sidon spaces are provided. In particular, in some of the constructions the relation between k, the dimension of the Sidon space, and n, the dimension of the ambient extension field, is optimal. These constructions are shown to provide cyclic subspace codes, which are useful tools in network coding schemes. To the best of our knowledge, this constitutes the first set of constructions of nontrivial cyclic subspace codes in which the relation between k and n is polynomial, and in particular, linear. As a result, a conjecture by Trautmann et al. regarding the existence of non-trivial cyclic subspace codes is resolved for most parameters, and multi-orbit cyclic subspace codes are attained, whose cardinality is within a constant factor (close to 1/2) from the sphere-packing bound for subspace codes.

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 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.

In this paper, we study the impact of locality on the decoding of binary cyclic codes under two approaches, namely ordered statistics decoding (OSD) and trellis decoding. Given a binary cyclic code having locality or availability, we suitably modify the OSD to obtain gains in terms of Signal-To-Noise ratio, for a given reliability and essentially the same level of decoder complexity. With regard to trellis decoding, we show that careful introduction of locality results in the creation of cyclic subcodes having lower maximum state complexity. We also present a simple upper-bounding technique on the state complexity profile, based on the zeros of the code. Finally, it is shown how the decoding speed can significantly be increased in the presence of locality, in the moderate-to-high SNR regime, by making use of a quick-look decoder that often returns the ML codeword.

The interest in subspace codes has increased in recent years due to their application in error correction for random network coding. In order to study their properties and find good constructions, the notion of cyclic subspace codes was introduced by using the extension field structure of the ambient space. However, to this date there exists no general construction with a polynomial relation between k, the dimension of the codewords, and n, the dimension of the entire space. Independently of the study of cyclic subspace codes, sSidon spaces were recently introduced by Bachoc et al. as a tool for the study of certain multiplicative properties of subspaces over finite fields. In this paper it is shown that Sidon spaces are necessary and sufficient for obtaining a full-orbit cyclic subspace code with minimum distance 2 k - 2. By presenting several constructions of Sidon spaces, full-orbit cyclic subspace codes are obtained, in which n is quadratic in k. The constructions are based on a variety of tools; namely, Sidon sets, that are sets of integers in which all pairwise sums are distinct, irreducible polynomials, and linearized polynomials. Further, the existence of a Sidon space in which n is linear in k is shown, alongside the fact that any Sidon space induces a Sidon set.

Minimum storage regenerating (MSR) codes form a special class of maximum distance separable (MDS) codes by providing mechanisms for exact regeneration of a single code block in their codewords by downloading the minimum amount of information from the remaining code blocks. As a result, the MSR codes find application to distributed storage systems to enable node repairs with the optimal repair band-width. However, the construction of exact-repairable MSR codes requires working with a large sub-packetization level, which restricts the employment of these codes in practice. This paper explores exact-repairable MDS codes that significantly reduce the required sub-packetization level by achieving slightly suboptimal repair bandwidth as compared to the MSR codes. This paper presents a general approach to combine an MSR code with large sub-packetization level with a code with large enough minimum distance to construct exact-repairable MDS codes with small sub-packetization level and near-optimal repair bandwidth. For a given number of parity blocks, the codes constructed using this approach have their sub-packetization level scaling logarithmically with the code length. In addition, the obtained codes require field size linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during a node repair.

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.

A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most r) of other symbols of the codeword. In this paper, we introduce a construction of LRC codes on algebraic curves, extending a recent construction of the Reed-Solomon like codes with locality. We treat the following situations: local recovery of a single erasure, local recovery of multiple erasures, and codes with several disjoint recovery sets for every coordinate (the availability problem). For each of these three problems we describe a general construction of codes on curves and construct several families of LRC codes. We also describe a construction of codes with availability that relies on automorphism groups of curves. We also consider the asymptotic problem for the parameters of the LRC codes on curves. We show that the codes obtained from asymptotically maximal curves (for instance, Garcia-Stichtenoth towers) improve upon the asymptotic versions of the Gilbert-Varshamov bound for LRC codes.

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with r redundancy nodes can correct any r node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, e erasures are a more likely failure event, for some 1 ≤ e <; r. Hence, a natural question is how much information do we need to access in order to rebuild e storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of e erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of 1/r for the rebuilding of any systematic node when e = 1; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any r erasures can be corrected by accessing some of the remaining information, and any e = 1 erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of e/r for systematic nodes of MDS codes, for any 1 ≤ e r; 2) we construct systematic codes that achieve optimal rebuilding ratio of 1/r, for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.

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.

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert-Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets.

Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes, such as Reed-Solomon (RS), are highly sub-optimal for distributed environments due to their high overhead during single-failure events. Locally repairable codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs. Fundamental bounds and methods for explicitly constructing LRCs suitable for deployment in distributed storage clusters are not fully understood and currently form an active area of research. In this paper, we present an explicit LRC that is simple to construct and is optimal for a specific set of coding parameters. Our construction is based on grouping RS symbols and then adding extra simple parities that allow for small repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code's generator matrix.

In distributed storage, a file is stored in a set of nodes and protected by erasure-correcting codes. Regenerating code is a type of code with two properties: first, it can reconstruct the entire file in the presence of any r node erasures for some specified integer r; second, it can efficiently repair an erased node from any subset of remaining nodes with a given size. In the repair process, the amount of information transmitted from each node normalized by the storage size per node is termed repair bandwidth (fraction). When the storage size per node is minimized, the repair bandwidth is lower bounded by 1/r, where r is the number of parity nodes. A code attaining this lower bound is said to have optimal repair. We consider codes with minimum storage size per node and optimal repair, called minimum storage regenerating (MSR) codes. In particular, if an MSR code has r parities and any r erasures occur, then by transmitting all the information from the remaining nodes, the original file can be reconstructed. On the other hand, if only one erasure occurs, only a fraction of 1/r of the information in each remaining node needs to be transmitted. If we view each node as a vector or a column over some field, then the code forms a 2-D array. Given the length of the column l and the number of parities r, we explicitly construct the high-rate MSR codes. The number of systematic nodes of our construction is (r + 1) logrl, which is longer than previously known results. Besides, we construct the MSR codes with other desirable properties: first, the codes with low complexity when the information is updated, and second, the codes with low access or storage node I/O cost during repair.

A code over a finite alphabet is called locally recoverable (LRC code) if every symbol in the encoding is a function of a small number (at most r) other symbols. A family of linear LRC codes that generalize the classic construction of Reed-Solomon codes was constructed in a recent paper by I. Tamo and A. Barg (IEEE Trans. Inform. Theory, vol. 60, no. 8, 2014, pp. 4661-4676). In this paper we extend this construction to codes on algebraic curves. We give a general construction of LRC codes on curves and compute some examples, including asymptotically good families of codes derived from the Garcia-Stichtenoth towers. The local recovery procedure is performed by polynomial interpolation over r coordinates of the codevector. We also obtain a family of Hermitian codes with two disjoint recovering sets for every symbol of the codeword.

We consider linear cyclic codes with the locality property, or locally recoverable codes (LRC codes). A family of LRC codes that generalizes the classical construction of Reed-Solomon codes was constructed in a recent paper by I. Tamo and A. Barg (IEEE Trans. IT, no. 8, 2014). In this paper we focus on the optimal cyclic codes that arise from the general construction. We give a characterization of these codes in terms of their zeros, and observe that there are many equivalent ways of constructing optimal cyclic LRC codes over a given field. We also study subfield subcodes of cyclic LRC codes (BCH-like LRC codes) and establish several results about their locality and minimum distance.

A code over a finite alphabet is called locally recoverable code (LRC code) if every symbol in the encoding is a function of a small number (at most r) other symbols. We present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality. The codes can be constructed over a finite field alphabet of any size that exceeds the code length. The codewords are obtained as evaluations of specially constructed polynomials over a finite field, and reduce to Reed-Solomon codes if the locality parameter r is set to be equal to the code dimension. The recovery procedure is performed by polynomial interpolation over r points. We also construct codes with several disjoint recovering sets for every symbol. This construction enables the system to conduct several independent and simultaneous recovery processes of a specific symbol by accessing different parts of the codeword. This property enables high availability of frequently accessed data.

A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. Bounds on the rate and distance of such codes have been extensively studied in the literature. In this paper we derive upper bounds on the rate and distance of codes in which every symbol has t ≥ 1 disjoint recovering sets.

Distributed storage systems employ codes to provide resilience to failure of multiple storage disks. In particular, an (n, k) maximum distance separable (MDS) code stores k symbols in n disks such that the overall system is tolerant to a failure of up to n - k disks. However, access to at least k disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length ℓ. The MDS array codes have the potential to repair a single erasure using a fraction 1/(n - k) of data stored in the remaining disks. We introduce new methods of analysis, which capitalize on the translation of the storage system problem into a geometric problem on a set of operators and subspaces. In particular, we ask the following question: for a given (n, k), what is the minimum vector-length or subpacketization factor ℓ required to achieve this optimal fraction? For exact recovery of systematic disks in an MDS code of low redundancy, i.e., k/n > 1/2, the best known explicit codes have a subpacketization factor ℓ, which is exponential in k. It has been conjectured that for a fixed number of parity nodes, it is in fact necessary for ℓ to be exponential in k. In this paper, we provide a new log-squared converse bound on k for a given ℓ, and prove that k ≤ 2 log2I(logδℓ + 1), for an arbitrary number of parity nodes r = n - k, where δ = r/(r - 1).

A code over a finite alphabet is called locally recoverable (LRC) if every symbol in the encoding is a function of a small number (at mostr) other symbols. We present a family of LRC codes that attain the maximum possible value of the distance for a given locality parameter and code cardinality. The codewords are obtained as evaluations of specially constructed polynomials over a finite field, and reduce to a Reed-Solomon code if the locality parameterris set to be equal to the code dimension. The size of the code alphabet for most parameters is only slightly greater than the code length. The recovery procedure is performed by polynomial interpolation overrpoints. We also construct codes with several disjoint recovering sets for every symbol. This construction enables the system to conduct several independent and simultaneous recovery processes of a specific symbol by accessing different parts of the codeword. This property enables high availability of frequently accessed data (“hot data”).

Maximum distance separable (MDS) codes are widely used in storage systems to protect against disk (node) failures. A node is said to have capacitylover some field F, if it can store that amount of symbols of the field. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to anyn-knode failures. An optimal bandwidth (respectively, optimal access) MDS code communicates (respectively, accesses) the minimum amount of data during the repair process of a single failed node. It was shown that this amount equals a fraction of 1/(n - k) of data stored in each node. In previous optimal bandwidth constructions,lscaled polynomially with k in codes when the asymptotic rate is less than 1. Moreover, in constructions with a constant number of parities, i.e., when the rate approaches 1,lis scaled exponentially withk. In this paper, we focus on the case of linear codes with linear repair operations and constant number of paritiesn-k=r, and ask the following question: given the capacity of a node l what is the largest number of information disks k in an optimal bandwidth (respectively, access) (k+r, k, l) MDS code? We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes. The first is a family of codes with optimal update property, and the second is a family with optimal access property. Moreover, the bounds show that in some cases optimal-bandwidth codes have largerkthan optimal-access codes, and therefore these two measures are not equivalent.

Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly suboptimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and simple to implement construction of optimal LRCs, for code parameters previously established by existence results. For the analysis of the optimality of our code, we derive a new result on the matroid represented by the code's generator matrix.

Maximum distance separable (MDS) array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct, then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between${{1} \over {2}}$and${{3} \over {4}}$; however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a two-erasure correcting code, the rebuilding ratio is${{1} \over {2}}$. In general, we construct a new family of$r$-erasure correcting MDS array codes that has optimal rebuilding ratio of${{1} \over {r}}$in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the cases$r=2$and$r=3$, they use a finite field of size 3 and 4, respectively) and an optimal update property.

Maximum distance separable (MDS) codes are widely used in storage systems to protect against disks (nodes) failures. An (n, k, l) MDS code uses n nodes of capacity l to store k information nodes. The MDS property guarantees the resiliency to any n - k node failures. An optimal bandwidth (resp. optimal access) MDS code communicates (resp. accesses) the minimum amount of data during the recovery process of a single failed node. It was shown that this amount equals a fraction of 1/(n - k) of data stored in each node. In previous optimal bandwidth constructions, l scaled polynomially with k in codes with asymptotic rate <; 1. Moreover, in constructions with constant number of parities, i.e. rate approaches 1, l scaled exponentially w.r.t. k. In this paper we focus on the practical case of n - k = 2, and ask the following question: Given the capacity of a node l what is the largest (w.r.t. k) optimal bandwidth (resp. access) (k + 2, k, l) MDS code. We give an upper bound for the general case, and two tight bounds in the special cases of two important families of codes.

MDS codes are erasure-correcting codes that can correct the maximum number of erasures given the number of redundancy or parity symbols. If an MDS code has r parities and no more than r erasures occur, then by transmitting all the remaining data in the code one can recover the original information. However, it was shown that in order to recover a single symbol erasure, only a fraction of 1/r of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we ask the following question: given the length of the column l, can we construct high-rate MDS array codes with optimal repair bandwidth of 1/r, whose code length is as long as possible? In this paper, we give code constructions such that the code length is (r + l)logrl.

We consider codes over permutations under the infinity norm. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding procedures, and then optimize the code's minimal distance via relabeling. To establish that the relabeling problem is hard and is of interest, we formally define it and show that all codes may be relabeled to get a minimal distance at most 2. On the other hand, the decision problem of whether a code may be relabeled to distance 2 or more is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved to be hard to approximate up to a factor of 2. We then consider general bounds on the relabeling problem. We specifically construct the optimal relabeling for transitive cyclic groups. We conclude with the main result-a general probabilistic bound, which we then use to show both the AGL(p) group and the dihedral group onpelements may be relabeled to a minimal distance ofp-O(√pinp).

Codes over permutations under the infinity norm have been recently suggested as a coding scheme for correcting limited-magnitude errors in the rank modulation scheme. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding/decoding procedures, and then optimize the code's minimal distance via relabeling. We formally define the relabeling problem, and show that all codes may be relabeled to get a minimal distance at most 2. The decision problem of whether a code may be relabeled to distance 1 is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved hard to approximate. Finally, we consider general bounds on the relabeling problem. We specifically show the optimal relabeling distance of cyclic groups. A specific case of a general probabilistic argument is used to show AGL(p) may be relabeled to a minimal distance of p - O(√(p ln p)).

MDS array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting (and more practical) case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of r-erasure correcting MDS array codes that has optimal rebuilding ratio of 1/r in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the case r = 2 they use a finite field of size 3) and an optimal update property.

We study error-correcting codes for permutations under the infinity norm, motivated by a novel storage scheme for flash memories calledrank modulation. In this scheme, a set of$n$flash cells are combined to create a single virtual multilevel cell. Information is stored in the permutation induced by the cell charge levels. Spike errors, which are characterized by a limited-magnitude change in cell charge levels, correspond to a low-distance change under the infinity norm. We define codes protecting against spike errors, called limited-magnitude rank-modulation codes (LMRM codes), and present several constructions for these codes, some resulting in optimal codes. These codes admit simple recursive, and sometimes direct, encoding and decoding procedures. We also provide lower and upper bounds on the maximal size of LMRM codes both in the general case, and in the case where the codes form a subgroup of the symmetric group. In the asymptotic analysis, the codes we construct outperform the Gilbert–Varshamov-like bound estimate.