Collaborative Decoding of Polynomial Codes for Distributed Computation

We show that polynomial codes (and some related codes) used for distributed matrix multiplication are interleaved Reed-Solomon codes and, hence, can be collaboratively decoded. We consider a fault tolerant setup where t worker nodes return erroneous values. For an additive random Gaussian error model, we show that for all t < N-K, errors can be corrected with probability 1. Further, numerical results show that in the presence of additive errors, when L Reed-Solomon codes are collaboratively decoded, the numerical stability in recovering the error locator polynomial improves with increasing L.