Ph.D Thesis

Ph.D StudentYohananov Lev
SubjectCodes Over Graphs
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Eitan Yaakobi
Full Thesis textFull thesis text - English Version


In this work, codes over graphs are studied. A code over graphs is a set of complete graphs with self-loops with a fixed number of nodes n. Every graph-codeword in such codes stores the information symbols over some alphabet ⅀ on its edges. If a code over graphs contains only directed, undirected complete graphs with self-loops, then it is called a directed, undirected code over graphs, respectively. The number of edges in every codeword of the directed, undirected codes over graphs is n2, n(n)/2, respectively. A node failure is the event in which the entire neighborhood set of edges of a node is erased. Codes that tolerate ρ node failures which are of maximal cardinality are called optimal. By using MDS codes, optimal codes over graphs are constructed over a field size O(n2). Several optimal constructions with smaller field sizes are presented in this work.

Another family of codes, called codes over trees, is studied. A code over trees is a set of undirected trees with a fixed number of nodes. Every tree-codeword corresponds to unique information which is given by the structure of the tree-codeword. These codes are constructed to tolerate any ρ edge erasures, which transform a tree into a forest with ρ sub-trees. The tree distance between two trees is the number of edges that belong to exactly one tree. Studying this distance measure is important for many applications that use trees and properties on their locality and the number of neighbor trees. The largest size of codes over trees with a prescribed minimum tree distance is investigated. In addition, upper bounds, several constructions, and decoding schemes are presented.

The last work of this thesis studies functional k-batch codes. A functional k-batch code of length n and dimension s encodes s information bits x0,x1,?,xs-1 into n encoded bits y0,y1,?,yn-1. These codes satisfy the following requirement: for any request of k linear combinations v0,v1,?,vk-1 of the s information bits, there are k pairwise disjoint subsets R0,R1,?,Rk-1 of the set {0,1,?,n-1} such that every recovery set Ri that is denoted by {a1,a2,?,at}, satisfies ya1a2?at=vi. A code is called optimal if for given values of s and k it has the minimal number of the encoded bits. A recent conjecture states that for s information bits and any k=2s-1 requests, the optimal solution requires 2s-1 encoded bits. This conjecture has been verified only for s < 6. Previous work showed that codes with n = 2s-1 encoded bits can support k=2s-2 2s-4 O(2s/2) requests. This work reduces this gap and shows the existence of such codes while the number of requests is roughly (5/6)2s-1-s. Another construction in the work provides functional batch codes with n=2s-2 servers and k=2s requests, which are optimal codes.