Improved Maximally Recoverable LRCs using Skew Polynomials

An $(n,r,h,a,q)$-LRC is a linear code over $\mathbb{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 $\left(O\left(\max\{r,n/r\}\right)\right)^{\min\{h,r-a\}}$. This significantly improves upon known constructions in most parameter ranges. Moreover, it matches the best known lower bound from~\cite{gopi2020maximally} in an interesting special case when $r=\Theta(\sqrt{n})$ and $h,a$ are constants with $h \le a+2$, achieving the optimal field size of $\Theta_{a,h}(n^{h/2}).$ Our construction is based on the theory of skew polynomials.