Faster Matrix Multiplication via Asymmetric Hashing

1 Introduction

• Fast matrix multiplication has unknown exponent ω, with 2 ≤ ω ≤ 3, and its exact value affects matrix operations and algorithms for several combinatorial problems.Examples include LUP decomposition, matrix inversion, determinant, transitive closure, all-pair shortest paths, context-free grammar parsing, and RNA folding.Source: §1 · p. 2
• Prior work progressed from Strassen’s ω ≤ log2 7 < 2.8074 [Str69] through analyses of higher Coppersmith-Winograd powers, reaching ω < 2.3728596 with Alman and Vassilevska Williams’ refined laser method [AW21b].Coppersmith and Winograd obtained ω < 2.38719 and ω < 2.375477 for the original and second-power analyses, while later work analyzed fourth, eighth, and 32nd powers.Source: §1 · p. 2
• The laser method raises an efficiently computable tensor to a power, zeroes variables, and degenerates it into independent matrix multiplication tensors.Recent improvements apply this framework to Coppersmith-Winograd tensors CWq [CW90].Source: §1 · p. 2
• Using asymmetric hashing to compensate for combination loss, the paper improves the second-power analysis to ω < 2.374631 and generalizes it to higher powers, obtaining ω < 2.371866.Source: §1 · p. 2
• The main contribution is identifying combination loss across adjacent recursion levels and compensating for it with asymmetric hashing.This use of asymmetric hashing differs from its prior purposes in analyzing asymmetric or rectangular matrix multiplication tensors.Source: §1 · p. 2
• The eighth-power result ω < 2.371866 breaks the ω < 2.3725 limitation proved for previous lower-power approaches by Ambainis, Filmus and Le Gall.Their separate 2.3078 barrier for a wider class of algorithms still includes this approach, as do other general barriers.Source: §1 · p. 3

1.1 Organization of this Paper

• The paper is organized around laser-method background, asymmetric hashing and notation, second- and higher-power analyses, and an optimization program with numerical results.These topics are covered in Sections 2–8, respectively.Source: §1.1 · p. 3

2.1 Coppersmith-Winograd Algorithm

• The paper opens the black box of Coppersmith-Winograd subtensors [CW90], revealing internal structure that makes the combination loss visible.The overview differs from the original black-box treatment by examining subtensor structure directly.Source: §2.1 · p. 3
• In the second-power decomposition, most level-2 subtensors are matrix multiplication tensors, but T1,1,2 and its permutations are not.This distinction drives the two-level analysis: suitable powers are partitioned into blocks, then nonsuitable components are further decomposed and zeroed.Source: §2.1 · p. 4
• The laser method raises tensor powers and zeroes variables so remaining matrix multiplication tensors become independent, enabling Schönhage’s τ theorem.A single-level analysis gives ω < 2.38719, while the second-power analysis gives ω < 2.375477 [CW90].Source: §2.1 · p. 5
• Merging split subtensors avoids wasting terms: components already representing matrix multiplication can be split and recombined without worsening their asymptotic size.For T0,2,2, choosing λ = 1/(2+q^2) recovers a matrix multiplication tensor of size (q^2 + 2)^m(1−o(1)).Source: §2.1 · pp. 7–8

2.2 Combination Loss

• The key insight is that the preceding analysis is wasteful because successive level-2 and level-1 zeroing-outs discard structure while enforcing block distributions and independence.Level-2 zeroing retains blocks obeying α and then applies hashing with a Salem-Spencer set; level-1 tracks split distributions for the component positions.Source: §2.2 · p. 8
• The combination loss |Z′|/|ZM| is exponentially large because λ and µ differ by a constant when ω > 2, motivating compensation.The loss arises because the even split distribution has higher entropy than the constrained distribution used by ZM.Source: §2.2 · pp. 9–10

2.3 Compensate for Combination Loss

• Asymmetric hashing sets αX = αY and αZ so each Z-block can match 2^Θ(n) X,Y-block pairs while X- and Y-block matchings remain unique.This produces mostly disjoint subtensors, while unique X- and Y-block assignments enable removal of interfering terms.Source: §2.3 · pp. 10–11
• The compensation method resolves disjointness and independence challenges by randomly gluing permuted broken tensors to fix holes and using compatibility tests to eliminate interfering terms.A level-1 Z-block is typically compatible with only one X,Y pair; incompatible or multiply compatible blocks are zeroed out and repaired as holes.Source: §2.3 · pp. 12–13

2.4 Beyond the Second Power

• For higher CW powers, the method analyzes global and component values, fixes holes before converting tensors to matrix multiplication tensors, and generalizes compatibility constraints to components with i = 0 or j = 0.Parameters are optimized computationally, while random hole-shifting and gluing recover a hole-free tensor when the target structure has suitable symmetry.Source: §2.4 · p. 13
• Higher-power analysis hashes triples so X- and Y-blocks are disjoint, permits shared Z-blocks, then zeroes incompatible Z-blocks before independent degeneration.The procedure also fixes holes and applies additional technical zeroing steps before forming the desired lower bound.Source: §2.4 · p. 14
• Component evaluation restores the required NBX = NBY > NBZ condition by choosing three different hashing numbers, making Z asymmetric from X and Y.This enables lower bounds for high-level components despite the original symmetry NBX = NBY = NBZ.Source: §2.4 · p. 14
• ω < 2.37187 from the eighth power of the CW tensor breaks the 2.3725 lower bound for previous higher-power and refined-laser algorithms [AFLG15, AW21b].The improvement comes from compensating for combination loss at each level.Source: §2.4 · p. 14
• Using the same variable block multiple times from level 2 improves the values of several level-3 subtensors beyond the estimates used in the 2.3725 lower bound.The affected subtensors include T1,2,5, T1,3,4, T2,2,4, and T2,3,3; their improved values break that lower bound.Source: §2.4 · pp. 14–15
• The method remains subject to the 2.3078 lower bound for algorithms that zero level-1 variable blocks and merge non-independent matrix multiplications.Thus, breaking 2.3725 does not remove the broader limitation on this algorithmic class.Source: §2.4 · p. 15

3 Preliminaries

• The preliminary notation also fixes log x as log_2 x by default, defines [n] = {1, . . . , n}, disjoint unions, and indicator functions 1[P].These conventions support subsequent tensor definitions and arguments.Source: §3 · p. 15

3.1 Tensors, Operations, and Ranks

• Tensors are formal sums of x_i y_j z_k monomials over three variable sets and a field, with the matrix multiplication tensor ⟨n, m, p⟩ as a central example.The paper’s tensor notation largely follows [AW21b].Source: §3.1 · p. 15, §3 · p. 15
• Tensor isomorphism permits variable renamings through bijections across the three variable sets, while self-isomorphisms form the automorphism group Aut(T).Equivalent tensors are denoted T ≅ T′.Source: §3.1 · pp. 15–16
• The basic tensor operations are direct sum, tensor product, and compatible summation, with T^⊕n and T^⊗n denoting repeated direct sums and tensor products.Direct sums use disjoint variable sets, whereas tensor products use Cartesian-product variable sets.Source: §3.1 · p. 16
• Rotation and swapping permute tensor dimensions, enabling 3-symmetrization and 6-symmetrization so that tensor variables become symmetric.The definitions are sym3(T) = T ⊗ T^rot ⊗ T^rot rot and sym6(T) = sym3(T) ⊗ sym3(T)^swap.Source: §3.1 · pp. 16–17
• Tensor rank is the minimum number of rank-one terms in a decomposition, while asymptotic rank captures the corresponding growth under tensor powers.The rank decomposition is the equation defining rank R(T).Source: §3.1 · p. 17
• Schönhage’s τ theorem [Sch81] applies to direct sums of matrix multiplication tensors and states that, under its τ-condition, ω ≤ 3τ.The theorem assumes τ ∈ [2/3, 1] and positive dimensions n_i, m_i, p_i.Source: §3.1 · p. 17

Restrictions

• Restrictions map each tensor variable to a linear combination of variables in the target tensor, preserving non-increasing rank and border rank.Source: §3.2 · p. 17

Degenerations

• Degenerations use polynomial mappings in a formal variable λ; restrictions are special degenerations, and border rank does not increase.Source: §3.2 · p. 18

Zeroing out

• Zeroing out restricts a tensor by setting variables outside selected subsets X′, Y′, and Z′ to zero, producing a subtensor.Although sufficient in previous work, zeroing out is supplemented here by another degeneration for technical reasons.Source: §3.2 · p. 18

Identifications

• Identifications degenerate direct sums of tensors on disjoint copies into their sum over shared variable sets, and extend similarly to m tensors.Source: §3.2 · p. 18

Values

• The 3- and 6-symmetrized τ-values quantify asymptotic matrix-multiplication capability, with 6-symmetrized values needed here for technical reasons.Their super-multiplicative and super-additive properties bound complex tensors from the values of their ingredients.Source: §3.2 · pp. 18–19

3.3 Partitions of a Tensor

• A tensor partition divides X, Y, and Z into disjoint subsets and decomposes T into component subtensors T_i,j,k over corresponding subset triples.Each variable inherits the index of its subset, and each T_i,j,k is a component of the partitioned tensor.Source: §3.3 · p. 19
• P-partitioned tensors require T_i,j,k = 0 unless i + j + k = P, a structure heavily used because it enables the laser method.Most partitioned tensors considered in the paper are P-partitioned.Source: §3.3 · p. 19
• For T = T_base^⊗n, a base partition induces X-, Y-, and Z-blocks indexed by length-n sequences, which partition the tensor-power variables.A block is formed by taking the Cartesian product of the corresponding base-partition subsets across all n tensor factors.Source: §3.3 · p. 19
• The tensor power is partitioned into subtensors T_I,J,K restricted to block triples, and each variable’s index sequence is inherited from its block.This extends the component and index definitions from the base tensor to tensor-power blocks.Source: §3.3 · p. 19

3.4 Coppersmith-Winograd Tensor

• The Coppersmith-Winograd tensor CW_q uses three-way partitions with X_0 = {x_0}, X_1 = {x_1, ..., x_q}, and X_2 = {x_q+1}, with analogous partitions for Y and Z.Under these partitions, CW_q consists of six nonzero components: T_1,1,0, T_1,0,1, T_0,1,1, T_0,0,2, T_0,2,0, and T_2,0,0.Source: §3.4 · p. 20
• CW_q is 2-partitioned because every nonzero component satisfies i + j + k = 2, enabling the laser method; its asymptotic rank is eR(CW_q) = q + 2 [CW90].The rank property benefits application of Theorem 3.2.Source: §3.4 · p. 20
• For T = CW_q^⊗N, the induced level-1 partition has T_I,J,K nonzero only when I + J + K = (2, 2, ..., 2).The corresponding blocks and index sequences follow the general tensor-power partition construction.Source: §3.4 · p. 20

• Prior analyses apply the laser method recursively to tensor powers CW_q^(2^ℓ), rather than directly to CW_q.Source: §3.5 · p. 20
• Fixing the same N across levels makes each level a partition of the same tensor T = CW_q^N at a different granularity.At level ℓ, N is taken as a multiple of 2^(ℓ−1), with n = N/2^(ℓ−1).Source: §3.5 · pp. 20–21

Level-1 partition

• The level-1 partition groups tensor components indexed by I, J, K ∈ {0,1,2}^N satisfying I + J + K = (2, …, 2).Source: §3.5 · p. 21

Level-ℓ partition

• At level ℓ, variables are grouped by the sums of 2^(ℓ−1) base indices, yielding components T_i,j,k that are nonzero only when i + j + k = 2^ℓ.The induced level-ℓ blocks form triples whose coordinate sequences satisfy I_t + J_t + K_t = 2^ℓ for every t.Source: §3.5 · p. 21

Level-ℓ index sequences

• Each level-ℓ index sequence is formed by adding consecutive pairs from level-(ℓ−1), so every finer block has one parent while each coarser block contains several finer blocks.Source: §3.5 · pp. 21–22

3.6 Distributions and Entropy

• The analysis uses discrete distributions over finite supports that are normalized and non-negative, with entropy defined in the standard way.Source: §3.6 · p. 22

3.7 Distributions of Index Sequences

• The laser method chooses a distribution over all components of T = CW^(⊗(2ℓ−1)) when applied to a tensor power.Source: §3.7 · pp. 22–23
• A level-ℓ joint component distribution assigns frequencies to components T_i,j,k with i + j + k = 2ℓ, and consistency requires matching those frequencies across index positions.Source: §3.7 · p. 23
• Marginal distributions αX, αY, and αZ record the corresponding frequencies of individual X-, Y-, and Z-index values and are induced by the joint distribution.Source: §3.7 · p. 23
• In level 1, given marginals uniquely determine the joint distribution when it exists, whereas higher-level marginals generally do not.Source: §3.7 · p. 23
• The set Dα collects joint distributions sharing α’s marginals, while D*(αX, αY, αZ) selects those with maximum entropy.Source: §3.7 · p. 23
• A level-ℓ split distribution describes how each component T_i,j,k divides into paired level-(ℓ−1) components, with its marginals tracking the resulting lower-level index frequencies.Source: §3.7 · pp. 23–24
• This higher-level non-uniqueness causes a loss in moduli, which the refined laser method [AW21b] can reduce.Source: §3.7 · p. 23

3.8 Salem-Spencer Set

• The Salem-Spencer set is needed, as in previous works, to construct independent matrix products.Source: §3.8 · p. 24
• A Salem-Spencer set A ⊂ {0, ..., M −1} has no nontrivial three-term arithmetic progression modulo M and satisfies |A| > M1−o(1) for every positive integer M [SS42, Beh46].If a, b, c ∈ A satisfy a + c ≡ 2b (mod M), then a = b = c.Source: §3.8 · p. 24

Definition

• Restricted-splitting tensor power is a new concept that captures a component subtensor under a specified split distribution on variable blocks.The construction zeroes out level-(ℓ−1) variable blocks that do not match the prescribed split distribution.Source: §3.9 · p. 24
• The framework can restrict the split distribution of the X, Y, or Z dimension, with Z used by default when unspecified.The section also defines restricted-splitting values and 3-symmetrized restricted-splitting values for these distributions.Source: §3.9 · pp. 24–25
• Restricted-splitting values provide the recursive interface between level-ℓ components and their level-(ℓ−1) components, paralleling the role of ordinary values.Prior analyses used ordinary values to connect adjacent levels; this paper introduces restricted-splitting values for the same purpose.Source: §3.9 · p. 25
• In restricted-splitting analysis, the prescribed restriction eα_i,j,k is fixed in advance, while component and splitting distributions remain variables selected to optimize the lower bound.This distinguishes eα_i,j,k from α and α(i,j,k), which are treated as optimization variables.Source: §3.9 · p. 25

Asymmetric Hashing

• Asymmetric hashing retains triples with distinct X- and Y-blocks while allowing shared Z-blocks, using Salem-Spencer buckets and collision removal by zeroing X- or Y-blocks.Hashing retains a triple only when all three blocks map to the same bucket in the Salem-Spencer set; subsequent greedy deletion eliminates X/Y collisions without zeroing Z-blocks.Source: §3.10 · pp. 25–27

Hash Loss

• The expected asymmetric output is at least NBX Nα/NαX,αY,αZ · 2−o(n) good triples when NαX,αY,αZ/NBX·M−1 ≤ 1/4, while R = Nα/NαX,αY,αZ measures hash loss.If R = 2−o(n), almost all X-blocks can survive; otherwise a 1−R fraction is wasted. Lemma 3.12 shows NαX,αY,αZ = poly(n) · maxα′∈Dα Nα′, so maximizing Nα avoids non-negligible hash loss.Source: §3.10 · pp. 27–28

Symmetric Hashing

• Symmetric hashing also removes triples sharing Z-blocks, applies only when NBX = NBY = NBZ, and retains NBX Nα/NαX,αY,αZ · 2−o(n) good triples with M = Θ(NαX,αY,αZ/Nα).Unlike asymmetric hashing, the greedy collision-resolution process zeroes some of all five involved blocks when a Z-block is shared.Source: §3.10 · p. 28

More general settings

• In the generalized setting, hashing applies to products or subtensors of a constant number of P-partitioned tensor powers when the required block-count and regularity conditions hold, yielding NBX Nα/NαX,αY,αZ · 2−o(n) independent good triples.The regions have a common partition size P, prescribed joint distributions and marginals, balanced block counts, and uniform triple incidences; n = n1 + ··· + ns.Source: §3.10 · p. 28

4 Improving the Second Power of CW Tensor

• ω < 2.375234 is obtained by analyzing the second power of the CW tensor, improving the previous ω < 2.375477 bound in [CW90].Because the second-power optimization can be solved exactly by hand, the improvement comes from new ideas rather than optimization heuristics.Source: §4 · p. 29

4.1 Coppersmith-Winograd Algorithm

• The CW framework lower-bounds component values, selects a symmetric distribution, hashes to independent triples, degenerates them into matrix multiplications, and applies Schönhage’s τ theorem.For the second power, symmetric hashing retains triples consistent with marginal distributions, while the original analysis achieves ω < 2.375477 with q = 6 and specified parameters [CW90].Source: §4.1 · pp. 30, 32

4.2 Non-rotational Values

• Non-rotational values omit symmetrization before degeneration, enabling asymmetric distributions required by the improved hashing method.For matrix multiplication components T0,j,k, non-rotational and symmetrized values match; T1,1,2 instead receives a lower bound on its symmetrized restricted-splitting value.Source: §4.2 · p. 32

4.3 Compatibility

• Compatibility identifies which level-1 blocks inside a level-2 triple contribute, and the probability pcomp quantifies the resulting combination loss.Only compatible blocks survive usefully; the remaining 1 − pcomp fraction is wasted when a level-2 block participates in one hashed triple.Source: §4.3 · pp. 33–34

4.4 Variant of the Coppersmith-Winograd Algorithm

• A modified CW algorithm uses restricted-splitting values, non-rotational values for asymmetric components, and an additional zeroing step that keeps only compatible blocks.Symmetry remains required for T1,1,2, the only component without a non-rotational value bound; other components may use asymmetric distributions.Source: §4.4 · p. 35
• The earlier variant’s values match the original analysis and expose combination loss: only level-1 blocks with a specific splitting distribution participate, while the rest are wasted.This observation motivates the asymmetric improvement.Source: §4.4 · p. 36

4.5 Our Improved Algorithm

• Asymmetric hashing compensates for combination loss by placing each X- or Y-block in one remaining triple while allowing each Z-block to appear in multiple triples.Additional zeroing-out steps restore triple independence, and random shuffling fixes the resulting Z-variable holes using a technique similar to [KK19].Source: §4.5 · p. 36
• The improved construction proves that incompatible level-1 blocks are eliminated and that each remaining triple initially retains a tensor isomorphic to T*.After further zeroing, triples become broken matrix multiplication tensors; because the hole probability is less than 1/2, the Matrix Hole Lemma fixes them with only an O(n) loss in tensor count.Source: §4.5 · pp. 38–40

4.6 Analysis

• The analysis introduces N_BX, N_BY, N_BZ, N_α, N_αX,αY,αZ, p_comp, and N_ret to quantify blocks, compatible triples, consistency, and retention after asymmetric hashing.These quantities support the subsequent calculation of the bound on ω.Source: §4.6 · p. 41
• Asymmetric hashing retains an expected NBX · Nα / NαX,αY,αZ · 2^-o(n) triples, but the hash loss arises when NαX,αY,αZ > Nα.The method chooses the hash modulus so each level-2 Z-block matches at most 1/pcomp level-2 X/Y-blocks on average.Source: §4.6 · p. 41
• The improvement comes from new theoretical ideas rather than better numerical optimization, since the optimal second-power parameters under the prior approach are easy to derive and prove optimal.The best bound from analyzing the second power had remained unchanged since [CW90].Source: §4.6 · p. 45
• ω < 2.375234 follows from asymmetric hashing with parameters a = 0.102787, b = 0.102058, c = 0.205540, d = 0.000232, and e ≈ 0.0125086667.The hash loss is N ≈ 1 − 2.49 × 10^-7, indicating a very small loss.Source: §4.6 · p. 45

4.7 Proof of Matrix Hole Lemma.

• The matrix hole lemma degenerates a direct sum of broken matrix multiplication tensors into an unbroken one.A probabilistic permutation argument makes every matrix position good, after which variables are identified and holes are zeroed out without duplicated terms.Source: §4.7 · pp. 45–46
• ω < 2.374631 is achieved for the second power by modifying restricted-splitting distributions so Z-blocks can be shared by more triples.The parameters and method are developed for later generalization to higher powers.Source: §4.7 · p. 47

5 Hole Lemma

• The generalization is needed because symmetrizing a tensor can create holes in X, Y, and Z variables, preventing direct application of the earlier lemma that handles only Z-variable holes.The new lemma instead fixes the tensor before symmetrization by permuting lower-level blocks, for tensors with the required symmetry.Source: §5 · p. 47

5.1 Standard Form Tensor

• Standard form tensors organize level-ℓ components and split distributions into small X, Y, and Z blocks, with only Z-blocks satisfying the split restrictions considered available.All Z-variables are the union of available small Z-blocks, while holes are created by zeroing out some of them.Source: §5.1 · pp. 47–48
• A broken standard form tensor is formed by zeroing out selected available small Z-blocks of a standard form tensor; these are holes, and the remaining blocks are non-holes.The fraction of holes and fraction of non-holes measure the proportions among all available small Z-blocks.Source: §5.1 · p. 48

5.2 Fixing the Holes

• When the sum of non-hole fractions satisfies Ση_t ≥ N^ℓ + 1, broken standard form tensors can be degenerated into one complete copy of T*; larger sums yield multiple copies.The multi-copy corollary partitions tensors into groups whose non-hole fractions lie between N^ℓ + 1 and N^ℓ + 2, then applies the Hole Lemma to each group.Source: §5.2 · pp. 48, 50, 51
• The proof randomly shuffles lower-level blocks using automorphisms that preserve block availability and tensor structure, making each available Z-block equally likely to be a hole.Independent shufflings ensure every available block is non-hole in at least one copy; zeroing duplicated appearances and identifying the copies reconstructs T*.Source: §5.2 · pp. 48–50

6 Improving High-Power Global Values

• The algorithm optimizes a probability distribution α over level-ℓ components, using their Z-split distributions and restricted-splitting value bounds as inputs to lower-bound the global tensor value.Its output is a lower bound on V^(6)_τ(T), with T defined from a high power of the CW tensor.Source: §6 · p. 51

6.1 Algorithm Description

• Asymmetric hashing retains large block triples consistent with α, with distinct retained X- and Y-blocks, so retained triples can share only Z-blocks.The hashing modulus is a prime M in [M0, 2M0], and any resulting hash loss for non-maximum-entropy α is accounted for in the analysis.Source: §6.1 · p. 52
• Compatibility-based zeroing enforces prescribed split distributions on small blocks, ensuring that any surviving small Z-block can form a triple only with a compatible large triple.A second zeroing step yields broken copies of a structured tensor; the hole lemma fixes Z-variable holes before independent degeneration and symmetrization.Source: §6.1 · pp. 52–53

6.2 Analysis

• The analysis characterizes typical small Z-blocks by split frequencies and defines pcomp as their compatibility probability with a uniformly random matchable X-block and corresponding triple.Typicalness is equivalent to avoiding the first additional zeroing step, while compatibility imposes the prescribed split conditions on boundary components and jointly positive components.Source: §6.2 · pp. 55–56
• Each useful small block is a hole with probability at most 1/8, enabling a lower bound on the number of standard-form tensors obtainable by degeneration.The bound applies to a retained triple consistent with α, and the resulting broken tensors can degenerate to copies of T*.Source: §6.2 · pp. 57–58
• Given α and component-level lower bounds, Algorithm 2 verifies the global-value lower bound by computing closed forms, solving a convex optimization problem, and applying the resulting formula.The optimization parameters are later tuned using heuristics described in Section 8.Source: §6.2 · p. 59

6.3 Example – Level-2 Global Value

• ω < 2.374631 improves the Section 4 bound by breaking symmetry among selected component distributions and using different restricted-splitting values.The parameters are found numerically by MATLAB; Table 2 specifies the parameters for this bound.Source: §6.3 · pp. 59–60, Table 2 · p. 60

7 Improving Component Values

• The new approach analyzes an asymmetric tensor T instead of sym3(T^⊗n), matching each Z-block with multiple X/Y-block pairs while preserving X/Y symmetry.The construction introduces A1, A2, A3 ∈ [0,1] with A1 + A2 + A3 = 1, reflecting asymmetry between X/Y and Z variables while keeping X and Y matched one-to-one.Source: §7 · p. 61
• Restricted split distributions are necessary because unrestricted laser analysis would not guarantee a degeneration sym6(T_i,j,k[eαZ]) ⊵ T_final.The method therefore imposes three potentially different Z-marginal split distributions and optimizes joint distributions whose Z-marginals match them, ultimately outputting a lower bound on V^(6)_τ(T_i,j,k, eαZ).Source: §7 · pp. 61–63

7.1 Algorithm Description

• The algorithm chooses distributions for three cyclic component orderings, applies asymmetric hashing across six regions, and retains large triples consistent with all regional split distributions.The last three distributions are obtained by swapping X and Y in the first three; non-maximum-entropy joint distributions incur hash loss accounted for later.Source: §7.1 · pp. 63–64
• Compatibility-based zeroing removes small blocks whose split patterns do not match the retained large triples, ensuring surviving small triples can participate only when compatibility conditions hold.A second zeroing step further keeps only useful small Z-blocks satisfying the prescribed component- and region-level split distributions.Source: §7.1 · pp. 65–66
• The algorithm zeroes out blocks that support multiple triples or are useless for their unique compatible triple, then fixes holes and independently degenerates each retained triple.After zeroing, each retained restriction is a broken copy of the standard-form tensor T ∗, whose non-hole fraction is ηI,J,K.Source: §7.1 · pp. 66–67

7.2 Analysis

• ηI,J,K ≥ 2−o(n) because at least 2−o(n) of useful blocks are typical and each typical block has constant probability of avoiding holes.Claim 7.13 bounds the hole probability for each typical useful block by at most 1/8, yielding the stated non-hole fraction for every retained triple.Source: §7.2 · pp. 68, 71

7.3 Value from Merging When {i, j, k} Contains Zero

• For components T_i,j,k with an index equal to zero, the lower bound is verified by computing closed-form quantities and solving a convex optimization problem for each region.The procedure takes α(r), A_r, and restricted-splitting distributions as inputs, then calculates the lower bound of V (6).Source: §7.3 · p. 73
• The restricted-splitting value is exactly V (6).Source: §7.3 · p. 73
• When i = 0, normal values for the two level-ℓ components provide the lower bound, with j = 0 handled similarly.The components are (0, j′, k′) and (0, j − j′, k − k′), using Lemma 7.14.Source: §7.3 · p. 73
• When k = 0, the restricted-splitting value equals the unrestricted value and is computed precisely by Lemma 7.14.Source: §7.3 · p. 73

8 Heuristics and Numerical results

• The framework propagates restricted-splitting value pairs across levels to produce a global value that can imply an upper bound on ω.It uses asymmetric hashing for higher-level components without zeros, merging when a component includes zero, and symmetric hashing at level 2.Source: §8 · pp. 73–74

8.1 Alternating Optimization

• Alternating optimization updates component and global parameters sequentially, using a soft-min surrogate to preserve information lost by min-operation gradients.The method initializes feasible parameters by maximizing each component value and iterates from lower to higher levels.Source: §8.1 · pp. 75–76

8.2 Heuristics within a Component

• Within each component, the method alternates between split weights and distributions, solving the weight step precisely and approximating the distribution step as a concave optimization.The approximation fixes complicated quantities at their previous values, enabling convex optimization tools.Source: §8.2 · pp. 77–78

8.3 Numerical Results

• Analyzing the eighth tensor power of the Coppersmith-Winograd tensor, the authors obtain ω ≤2.371866 by Theorem 3.2 and verify the result with a standalone program.The program recursively verifies the bounds of restricted-splitting values.Source: §8.3 · p. 78
• The program retains multiple value pairs per component so later levels can choose among different pairs, making higher-power analysis slower and stopping at the eighth power.The asymmetric-hashing analysis also improves results for the second and fourth tensor powers, as shown in Table 3.Source: §8.3 · p. 78

Lemma 4.6

• For component (0,2,2), restricting to a split distribution and maximizing the resulting matrix multiplication tensor at b′′ = 1/(2+q^2) proves the non-rotational restricted-splitting bound.The tensor is isomorphic to a matrix multiplication tensor using all remaining Z-variables.Source: A Missing Proofs from Section 4 · p. 83
• The component (1,1,2) analysis uses 3-symmetrization and symmetric hashing to obtain the lower bound 2^(2/3)q^τ(q^(3τ)+2)^(1/3), implying Lemma 4.6(d).The bound is optimized at b′ = 1/(2+q^(3τ)), as in [CW90].Source: A Missing Proofs from Section 4 · pp. 83–84

Lemma 4.10

• Lemma 4.10 follows because the split distributions induced by components (2,0,2), (0,2,2), and (1,1,2) force every remaining Z-block compatible with X and Y.The argument is by contradiction and assumes α(1,1,2) > 0; otherwise the lemma is trivial.Source: A Missing Proofs from Section 4 · p. 84

Lemma 4.12

• Lemma 4.12 shows that the degeneration from lower bound (14) is a zeroing out producing matrix multiplication tensors of equal size.It combines the zeroing-out degenerations of the factors from Lemma 4.6, and tensor products preserve both properties.Source: A Missing Proofs from Section 4 · p. 84

B Heuristics for Section 4

• The approximated program removes a near-one objective ratio and replaces the feasibility constraint with a minimum in the objective.The constraint modification is also valid for lower bounds, although this section omits the more complicated proof.Source: B Heuristics for Section 4 · p. 85
• Replacing αP with a fixed reference value α∗P makes the objective logarithmic concave and enables convex optimization tools.The original αP is a complicated function of a, b, c, d, e.Source: B Heuristics for Section 4 · p. 85
• Starting from α(0), the method repeatedly solves the approximated program with the current reference value and uses the resulting α(t) for the next iteration.In practice, tmax ≤5 is sufficient.Source: B Heuristics for Section 4 · p. 85
• A slight manual perturbation of the final solution enforces αBX ≤ αBZ/αP with little loss because αBX ≈ αBZ/αP before perturbation.Algorithm 1 is then run on the perturbed solution to obtain the final bound.Source: B Heuristics for Section 4 · p. 85

Lemma 7.10

• Lemma 7.10 concerns triples (X_I, Y_J, Z_K) consistent with α(r) across all regions r.The proof fixes a level-ℓ triple and partitions occurrences into left and right parts of level-(ℓ+1) components.Source: C Mising Proofs from Section 7 · p. 85

Strong usefulness

• Strong usefulness is defined through marginal split distributions, and its strongly useful blocks form B_strong(X_I, Y_J, Z_K).Strong usefulness provides a sufficient condition for usefulness and is connected to typicalness.Source: C Mising Proofs from Section 7 · p. 86

Counting strongly useful blocks

• The proof counts B_strong by imposing split constraints matching e_α for every region and level-ℓ component, using disjoint position sets.Each constraint contributes 2^{|S|·H(e_α)+o(n)} possible Z-index splits, and multiplying these counts gives the total.Source: C Mising Proofs from Section 7 · p. 86

Typical and strongly useful blocks

• Matching the required four-index frequencies to e_α(r) simultaneously guarantees typicalness and strong usefulness, yielding a lower bound on their intersection.The constraints are counted independently across regions and components because they apply to disjoint position sets.Source: C Mising Proofs from Section 7 · pp. 86–87

Conclusion

• Equations (41) and (42) follow from the counting arguments, with Eq. (41) holding up to a negligible factor 2^o(n).A similar transformation and count proves Eq. (42), and combining both equations completes Lemma 7.10.Source: C Mising Proofs from Section 7 · p. 87