IC Colloquium : Maximally recoverable codes
Event details
| Date | 13.11.2017 |
| Hour | 16:15 › 17:30 |
| Location | |
| Category | Conferences - Seminars |
By : Sergey Yekhanin - Microsoft Research
Abstract :
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).
Bio :
Sergey Yekhanin received his Specialist Diploma from Moscow State University in 2002, and his Ph.D. from MIT in 2007. In 2007-2008 he was a Member of the School of Mathematics at the Institute for Advanced Study at Princeton. In 2008 Dr. Yekhanin joined Microsoft Research where he is currently a Senior Researcher. Dr. Yekhanin's research interests lie in algebraic coding theory, combinatorics, and computational complexity theory. He is currently focusing on coding for distributed storage, coding for DNA storage, and practical differentially private algorithms. Dr. Yekhanin is a recipient of the ACM Doctoral Dissertation Award (2007) and the IEEE Communications Society and Information Theory Society Joint Paper Award (2014). He has been an invited speaker at the 2014 International Congress of Mathematicians.
More information
Abstract :
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).
Bio :
Sergey Yekhanin received his Specialist Diploma from Moscow State University in 2002, and his Ph.D. from MIT in 2007. In 2007-2008 he was a Member of the School of Mathematics at the Institute for Advanced Study at Princeton. In 2008 Dr. Yekhanin joined Microsoft Research where he is currently a Senior Researcher. Dr. Yekhanin's research interests lie in algebraic coding theory, combinatorics, and computational complexity theory. He is currently focusing on coding for distributed storage, coding for DNA storage, and practical differentially private algorithms. Dr. Yekhanin is a recipient of the ACM Doctoral Dissertation Award (2007) and the IEEE Communications Society and Information Theory Society Joint Paper Award (2014). He has been an invited speaker at the 2014 International Congress of Mathematicians.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Michael Kapralov