Improved Maximally Recoverable LRCs using Skew Polynomials - Gopi, Sivakanth; Guruswami, Venkatesan (IEEE Transactions on Information Theory, 2020)
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.