论文标题
纠缠的多项式代码，用于安全，私人和批处理矩阵乘法：打破“立方”屏障
Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
论文作者
论文摘要
在分布式矩阵乘法中，一个常见的情况是通过将输入矩阵分配到较小的子膜片中来分配每个工人的乘法任务的一部分。特别是，通过将两个输入矩阵分为$ m $ - by-$ p $和$ p $ - by- $ n $ subblocks，可以将单个乘法任务视为$ PMN $ submatrix产品的计算线性组合，可以将其分配给$ PMN $ pmn $工人。此类基于区块的设计已在安全，私人和批处理计算的主题下进行了广泛的研究，其中所有艺术状态都需要至少计算“立方”（$ PMN $）subpatrix乘法数。纠缠的多项式代码首先是用于缓解straggler的，为打破立方屏障提供了强大的方法。它实现了亚皮的恢复阈值，这意味着可以从\ emph {any}子集中恢复最终产品，其大小小于$ pmn $的乘法结果。在这项工作中，我们表明可以进一步扩展纠缠的多项式代码，还包括这三个重要设置，并提供了一个统一的框架，以订单来降低艺术状态的总计算成本，通过实现亚双比子恢复阈值。
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 \emph{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.
