Systematic Matrix Multiplication Codes

The problem of computing distributed matrix multiplication reliably has been of immense interest for several decades. Recently, it was shown that Polynomial codes achieve the theoretically minimum recovery bandwidth. However, existing constructions for Polynomial codes are nonsystematic, which can impose substantial overhead in distributed computing. In this paper, we propose two different systematic code constructions that achieve the same recovery bandwidth as Polynomial codes. First uses a random coding argument, and the second is polynomial-based, but uses bivariate instead of originally used univariate polynomials. We show that the proposed constructions are communication optimal with high probability.