Home / Curated / Algorithms / Entangled Polynomial Codes for Straggler-Resilient Distributed Matrix Multiplication

Entangled Polynomial Codes for Straggler-Resilient Distributed Matrix Multiplication

Algorithms AIMech:EntangledPolynomialCodesForStragglerResilientDistributedMatrixMultiplication DRAFT

Aliases: Entangled Polynomial Code, Entangled Polynomial Codes, Bilinear-Complexity Entangled Polynomial Coding

A straggler-resilient linear coded computing method for distributed matrix multiplication C = A^T B across N worker nodes that partitions A in F^{s x r} into p x m blocks A_{j,k} and B in F^{s x t} into p x n blocks B_{j',k'} (allowing each worker to store a 1/(pm) fraction of A and a 1/(pn) fraction of B) and encodes worker i's stored submatrices at distinct evaluation point x_i in F as A_tilde_i = sum_{j=0}^{p-1} sum_{k=0}^{m-1} A_{j,k} x_i^{j + k p} and B_tilde_i = sum_{j'=0}^{p-1} sum_{k'=0}^{n-1} B_{j',k'} x_i^{(p - 1 - j') + k' p m}, so that each desired inner-dimension sum C_{k,k'} = sum_{j=0}^{p-1} A_{j,k}^T B_{j,k'} aligns onto the unique degree-(p - 1 + k p + k' p m) coefficient of the degree-(p m n + p - 2) worker product polynomial h(x_i) = A_tilde_i^T B_tilde_i and can be recovered from any K_{entangled-poly} = p m n + p - 1 non-straggling workers.

Identity Notes & Concept Scope Distinct from Polynomial Codes (AIMech:PolynomialCodesForStragglerResilientHighDimensionalCodedMatrixMultiplication, which restrict p = 1 and partition input matrices only along their outer dimensions) and from MatDot and PolyDot Codes (AIMech:MatDotAndPolyDotCodesForStragglerResilientCodedMatrixMultiplication, where PolyDot achieves recovery threshold m^2 (2p - 1) for m = n because unaligned inner-dimension cross-terms double the polynomial degree in p): Entangled Polynomial Codes (Yu, Maddah-Ali, & Avestimehr, ISIT 2018 / IEEE TIT 2020) assign exponent strides (alpha, beta, theta) = (1, p, p m) with reversed inner-dimension powers x_i^j and x_i^{p-1-j'} to align all p summands of each C_{k,k'} onto x_i^{p-1 + k p + k' p m}, reducing the recovery threshold by a factor of 2 to p m n + p - 1 and further to 2 R(p, m, n) - 1 via bilinear-complexity tensor decompositions.

Claims & Grounded Evidence

3 Claims

Mechanism #epc-degree-alignment-recovery-threshold

By choosing exponent strides (alpha, beta, theta) = (1, p, p m) in Definition 4 (Eq. 28), each worker i evaluates a polynomial h(x_i) = A_tilde_i^T B_tilde_i of degree p m n + p - 2 in which each subblock C_{k,k'} = sum_{j=0}^{p-1} A_{j,k}^T B_{j,k'} appears as the exact coefficient of x_i^{p - 1 + k p + k' p m}, achieving recovery threshold K_{entangled-poly} = p m n + p - 1 from any subset of p m n + p - 1 non-straggling workers via polynomial interpolation.

supports Source: Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding · Locator: Section III Theorem 1 p. 3 Eq. 10; Section IV-B p. 7 Eq. 28-29

Scope #epc-linear-converse-and-bilinear-complexity-bound

Entangled Polynomial Codes achieve the optimal linear recovery threshold K*_{linear} = p m n + p - 1 = p m + p n - 1 whenever m = 1 or n = 1 (Theorem 2, Lemma 1, Eq. 12 and 30), and for arbitrary (p, m, n) an improved bilinear-complexity construction using a rank-R tensor decomposition of m-by-p by p-by-n matrix multiplication achieves recovery threshold 2 R - 1, characterizing K*_{linear} within a factor of 2 as R(p, m, n) <= K*_{linear} <= 2 R(p, m, n) - 1 (Theorem 3, Eq. 15).

supports Source: Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding · Locator: Section III Theorems 2-3 p. 4-5 Eq. 12-15; Section V Lemma 1 p. 8 Eq. 30; Section VI p. 9-10 Eq. 40-48

Limitation #epc-real-field-vandermonde-conditioning-limitation

When implemented over the field of real or complex numbers rather than a finite field, decoding Entangled Polynomial Codes requires interpolating a degree-(p m n + p - 2) polynomial (or degree-(2 R - 2) polynomial in the bilinear-complexity variant), which can suffer from numerical ill-conditioning and floating-point precision loss as p m n grows.

supports Source: Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding · Locator: Section VII Concluding Remarks p. 11

⚠️ Curated Limitations & Negative Results

Over real or complex fields, polynomial interpolation of degree p m n + p - 2 or 2 R(p, m, n) - 2 suffers from Vandermonde numerical conditioning degradation as partition counts p, m, n grow.
Achieving the factor-of-2 optimal bound 2 R(p, m, n) - 1 requires an explicit low-rank bilinear-complexity tensor decomposition (a, b, c) for (p, m, n), whose exact minimum rank R(p, m, n) is NP-hard to determine in general.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	Entangled Polynomial Codes provide optimal straggler-resilient coded matrix multiplication across distributed worker nodes in large-scale distributed and federated machine learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r542-primary-pdf`	Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper full_text	ID: https://dblp.org/rec/journals/tit/YuMA20 sha256:19ca132faffc…
`r542-arxiv-abs`	Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (arXiv abstract) Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper abstract_only	ID: https://arxiv.org/abs/1801.07487 sha256:92d512f3a3a6…
`r542-metadata-cr`	Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (Crossref metadata) Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr	primary paper abstract_only	ID: https://dblp.org/rec/journals/tit/YuMA20 sha256:848da46a7d6b…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:25:00Z

Updated: 2026-10-19T10:25:00Z

Source File: data/curated/EntangledPolynomialCodesForStragglerResilientDistributedMatrixMultiplication.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories