Title: New Bounds on the Field Size for Maximally Recoverable Codes Instantiating Grid-like Topologies,
Abstract: In recent years, the rapidly increasing amounts of data created and processed
through the internet resulted in distributed storage systems employing erasure
coding based schemes. Aiming to balance the tradeoff between data recovery for
correlated failures and efficient encoding and decoding, distributed storage
systems employing maximally recoverable codes came up. Unifying a number of
topologies considered both in theory and practice, Gopalan \cite{Gopalan2017}
initiated the study of maximally recoverable codes for grid-like topologies.
In this paper, we focus on the maximally recoverable codes that instantiate
grid-like topologies $T_{m\times n}(1,b,0)$. To characterize the property of
codes for these topologies, we introduce the notion of \emph{pseudo-parity
check matrix}. Then, using the hypergraph independent set approach, we
establish the first polynomial upper bound on the field size needed for
achieving the maximal recoverability in topologies $T_{m\times n}(1,b,0)$, when
$n$ is large enough. And we further improve this general upper bound for
topologies $T_{4\times n}(1,2,0)$ and $T_{3\times n}(1,3,0)$. By relating the
problem to generalized \emph{Sidon sets} in $\mathbb{F}_q$, we also obtain
non-trivial lower bounds on the field size for maximally recoverable codes that
instantiate topologies $T_{4\times n}(1,2,0)$ and $T_{3\times n}(1,3,0)$.