Paper Info
Title
Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
Abstract
In distributed matrix multiplication, a common scenario is to assign each worker a fraction of the multiplication task, by partitioning the input matrices into smaller submatrices. In particular, by dividing two input matrices into m-by-p and p-by-n subblocks, a single multiplication task can be viewed as computing linear combinations of pmn submatrix products, which can be assigned to pmn workers. Such block-partitioning based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least "cubic" (pmn) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, meaning that the final product can be recovered from any subset of multiplication results with a size order-wise smaller than pmn. In this work, we show that entangled polynomial codes can be further extended to also include these three important settings, and provide a unified framework that order-wise reduces the total computational costs upon the state of the arts by achieving subcubic recovery thresholds.
Year
DOI
Venue
2020
10.1109/ISIT44484.2020.9174167
2020 IEEE International Symposium on Information Theory (ISIT)
Keywords
DocType
ISSN
entangled polynomial codes,batch distributed matrix multiplication,cubic barrier,common scenario,input matrices,single multiplication task,computing linear combinations,pmn submatrix products,pmn workers,block-partitioning based designs,cubic number,submatrix multiplications,subcubic recovery threshold,multiplication results,total computational costs
Conference
2157-8095
ISBN
Citations 
PageRank 
978-1-7281-6433-5
2
0.41
References 
Authors
13
2
Name
Order
Citations
PageRank
Qian Yu127223.02
Amir Salman Avestimehr21880157.39