Improved Maximally Recoverable LRCs using Skew Polynomials

An (n,r,h,a,q)-LRC is a linear code over F_q of length n, whose codeword symbols are partitioned into n/r local groups each of size r. Each local group satisfies ‘a’ local parity checks to recover from ‘a’ erasures in that local group and there are further h global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it can correct all erasure patterns which are information-theoretically correctable given this structure—these are precisely patterns with up to ‘a’ erasures in each local group and an additional h erasures anywhere in the codeword.

We give an explicit construction of (n,r,h,a,q)-MR LRCs with field size q bounded by max{r,n/r}^{min{h,r-a}}. This significantly improves upon known constructions in most parameter ranges. Moreover, it matches the best known lower bound in an interesting range of parameters where r ~ sqrt{n}, r-a ~ sqrt{n}) and h is a fixed constant with h<= a+2, achieving the optimal field size of  ~ n^{h/2}. Our construction is based on the theory of skew polynomials.