Abstract
The sub-packetization $\ell$ and the field size $q$ are of paramount importance in MSR code constructions. For optimal-access MSR codes, Balaji \emph{et al.} proved that $\ell \geq s^{\left\lceil n/s \right\rceil}$, where $s = d-k+1$. Rawat \emph{et al.} showed that this lower bound is attainable for all admissible values of $d$ when the field size is exponential in $n$. After that, tremendous efforts have been devoted to reducing the field size. However, so far, reduction to a linear field size is only available for $d\in\{k+1,k+2,k+3\}$ and $d=n-1$. In this paper, we construct the first class of explicit optimal-access MSR codes with the smallest sub-packetization $\ell = s^{\left\lceil n/s \right\rceil}$ for all $d$ between $k+1$ and $n-1$, resolving an open problem in the survey (Ramkumar \emph{et al.}, Foundations and Trends in Communications and Information Theory: Vol. 19: No. 4). We further propose another class of explicit MSR code constructions (not optimal-access) with an even smaller sub-packetization $s^{\left\lceil n/(s+1)\right\rceil}$ for all admissible values of $d$, making significant progress on another open problem in the survey. Previously, MSR codes with $\ell=s^{\left\lceil n/(s+1)\right\rceil}$ and $q=O(n)$ were only known for $d=k+1$ and $d=n-1$. The key insight that enables a linear field size in our construction is to reduce $\binom{n}{r}$ global constraints of non-vanishing determinants to $O_s(n)$ local ones, which is achieved by carefully designing the parity check matrices.