THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. A functional$k$-batch code of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. These codes are designed to recover any multiset of$k$requests, each being a linear combination of the information bits, by$k$disjoint subsets of servers. A recent conjecture suggests that for any set of$k=2^{s-1}$requests, the optimal solution requires$2^{s}-1$servers. This paper shows that the problem of functional$k$-batch codes is equivalent to several other problems. Using these equivalences, sufficient conditions are derived that improve the understanding of the problem and enhance the ability to find the optimal solution.

Abstract We derive the coding capacity for duplication-correcting codes capable of correcting any number of duplications. We do so both for reverse-complement duplications, as well as palindromic (reverse) duplications. We show that except for duplication-length 1, the coding capacity is 0. When the duplication length is 1, the coding capacity depends on the alphabet size, and we construct optimal codes.

Afunctional$k$-batchcode of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. Any multiset request of size$k$of linear combinations (or requests) of the information bits can be recovered by$k$disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of$s$and$k$. A recent conjecture states that for any$k=2^{s-1}$requests the optimal solution requires$2^{s}-1$servers. This conjecture is verified for$s \leqslant 5$but previous work could only show that codes with$n=2^{s}-1$servers can support a solution for$k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $requests. This paper reduces this gap and shows the existence of codes for$k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$requests with the same number of servers. Another construction in the paper provides a code with$n=2^{s+1}-2$servers and$k=2^{s}$requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions forparallel Random I/O (RIO)codes.

A functional k-batch code of dimension$s$consists of$n$servers storing linear combinations of$s$linearly independent information bits. Any multiset request of size$k$of linear combinations (or requests) of the information bits can be recovered by$k$disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of$s$and$k$. A recent conjecture states that for any$k=2^{s-1}$requests the optimal solution requires$2^{s}-1$servers. This conjecture is verified for$s\leqslant 5$but previous work could only show that codes with$n=2^{s}-1$servers can support a solution for$k=2^{s-2}+2^{s-4}+ \left\lfloor\frac{2^{s/2}}{\sqrt{24}} \right\rfloor$requests. This paper reduces this gap and shows the existence of codes for$k= \lfloor\frac{2}{3}2^{s-1}\rfloor$requests with the same number of servers. Another construction in the paper provides a code with$n=2^{s+1}-2$servers and$k=2^{s}$requests, which is an optimal result. These constructions are mainly based on Hadamard codes and equivalently provide constructions for parallel Random I/O (RIO) codes.

In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the path tree.

In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the line tree.

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called ρ-node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any ρ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in ℤn. These codes are at most a single bit away from optimality.

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called ρ-node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any ρ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in Zn. These codes are at most a single bit away from optimality.

Motivated by systems where the information is represented by a graph, such as neural networks, associative memories, and distributed systems, we present in this work a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of an undirected graph, and a code over graphs is a set of graphs. A node failure is the event where all edges in the neighborhood of the failed node have been erased. We say that a code over graphs can tolerate ρ node failures if it can correct the erased edges of any ρ failed nodes in the graph. While the construction of such codes can be easily accomplished by MDS codes, their field size has to be at least), O(n2) when n is the number of nodes in the graph. In this work we present several constructions of codes over graphs with smaller field size. In particular, we present optimal codes over graphs correcting two node failures over the binary field, when the number of nodes in the graph is a prime number. We also present a construction of codes over graphs correcting ρ node failures for all ρ over a field of size at least (n + 1)/2 - 1, and show how to improve this construction for optimal codes when ρ = 2,3.

In this work we continue the study of a new class of codes, called codes over graphs. Here we consider storage systems where the information is stored on the edges of a complete directed graph with n nodes. The failure model we consider is of node failures which are erasures of all edges, both incoming and outgoing, connected to the failed node. It is said that a code over graphs is a ρ-node-erasure-correcting code if it can correct the failure of any ρ nodes in the graphs of the code. While the construction of such optimal codes is an easy task if the field size is O(n2), our main goal in the paper is the construction of codes over smaller fields. In particular, our main result is the construction of optimal binary codes over graphs which correct two node failures with a prime number of nodes.