SFU Theory Seminar Series: Sergey Yekhanin (CANCELLED)

This seminar is cancelled and will be scheduled for a later date.

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An LRC is a q-ary code, where encoding is as a two stage process. On the first stage h redundant symbols are generated from k data symbols. On the second stage k+h symbols are partitioned into smaller sets and each set is extended with a redundant symbols using an MDS code to form a local group. Local groups ensure that when a small number of coordinates are erased, any missing coordinate can be recovered by accessing just a few symbols. Also, if a larger number of coordinates is erased; then missing symbols can still be recovered by potentially accessing all remaining symbols.

An LRC code as above is Maximally Recoverable (MR), if it corrects all erasure patterns which are information theoretically correctable given the presence of local groups. Obtaining MR LRCs over finite fields of minimal size is important in practice and has been the goal of a line of work in coding theory. In this talk we review state of the art in this area and present several new results, including the first super-linear lower bound for the field size of maximally recoverable LRCs. (Joint work with Sivakanth Gopi and Venkat Guruswami).