All scheduled dates:
Title: Nonlinear Repair of Reed-Solomon Codes
Abstract: The problem of repairing linear codes, and in particular, Reed Solomon (RS) codes, has attracted a lot of attention in recent years due to its importance in distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. There are examples of RS codes with efficient repair schemes, and some are even optimal. However, these schemes fall short in several aspects; for example, they require a considerable field extension degree, and in particular, they do not work over prime fields. In this talk, we will explore the power of nonlinear repair schemes of RS codes and show that such schemes are crucial over prime fields, and in some cases, they outperform all linear schemes.
The talk is based on joint works with Noah Shutty, Itzhak Tamo, and Mary Wootters.
Title: How Non-Commutativity Helps Data Centers: Maximally Recoverable
Codes from Skew Polynomials
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 (also called
PMDS codes) offers the best possible blend of local and global erasure
resilience, guaranteeing recovery from all erasure patterns which are
information-theoretically correctable given the constraints of local
repair groups. This makes them attractive for use in distributed
storage systems where they have been deployed in certain parameter
Random constructions easily show the existence of MR LRCs over very
large fields, but a major 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
construction 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
The talk will introduce the concept of maximal recoverability, and
describe skew polynomials and non-singular matrices constructed using
them which lead to good MR LRCs. Time permitting, we will mention some
exciting recent connections between MR codes and list decoding, forged
by Brakensiek-Gopi-Makam in their work on higher order MDS codes.
Based on joint work with Sivakanth Gopi.