Seminar Announcement
Date: Thurday, 24 August 2023
Time: 2:00 PM
Venue: Seminar Hall
How Non-Commutativity Helps Data Centers: Maximally Recoverable Codes from Skew Polynomials
Venkatesan Guruswami
UC Berkeley and Simons Institute.
24-08-23

---

Abstract

Locally Repairable Codes (LRCs) allow for recovery from a small number of erased symbols in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of local and global erasure resilience, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local repair groups. This makes them attractive for use in distributed storage systems where they have been deployed in certain parameter regimes.
Locally Repairable Codes (LRCs) allow for recovery from a small number of erased symbols in a local manner based on just a few other codeword symbols. A maximally recoverable (MR) LRC offers the best possible blend of local and global erasure resilience, guaranteeing recovery from all erasure patterns which are information-theoretically correctable given the presence of local repair groups. This makes them attractive for use in distributed storage systems where they have been deployed in certain parameter regimes.
Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We will discuss a framework based on skew polynomials (a non-commutative analog of polynomial rings that dates back to (Ore, 1933)) that yields MR LRCs over the smallest known alphabets in many practically relevant parameter regimes, including matching a lower bound in an interesting case.
The talk will introduce maximal recoverable codes, and describe skew polynomials and non-singular matrices constructed using them which lead to good MR LRCs. Time permitting, we will mention some surprising connections between MR codes and list decoding.
Based on joint work with Sivakanth Gopi.Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We will discuss a framework based on skew polynomials (a non-commutative analog of polynomial rings that dates back to (Ore, 1933)) that yields MR LRCs over the smallest known alphabets in many practically relevant parameter regimes, including matching a lower bound in an interesting case.
The talk will introduce maximal recoverable codes, and describe skew polynomials and non-singular matrices constructed using them which lead to good MR LRCs. Time permitting, we will mention some surprising connections between MR codes and list decoding.
Based on joint work with Sivakanth Gopi.