Speeding Up Private Distributed Matrix Multiplication via Bivariate Polynomial Codes

We consider the problem of private distributed matrix multiplication under limited resources. Coded computation has been shown to be an effective solution in distributed matrix multiplication, both providing privacy against the workers and boosting the computation speed by efficiently mitigating stragglers. In this work, we propose the use of recently-introduced bivariate polynomial codes to further speed up private distributed matrix multiplication by exploiting the partial work done by the stragglers rather than completely ignoring them. We show that the proposed approach reduces the average computation time of private distributed matrix multiplication compared to its competitors in the literature while improving the upload communication cost and the workers' storage efficiency.This work was partially funded by the European Research Council (ERC) through Starting Grant BEACON (no. 677854) and by the UK EPSRC (grant no. EP/T023600/1) under the CHIST-ERA program. The work of J. Gómez-Vilardebó was supported in part by the Catalan Government under Grant SGR2017-1479, and by the Spanish Government under Grant RTI2018- 099722-B-100 (ARISTIDES