Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to optimally deal with straggling workers. The proposed strategy, named as polynomial codes, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. This is the first code that achieves the optimal utilization of redundancy for tolerating stragglers or failures in distributed matrix multiplication. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics including computation latency and communication load. Moreover, we extend this code to distributed convolution and show its order-wise optimality.
This paper extends the coded distributed computing of matrix multiplication proposed in Lee et al, 2016. The idea is to distribute the matrices by pre-multiplying them with the generator matrices of Reed Solomon code. Since Reed-Solomon codes are MDS codes, any K out of N distributed components are sufficient to recover the desired matrix multiplication.
I am somewhat confused by this paper. Reed-Solomon codes ARE defined to be evaluations of polynomials over finite field (or any fields). So why the authors say that they define something new called polynomial code and then follow up by saying the decoding is just like Reed-Solomon code? Reed Solomon codes are MDS code (in fact, Lee et al also used Reed Solomon codes, they just called it MDS codes).
The key idea of using codes for both matrices in matrix-matrix multiplication has appeared recently in Lee et al, 2017. I think there is a major problem from an application point of view in this paper that was not there for a simple matrix-vector multiplication of Lee et al of 2016. In case of matrix-vector multiplication A times x of Lee et al, 2016, the matrix A was fixed and x was variable. The matrix A was coded and distributed to the workers. x was uncoded. So the encoding is done only one time. It does indeed speed up the distributed computing. On the other hand, in this paper both the matrices A and B that are to be multiplied are being coded up. As a result when two matrices are given to multiply, a central node has to do a lot of polynomial evaluations and then distribute the evaluations among workers. The overhead for the central node seem to be way more than the actual computing task. Notably, this has to be done every time; as opposed to the one-time-encoding of Lee et al, 2016, or Dutta et al, 2016. 
 Also surprising is the lack of experimental results. Most of the related literature is interesting because of the experimental superior performance they exhibit in real systems. This paper does not make any attempt in that direction.  However since theoretically it is not that novel, and given the overhead in evaluating the polynomials, one really needs experimental validation of the methods.
========================
After the rebuttal:
I did not initially see the making of the product MDS as a big deal (i.e. the condition that no two terms in the expression (16) have same exponent of x is not that difficult to satisfy). But on second thought, the simplicity should not be deterrent, given that the previous papers kept this problem open.
There is one other point. What I understand is that each matrix is encoded using polynomials such that the product becomes codewords of Reed_Solomon codes. I do not necessarily agree with the term Polynomial code and the claim that a new class of code has been discovered.
Finally, it is not easy to approximate matrix multiplications over reals with finite field multiplication. I don't know why that is being seen as straight-forward quantization.