The Taub Faculty of Computer Science Events and Talks

In this work, we present a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of undirected or directed complete graphs, and a code over graphs is a set of graphs. A node failure is an event where all edges in the neighbourhood of the erased 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 optimal codes over graphs can be easily accomplished by MDS codes, their field size has to be at least O(n^2), when n is the number of nodes in the graph. In this work, we present several constructions of codes over graphs with smaller field sizes. To accomplish this task we use constructions of product codes and rank metric codes. Furthermore, we present optimal codes over graphs correcting two node failures, and almost optimal codes over graphs correcting three node failures, over the binary field, when the number of nodes in the graph is a prime number. Lastly, we provide an upper bound on the number of nodes for optimal codes. We also define another new family of codes which will be called codes over trees. Each codeword in such a code will be a tree with a fixed number of nodes. A unique form of a tree, i.e., a topology and an arrangement of its nodes, is information that we want to store and read. Such codes will be constructed with the ability to reconstruct trees with erroneous or erased edges. We will discuss some constructions and bounds on the size of such codes.