MSR Codes with Linear Field Size and Smallest Sub-packetization for Any Number of Helper Nodes

The sub-packetization l and the field size q are of paramount importance in MSR code constructions. For optimal-access MSR codes, Balaji et al. proved that l >= s (inverted right perpendicular n/s inverted left perpendicular), where s = d - k+ 1. Rawat 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 epsilon {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 l = s.n/s. for all d between k+1 and n-1, resolving an open problem in the survey (Ramkumar 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 optimalaccess) with an even smaller sub-packetization s(inverted right perpendicular n/s+1 inverted left perpendicular). for all admissible values of d, making significant progress on another open problem in the survey. Previously, MSR codes with l = ss(inverted right perpendicular n/s+1 inverted left perpendicular). 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 ((n)(r)) global constraints of non-vanishing determinants to O-s(n) local ones, which is achieved by carefully designing a group of kernel matrices and then blowing them up to get parity check submatrices.