NSF-BSF: CIF: Small: From storage codes to recoverable systems

Overview: The proposed research focuses on developing two directions of data representation on graphs motivated by the problems of storage coding and index coding on finite graphs. In the first part the project will pursue constructions of storage codes on graphs relying on a link between linear storage coding and the developing construction methods of LDPC quantum codes relying on Cayley graphs and higher-dimensional complexes. The project will also pursue the problem of recovering multiple failed vertices in storage codes on regular graphs relying on the link between erasure correction and percolation threshold on the graph.

In the second part the project aims to study and develop the notion of recoverable systems introduced recently in a joint work of the Pls. Recoverable systems represent an extension of storage codes to infinite graphs, and their analysis involves a range of tools previously unclaimed in the studies of storage/index codes. The problems pursued in this part include bounding the capacity of recoverable systems as a function of the shape and size of the neighborhood used for the recovery, enumeration and classification of capacity maximizing systems, constructions of such systems. The project also plans to study a probabilistic version of erasure correction under some recovery guarantees, and aims to identify and classify entropy—maximizing measures on the graphs as well as the analogs of this problem for 2D lattices and various versions of erasure recovery procedures in the case of multiple concurrent failures. Keywords: Codes for storage; repairable networks; LDPC quantum codes; recoverable systems; con strained systems; entropy maximizing measures.