New Bounds for Matrix Multiplication: from Alpha to Omega

1 Introduction

• Known matrix-multiplication techniques cannot achieve ω = 2, while within the laser-method framework, how close one can get to the 2.3078 barrier remains an open question.Source: §1 · p. 2
• Rectangular exponents matter for APSP, minimum witnesses, bottleneck paths, and clique detection, while α measures progress toward the ideal ω = 2.In particular, µ satisfies ω(1, µ, 1) = 1 + 2µ, and ω(1, 2, 1) governs 4-clique detection.Source: §1 · p. 2

1.1 Our Results

• α > 0.321334, µ < 0.527661, and ω(1, 2, 1) < 3.250385, improving previous bounds 0.31389, 0.5286, and 3.25164, respectively.The paper’s new laser-method variant improves both square and rectangular matrix multiplication bounds.Source: §1.1 · pp. 2–3
• The improved bounds yield O(n2.527661) APSP algorithms and O(n3.250385) algorithms for finding 4-cliques.The APSP consequence also applies to minimum witnesses for Boolean Matrix Multiplication and All-Pairs Bottleneck Paths.Source: §1.1 · p. 3
• The new method improves prior rectangular-multiplication bounds and reports additional values in Table 1, including comparisons with [DWZ23] and [LGU18].Table 1 analyzes the fourth power of the CW tensor; its κ = 1 comparison uses [DWZ23]’s eighth-power analysis, while other entries use [LGU18].Source: §1.1 · pp. 2–3, Table 1 · p. 3
• Independently, Le Gall [LG24] improved [LGU18] for rectangular multiplication, but this paper’s method both generalizes and improves [DWZ23], yielding better bounds than [LG24].The paper notes that Le Gall’s method does not match the square-multiplication bound from [DWZ23] for technical reasons.Source: §1.1 · p. 3

2.1 Overview of Previous Work

• The laser method raises ω bounds by tensor-power decomposition, zeroing variable blocks, and applying Schönhage’s asymptotic sum inequality to retained matrix multiplication tensors.The method seeks a direct sum whose matrix multiplication value is large relative to the tensor’s asymptotic rank.Source: §2.1 · pp. 4–5
• Prior work [DWZ23] moved recursive zeroing earlier and relaxed independence, but its technique shared level-ℓ blocks in only one variable dimension and required asymmetric zeroing.Their construction also produced copies with holes restricted to Z-variables.Source: §2.1 · pp. 7–8

2.2 Our Improvements

• Complete split distributions move zeroing directly to level-1 blocks, enabling level-1 independence and potentially more retained tensor copies than [DWZ23].This relaxed independence can improve the bound on ω through the asymptotic sum inequality.Source: §2.1 · p. 7, §2.2 · p. 9
• Complete split distributions record proportions of all 32^(2ℓ−1) chunk types, so constraints persist through recursive levels rather than disappearing after one split.This persistence motivates enforcing the distributions across X-, Y-, and Z-variables and creates the need to handle holes in all three dimensions.Source: §2.2 · pp. 9–10
• The complete three-dimensional enforcement introduces a technical issue because recursive tensor copies cannot be freely rewritten by index permutation while preserving the imposed constraints.The issue arises even in a simplified single-support setting and affects how subsequent recursive analyses are defined.Source: §2.2 · p. 10
• The hole fraction drops from 1−2−o(N) to 2−Ω(n) by relaxing zeroing conditions and using concentration bounds.The relaxed construction gives more flexibility in T1 than T2, while a uniformly random level-1 block satisfies the target distribution with probability 1−2−Ω(n).Source: §2.2 · p. 11
• The paper generalizes to repair holes simultaneously in all three dimensions for a broad class of tensors, requiring a hole fraction below O(1/log N).This requirement is ensured by the preceding hole-reduction step, while retaining the broad tensor support of [DWZ23].Source: §2.2 · p. 11
• The recursive repair decomposes a broken tensor into eight subtensors and recurses on seven subproblems whose variable sets are smaller by the hole fraction.When the hole fraction c is sufficiently small, the number of broken tensor copies remains affordable.Source: §2.2 · pp. 11–12
• For rectangular multiplication, the analysis applies the laser method jointly to multiple constituent tensors because their cyclic proportions may differ.This follows the framework of Le Gall [LG12] and [LGU18] for producing tensors of the form ⟨a, aκ, a⟩ and bounding ω(1, κ, 1).Source: §2.2 · p. 12
• Combining the refined laser method with asymmetric hashing fails to improve the survival gap: shared ZK blocks prevent zeroing all three blocks, leaving probabilities p versus p2.The resulting bound is therefore the same as in the older approach.Source: §2.2 · p. 12

3.1 Tensors and Tensor Operations

• A tensor T is a trilinear form over variable sets X, Y, and Z and a field F.The three variable sets are called the tensor’s support.Source: §3.1 · p. 13
• All coefficients a_i,j,k are in F, and tensors with only 0–1 coefficients can be viewed over any field F.All tensors used in the paper have 0–1 coefficients.Source: §3.1 · p. 13
• The sum T + T′ is defined only when both tensors have the same support sets, combining corresponding coefficients.The resulting form uses the common variables X, Y, and Z.Source: §3.1 · p. 13
• The direct sum T ⊕ T′ sums tensors after relabeling their variables onto disjoint unions of the three support sets.When the supports are already disjoint, the tensors are independent; T ⊕n denotes n independent copies.Source: §3.1 · p. 13
• The tensor product, or Kronecker product, forms a tensor over the Cartesian-product variable sets X × X′, Y × Y′, and Z × Z′.T ⊗n denotes the n-th tensor power of T.Source: §3.1 · p. 13
• T and T′ are isomorphic, written T ≡ T′, when their support sizes match and coefficient arrays agree after separate permutations of each variable set.Thus, isomorphism means equivalence up to relabeling variables.Source: §3.1 · p. 13

3.2 Tensor Rank

• Tensor rank R(T) is the minimum number of rank-one terms in a decomposition of T.The resulting sum is called a rank decomposition.Source: §3.2 · p. 14
• Tensor rank is subadditive under addition: R(T + T′) ≤ R(T) + R(T′).Source: §3.2 · p. 14
• The asymptotic rank eR(T) is defined from tensor powers and is well-defined by Fekete’s lemma.It is upper bounded by R(T ⊗m)^(1/m) for every fixed integer m > 0.Source: §3.2 · p. 14

3.3 Degenerations, Restrictions, Zero-outs

• A degeneration T ⊵ T′ uses F[λ]-linear maps over the polynomial ring F[λ] to transform T into T′.Source: §3.3 · p. 14
• Degeneration preserves an asymptotic-rank upper bound: if T′ ⊵ T, then eR(T′) ≤ eR(T).Source: §3.3 · p. 14
• A restriction is a degeneration whose maps φX, φY, φZ are F-linear rather than F[λ]-linear.Source: §3.3 · p. 15
• In the laser method, zero-outs are the restricted operations considered: selected subsets X′ ⊆ X, Y′ ⊆ Y, and Z′ ⊆ Z are retained while the remaining variables are set to zero.The resulting tensor T′ = T|X′,Y′,Z′ is called a subtensor over X′, Y′, Z′.Source: §3.3 · p. 15

• The tensor ⟨a,b,c⟩ represents multiplication of an a × b matrix by a b × c matrix, producing an a × c matrix.It is defined over variable sets for the input and output entries.Source: §3.4 · p. 15
• Tensor products satisfy ⟨a,b,c⟩⊗⟨d,e,f⟩ ≡ ⟨ad,be,cf⟩.Source: §3.4 · p. 15
• Following Strassen, a rank bound R(⟨q,q,q⟩) ≤ r yields an arithmetic circuit of size O(n^(log_q r)) for multiplying n × n matrices.Source: §3.4 · p. 15
• The matrix multiplication exponent is defined by ω := inf_{q∈N,q≥2} log_q(R(⟨q,q,q⟩)), equivalently characterizing circuits of size O(n^(ω+ε)).The tensor-power identity ⟨q,q,q⟩^⊗n ≡ ⟨q^n,q^n,q^n⟩ gives the asymptotic-rank formulation.Source: §3.4 · pp. 15–16
• For rectangular multiplication, ω(a,b,c) governs circuits of size O(n^(ω(a,b,c)+ε)) for multiplying n^a × n^b by n^b × n^c matrices.The section focuses on ω(1,κ,1) for κ > 0; ω(1,1,κ), ω(1,κ,1), and ω(κ,1,1) are equal.Source: §3.4 · p. 16

3.5 Schönhage’s Asymptotic Sum Inequality

• Schönhage’s asymptotic sum inequality converts bounds on the asymptotic rank of direct sums of matrix multiplication tensors into upper bounds on ω.The result is attributed to Schönhage.Source: §3.5 · p. 16
• Theorem 3.1 states conditions for applying the inequality to a direct sum of matrix multiplication tensors.It assumes positive integers r > m and parameters a_i, b_i, and c_i.Source: §3.5 · p. 16
• Under the theorem’s equation, ω is bounded by 3τ, where τ lies in [2/3, 1].τ is defined as the solution to the stated equation.Source: §3.5 · p. 16
• The same asymptotic-sum framework also yields bounds for rectangular matrix multiplication exponents.The section introduces an analogous rectangular form before stating Theorem 3.2.Source: §3.5 · p. 16
• Theorem 3.2 extends the asymptotic sum inequality to ω(a, b, c) for positive integers t and q and nonnegative a, b, and c.This formulation targets rectangular matrix multiplication directly.Source: §3.5 · p. 16

3.6 The Coppersmith-Winograd Tensor

• The Coppersmith-Winograd tensor CW_q is defined over variable sets X, Y, and Z indexed from 0 through q+1.Here q is a nonnegative integer.Source: §3.6 · p. 16
• CW_q is the sum of six matrix multiplication tensors, including three copies of ⟨1, 1, 1⟩.The decomposition follows the tensor’s defining terms.Source: §3.6 · pp. 16–17
• Coppersmith and Winograd established the asymptotic-rank bound eR(CW_q) ≤ q + 2.This bound supplies the tensor-rank estimate used in subsequent applications.Source: §3.6 · p. 17

• T^(ℓ) is defined as the (2ℓ−1)-th tensor power of CWq for ℓ≥1.Source: §3.7 · p. 17

Level-1 Partition

• At level 1, CWq partitions its variable sets into three parts, with constituent tensors indexed by triples (i,j,k).Source: §3.7 · p. 17
• A level-1 constituent tensor is nonzero exactly when i+j+k = 2, allowing CWq to be expressed as a sum of constituent tensors.Source: §3.7 · p. 17

• The level-1 partition induces sequence-indexed partitions on higher tensor powers, whose blocks are coarsened by merging sequences with the same sum.Source: §3.7 · pp. 17–18
• At level ℓ, constituent tensors are nonzero exactly when i+j+k = 2ℓ, defining the level-ℓ variable blocks.Source: §3.7 · p. 18

• The tensor power (CWq)⊗N is represented as (T (ℓ))⊗n with N = n · 2ℓ−1, allowing the level-ℓ partition of T (ℓ) to induce a partition.The notation N := n · 2ℓ−1 fixes the relationship between tensor-power size and level.Source: §3.8 · p. 18
• At level 1, variable blocks are indexed by sequences in {0, 1, 2}N, and blocks XˆI, Y ˆJ, Z ˆK form a nonzero subtensor exactly when ˆIt + ˆJt + ˆKt = 2 for every t.Such a subtensor is denoted XˆIY ˆJZ ˆK and called a level-1 triple.Source: §3.8 · p. 18
• At level ℓ, variable blocks are indexed by sequences in {0, 1, . . . , 2ℓ}n, and X_I, Y_J, Z_K form a nonzero subtensor when It + Jt + Kt = 2ℓ for every t.The notation X_IY_JZ_K denotes this subtensor, called a level-ℓ triple.Source: §3.8 · pp. 18–19
• Because the level-ℓ partition coarsens the level-1 partition, a level-1 block XˆI lies in X_I when consecutive length-2ℓ−1 subsequences of ˆI sum to I.This containment is denoted ˆI ∈ I and XˆI ∈ X_I.Source: §3.8 · p. 19

Definitions

• Distributions have finite support, assign nonnegative mass to each element, and have total mass 1; entropy H(α) uses logarithms base 2.The section establishes these as foundational definitions for later arguments.Source: §3.9 · p. 19

Combinatorial fact

• Lemma 3.3 states a standard combinatorial fact for a distribution over [s] and a positive integer N.The supplied passage introduces the lemma and its parameters, but the displayed conclusion is incomplete.Source: §3.9 · p. 19

Product distributions

• For distributions α and β over S and S′, α × β is defined as a joint distribution over the Cartesian product S × S′.This defines the ordinary product construction for two distributions.Source: §3.9 · p. 19
• When the supports are integer sequences, α × β instead distributes over sequences formed by concatenating one sequence from each support.The concatenation operation is denoted s ◦ s′.Source: §3.9 · p. 19

Complete Split Distributions

• Complete split distributions characterize the level-1 variable blocks contained in level-ℓ variable blocks arising from leveled partitions of tensor powers of CWq.They are defined as distributions over all length 2ℓ−1 sequences from {0, 1, 2}.Source: §3.10 · p. 20

Consistency

• A level-1 index sequence is consistent with a distribution β when each length-2ℓ−1 sequence type occurs with the proportion specified by β.The sequence itself induces this distribution by counting its consecutive chunks, including after restriction to a subset S ⊆ [n].Source: §3.10 · p. 20

Tensor Grouping

• For a level-ℓ constituent tensor Ti,j,k, the framework groups level-1 X-, Y-, and Z-variable blocks whose index sequences are approximately consistent with specified distributions βX, βY, and βZ.This grouping is parameterized by an exponent N and tolerance ε, with ε = 0 yielding the exact-consistency notation.Source: §3.10 · p. 20

3.11 Salem-Spencer Sets

• The hashing step of the laser method relies on a large dense subset of ZM with no nontrivial 3-term arithmetic progressions.This subset is used to construct the hashing step.Source: §3.11 · p. 21
• Theorem 3.7 () states that for every positive integer M > 0, there exists B ⊆ ZM in which a + b ≡ 2c (mod M) holds only when a = b = c.Thus, B contains no nontrivial 3-term arithmetic progressions.Source: §3.11 · p. 21

4 Algorithm Outline

• The algorithm accepts a sufficiently large tensor power and degenerates it into independent matrix multiplication tensors of dimensions ⟨m, m^κ, m⟩, yielding an upper bound on ω(1, κ, 1).Here, κ ≥ 0 specifies the target rectangular exponent bound.Source: §4 · p. 21

4.1 Algorithm Framework

• An interface tensor connects algorithmic levels: each level maps an input interface tensor to independent copies of another interface tensor, while tensor products concatenate their parameter lists.The first level instead receives a large tensor power of CW_q.Source: §4.1 · p. 21
• The framework first applies a global stage, then recursively applies constituent stages from level ℓ* down to level 2, and finally degenerates level-1 interface tensors into matrix multiplication tensors.Each constituent stage outputs a matrix multiplication tensor together with independent lower-level interface tensors, enabling the recursion.Source: §4.1 · pp. 21–22

4.2 Algorithm Outline

• The global-stage outline splits the tensor into three regions, uses asymmetric hashing and zeroing to enforce unique level-ℓ triples, and applies compatibility and usefulness tests before fixing holes.The three regions permit sharing in different dimensions, balancing variable blocks despite the procedure’s asymmetry; the structure generalizes the split-distribution approach of [DWZ23] to complete split distributions.Source: §4.2 · pp. 22–23
• Hole fixing converts sufficiently many broken interface-tensor copies into an unbroken copy when at most a 1/(8N) fraction of blocks are holes and r ≥ 2^C1N/log N.The resulting level-1-independent interface tensors with holes are repaired using Corollary 4.2.Source: §4.2 · p. 23

5 Global Stage

• The global construction defines marginal distributions and the entropy penalty P_α as the maximum entropy increase among distributions sharing α’s three marginals.These quantities parameterize the block counts used in the asymmetric-hashing analysis.Source: §5 · p. 23
• Theorem 5.3 yields 2^o(n) independent copies of a level-ℓ_ε interface tensor, with a 2^o_{1/ε}(n) loss in the retained-copy count.The proof merges level-ℓ interface tensors whose target complete split distributions differ by at most ε in L∞ distance.Source: §5 · pp. 24–25

5.1 Dividing into Regions

• The tensor is partitioned into three regions, each hashed separately with shared Z-, Y-, or X-blocks, and their independent interface tensors are combined by tensor product.The detailed analysis is given for the first region; the other two follow symmetrically.Source: §5.1 · p. 26

5.2 Asymmetric Hashing

• Asymmetric hashing retains consistent block triples at scale N_{αX,αY,αZ} = 2^(H(α)+P_α)·A_1n ± o(n), using Salem–Spencer buckets and collision-based zero-outs.The Salem–Spencer set forces surviving triples in each bucket to share a common hash value, after which repeated zero-outs ensure X- and Y-block uniqueness.Source: §5.2 · p. 27

5.3 Compatibility Zero-Out I

• Compatibility zero-outs enforce prescribed split distributions for X- and Y-blocks and averaged distributions for Z-blocks, ensuring every surviving Z-block is compatible with its containing level-ℓ triple.Compatibility is adapted from [DWZ23] and is established for every surviving level-1 block triple.Source: §5.3 · p. 29
• Compatibility zeroing enforces the required split distributions for remaining level-1 blocks, including the Z-block constraints derived from complementary X-block distributions.For j = 0, the proof derives split(K-hat, S_i,j,k) = beta_Z,i,j,k from the corresponding X-block constraint, with the i = 0 case analogous.Source: §5.3 · p. 29

5.4 Compatibility Zero-Out II: Unique Triple

• The unique-triple zeroing step removes every level-1 Z-block compatible with multiple level-ell triples, leaving each remaining Z-block in a unique triple.Source: §5.4 · p. 30

5.5 Usefulness Zero-Out

• Usefulness zeroing removes Z-blocks that fail all required split constraints for their unique triple, leaving subtensors that are broken copies of T ∗ with holes exactly from multiply compatible blocks.The remaining subtensors are level-1-independent and can be written as a direct sum of broken copies of T ∗.Source: §5.5 · pp. 30–31

5.6 Fixing Holes

• 1/8N: with constant probability, each retained subtensor has at most this fraction of holes, yielding N_alpha · M^-1-o(1) copies of T ∗ that can be degenerated into unbroken copies.The hole bound follows from Claim 5.16, linearity of expectation, Markov’s inequality, and a union bound; Corollary 4.2 performs the degeneration.Source: §5.6 · p. 34

5.7 Summary

• The same procedure is applied to the second and third regions using asymmetric hashing, and tensoring the three regional results concludes the proof.The second region shares Y-variable blocks, while the third shares X-blocks.Source: §5.7 · p. 34

6 Constituent Stage

• Terms with it = 0, jt = 0, or kt = 0 are handled separately because they are already matrix multiplication tensors, following an idea similar to.When kt = 0, the tensor is isomorphic to an inner product tensor ⟨1, M, 1⟩ for some M ≥ 0.Source: §6 · p. 35
• Theorem 6.3 degenerates 2^o(n) copies of a level-ℓ 3ε-interface tensor into independent copies of a level-(ℓ−1) ε-interface tensor.The output parameter list preserves the constraints specified in Proposition 6.2 for positive it, jt, and kt.Source: §6 · p. 37

6.1 Dividing into Regions

• Dividing each term into three regions and zeroing incompatible level-1 blocks yields a tensor isomorphic to the corresponding region-restricted tensor.The construction retains blocks whose regional split distributions are ε-approximately consistent with the selected β(r) distributions.Source: §6.1 · pp. 38–39

6.2 Asymmetric Hashing

• Asymmetric hashing uses shared Z-block buckets and repeated zeroing to make surviving triples compatible, with expected count at least Nα · M^-1-o(1).The hashing claims are analogous to Section 5 and are attributed to and [DWZ23].Source: §6.2 · pp. 40–41

6.3 Compatibility Zero-Out I

• Compatibility zero-out I removes level-1 blocks whose split distributions fail to match the designated lower-level distributions within their unique block triples.The same rule is applied symmetrically to X- and Y-blocks, with analogous handling intended for the remaining variable family.Source: §6.3 · p. 41
• Compatibility zero-outs ensure every remaining level-1 block is compatible with its containing level-(ℓ−1) triple.This follows from the compatibility conditions imposed in the first zero-out step.Source: §6.3 · p. 42

6.4 Compatibility Zero-Out II: Unique Triple

• Zeroing out blocks compatible with multiple triples leaves each remaining level-1 Z-block compatible with a unique level-(ℓ−1) triple.Blocks compatible with more than one triple become holes.Source: §6.4 · p. 42

6.5 Usefulness Zero-Out

• Non-useful Z-blocks are removed after unique-triple filtering, leaving two hole types caused by input constraints and multi-triple compatibility.The next step analyzes and fixes both types of holes.Source: §6.5 · p. 42

6.6 Fixing Holes

• 1−1/n^2 of the relevant random level-1 blocks survive the complete split-distribution constraints in each X, Y, and Z dimension.The X-dimension bound is established directly, and the Y- and Z-dimension bounds follow by symmetry.Source: §6.6 · p. 43

6.7 Summary

• Nα · M^-1−o(1) copies of T* are obtained with hole fraction O(1/n^2), then degenerated into unbroken copies.The construction uses hashing and Corollary 4.2; the second and third regions use asymmetric hashing that shares Y-variable blocks and X-blocks, respectively.Source: §6.6 · p. 45, §6.7 · p. 46

Theorem 7.2

• A partitioned tensor satisfying Property 7.1 can be recovered from sub-polynomially many broken copies with small hole fractions in all three dimensions.Property 7.1 requires structure-preserving permutations, preservation of tensor coefficients, and uniform randomization of parts.Source: §7 · p. 47
• Theorem 7.2 states that r ≥ C0·M^(1/log log N) broken copies suffice when each copy has at most 1/(4 log M_Y), 1/(4 log M_X), and 1/(4 log M_Z) holes in X-, Y-, and Z-parts, respectively.Here M = max{M_X, M_Y, M_Z}.Source: §7 · p. 47

Proof strategy

• The proof permutes holes away from a target subtensor, consumes one broken copy for its covered terms, and recursively handles the remaining seven smaller subtensors.Lemma 7.3 supplies the hole-avoiding permutations, while the eight-way decomposition yields the recursion used to prove the bound.Source: §7 · pp. 47–49

Application to interface tensors

• An interface tensor with at most a 1/(8N) fraction of holes among level-1 X-, Y-, and Z-blocks can be recovered from a direct sum of at least 2C1N/log N broken copies.The application uses at most 3^N blocks per dimension and constructs the required permutations by randomly permuting chunks within each tensor term.Source: §7 · pp. 47, 49, 50

Optimization strategy

• The constrained optimization uses sequential quadratic programming with SNOPT, although solution quality and runtime depend on the initial point.For κ = 1, parameters from Le Gall’s analysis [LG14] provide a feasible starting point yielding the same upper bound on ω before SQP refinement.Source: §8 · pp. 51–52
• For κ ≠ 1, optimization is initialized from a nearby κ solution and proceeds sequentially across κ values.The parameters for ω(1, 1, 1) initialize ω(1, 0.95, 1), which then initializes ω(1, 0.90, 1).Source: §8 · p. 52

Lagrange multipliers

• Lagrange-multiplier constraints encode maximum-entropy distributions with fixed marginals in the optimization problem.Strict concavity of entropy guarantees that distributions satisfying the resulting conditions maximize entropy; analogous constraints are also used in Theorem 6.3.Source: §8 · pp. 52–53

Smooth the landscape

• Minimum-defined intermediate variables are replaced by linear inequality constraints, smoothing the landscape required by SQP.The transformation E = min(x, y, z) into E ≤x, E ≤y, E ≤z avoids nondifferentiable spikes, and the authors observe SQP performs poorly without it.Source: §8 · p. 53

Numerical results

• ω ≤2.371552, α ≥0.321334, and µ ≤0.527661 are obtained by solving the optimization problem for the fourth power of the CW tensor with q = 5.The bounds are computed by a MATLAB program using SNOPT.Source: §8 · p. 53