Fetching the paper…

Reading the bibliography…

2018

GASP Codes for Secure Distributed Matrix Multiplication

D'Oliveira, Rafael G. L., Rouayheb, Salim El, Karpuk, David

Original
PDF
Post on X

Understand

We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers.

We construct polynomial codes for SDMM by studying a combinatorial problem on a special type of addition table, which we call the degree table.
The codes are based on arithmetic progressions, and are thus named GASP (Gap Additive Secure Polynomial) Codes.
GASP Codes are shown to outperform all previously known polynomial codes for secure distributed matrix multiplication in terms of download rate.

GASP Codes for Secure Distributed Matrix Multiplication · Around

Built on

A. Shamir, “How to share a secret,”
1979
Earlier work this paper cites.
R. Bitar, P. Parag, and S. El Rouayheb, “Minimizing latency for secure distributed computing,” in
2017
Earlier work this paper cites.
Q. Yu, M.A. Maddah-Ali, A.S. Avestimehr, “ Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication,”
Original
2017
Earlier work this paper cites.
W.-T. Chang, R. Tandon, “ On the Capacity of Secure Distributed Matrix Multiplication,”
Original
2018
Earlier work this paper cites.
J. Kakar, S. Ebadifar, and A. Sezgin, “ Rate-Efficiency and Straggler-Robustness through Partition in Distributed Two-Sided Secure Matrix Computation,”
Original
2018
Earlier work this paper cites.

Similar

Q. Yu, S. Li, N. Raviv, S.M.M. Kalan, M. Soltanolkotabi, A.S. Avestimehr, “Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy,”
Original
2018
Cited alongside, same era.
Q. Yu, M.A. Maddah-Ali, A.S. Avestimehr, “Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding,”
Original
2018
Cited alongside, same era.
S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V. Cadambe, P. Grover, “On the Optimal Recovery Threshold of Coded Matrix Multiplication,”
Original
2018
Cited alongside, same era.
U. Sheth, S. Dutta, M. Chaudhari, H. Jeong, Y. Yang, J. Kohonen, T. Roos, P. Grover, “An Application of Storage-Optimal MatDot Codes for Coded Matrix Multiplication: Fast k-Nearest Neighbors Estimation,”
Original
2018
Cited alongside, same era.

Then

S. Li, M.A. Maddah-Ali, Q. Yu and A.S. Avestimehr, “A Fundamental Tradeoff Between Computation and Communication in Distributed Computing,” in
2018
Closest in time.
H. Yang and J. Lee, “Secure Distributed Computing With Straggling Servers Using Polynomial Codes,” in
2019
Closest in time.
N. Raviv and D. Karpuk, “Private Polynomial Computation from Lagrange Encoding,” in
2019
Closest in time.
R. G. L. D’Oliveira, S. El Rouayheb, D. Heinlein, D. Karpuk, “Notes on Communication and Computation in Secure Distributed Matrix Multiplication,”
Original
2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…