CS Paper Radar

Explicit tensors beyond the linear flattening barrier

Benjamin Lovitz

cs.DS math.AG ·submitted 2026-10-06 15:11 UTC · v1
theory

Abstract

We construct explicit n x n x n tensors of border rank at least 3n-o(n), improving the previous record of (2 + $\varepsilon$)n due to (Landsberg and Michalek 2025). We also prove that the linear flattening method cannot be used to establish lower bounds on border rank beyond 2n-1. When n is odd, we prove that this bound is achieved by Koszul flattenings. When n is even, a result of (Landsberg 2015) shows that Koszul flattenings can achieve 2n-2, leaving an open gap of size one. Our 2n-1 bound improves the best known 6n-4 linear flattening barrier due to (Garg et al. 2019) and (Buczyński 2026). Combined, these results show that our 3n-o(n) construction, as well as the construction of Landsberg and Michalek, provide explicit examples of tensors with higher border rank than any linear flattening can achieve.

Comment
19 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Disjoint and nearly disjoint sums of matrix multiplication tensors and their centroids

cs.CC math.AGmath.ACmath.RA ·2026-08-27 ·Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle
theory similarity 0.63
Abstract · 52 pages, 3 figures

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

0.46

A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$

cs.CC cs.DScs.SC ·2026-09-16 ·Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li +11 more
theorycode/data similarity 0.61
Abstract · 27 pages. Complete Lean formalization, finite certificates, source code, and reproducibility materials are available in the accompanying pub…

We prove that the tensor rank of $3\times3$ matrix multiplication over $\mathbb F_2$ is at least $21$. The structural proof, independently developed by Qiushi Engine, converts occupation constraints on a single tensor factor into algebraic relations coupling all three factors. Certified quotient-rank bounds and finite geometry force any hypothetical $20$-term decomposition to have first-factor matrix-rank profile $(16,1,3)$. The ranks of the corresponding split-flattened summands therefore sum to $27$, exactly the rank of the full split flattening. Equality in rank subadditivity forces their images to form a direct sum; normalization by the inverse flattening then makes the summands pairwise annihilating idempotents. An explicit product identity for matrix multiplication implies that at most one first factor can be invertible, contradicting the three forced by the profile. The same obstruction constrains $22$-term decompositions attaining the split-rank bound. The complete proof, including the finite quotient bounds, is formalized in Lean. The accompanying research trajectory records Qiushi Engine's long-horizon autonomous research, from numerical experiments and quotient constructions to the structural proof.

0.24

Nonnegative Rank Bounds for the Algebraic Monotone Calculus

cs.CC ·2026-10-31 ·Fedor Part
theory similarity 0.60
Abstract

In Hrubes' Algebraic Monotone Calculus a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $χ(A)-εχ(1)$ for some $ε>0$, where the coefficient of $χ(A)$ at $x^σ$ counts the terms of $A$ satisfied by $σ$, and $χ(1)=\prod_i(x_i^0+x_i^1)$. Proof size is circuit size, and $ε$ is existentially quantified, so lower bounds must hold at arbitrarily small $ε$. We prove lower bounds for bounded-depth fragments by two nonnegative rank measures of the target: monotone tensor rank and the nonnegative rank of a flattening. At depth three a proof is a nonnegative tensor decomposition. Restricting its terms to subcube indicators gives conical juntas, a system polynomially equivalent to Sherali-Adams in twin variables. For arbitrary terms we adapt Rothvoss' hyperplane separation to monotone tensor rank: Tseitin formulas on constant-degree expanders of large girth need proofs of size $2^{Ω(εn)}$ whenever $ε=ω(\log n/n)$. This cannot reach every $ε$: at shift $2^{-Θ(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every $ε\geq2^{-Ω(n)}$, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at every $ε$. Beyond depth three we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and mixed-product depth $t$: the largest number of product gates on a root-to-leaf path whose two inputs each meet both sides of the bipartition. Approximate extension complexity then bounds perfect matching and odd factor instances, and planted CSP integrality gaps give an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.

0.25

Border rank=rank for Kruskal tensors and a Kruskal's theorem for skew decompositions

cs.DS math.AG ·2026-08-21 ·Alexander Taveira Blomenhofer, Benjamin Lovitz
theory similarity 0.58
Abstract · 33 pages

We show that border rank is equal to rank for Kruskal tensors. We also give an analogous Kruskal condition for alternating tensors, which certifies uniqueness of skew rank decompositions. Furthermore, we show that border skew rank is equal to skew rank for alternating Kruskal tensors, and we give an algorithm to find the minimum skew rank decomposition of alternating Kruskal tensors.

0.49

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

cs.SC cs.CC ·2026-09-11 ·Abhinav Agarwal
theoryhot direction similarity 0.57
Abstract

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

0.25

A Lower Bound of 21 for $3\times3$ Matrix Multiplication over $\mathbb{F}_2$

cs.CC cs.DS ·2026-09-06 ·Chengu Wang
theory similarity 0.57
Abstract

We prove that $3\times3$ matrix multiplication over $\mathbb{F}_2$ has bilinear complexity at least $21$, improving the previous lower bound of $20$. Lower bounds for restrictions of the first input constrain how many first factors of a decomposition can lie in each subspace. For a hypothetical $20$-term decomposition, the strengthened restriction bounds force all first factors of matrix rank at least two into a single coset of a three-dimensional rank-one subspace. An exhaustive computation finds no admissible first-factor profile with $20$ terms. We also prove that $2\times3$ by $3\times3$ matrix multiplication over $\mathbb{F}_3$ has rank exactly $15$: three profiles with $14$ terms survive the corresponding computation up to symmetry, and short restriction arguments exclude them. We combine Wang's automated framework for tensor-rank lower bounds with D'Ambrosio's capacity-and-profile strategy. Our computational contributions are rank-one-span searches that strengthen the subspace lower-bound table and a direct, symmetry-reduced profile enumerator that enforces all subspace capacities simultaneously.

0.28

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

cs.LG stat.MLmath.COmath.ST ·2026-09-10 ·Haoming Wang, Ming Yuan
theory similarity 0.55
Abstract

Identifiability of tensor decompositions is often established through linear-algebraic conditions on the factor families. For nonnegative decompositions, however, positivity provides additional information that is not captured by dimension and independence alone: nonnegative terms cannot cancel, and their supports constrain competing decompositions. We introduce a positive scattering term that quantifies this additional source of identifiability and combine it with the dimension budget underlying the Lovitz--Petrov generalization of Kruskal's theorem. For every subset of components, we obtain two sufficient conditions: a threshold of $2|S|-2$ guarantees minimality and nonnegative rank, while the stronger threshold $2|S|-1$ guarantees uniqueness among nonnegative decompositions of the same length. The key result is a positive splitting inequality for irreducible exchanges of nonnegative rank-one tensors, which combines the dimension constraint with support-induced geometric rigidity. Although the scattering term is defined through an optimization over intermediate factor spaces, we show that its mode costs are exactly $0$, $1$, or $+\infty$, yielding an exact activation characterization in terms of graph connectivity. The resulting criterion can strictly certify sparse nonnegative tensor decompositions beyond the reach of Kruskal and Lovitz--Petrov conditions, including examples for which those conditions fail even after reshaping. In the matrix case, the two criteria reduce respectively to full-rank factorization and two-sided separability.

0.36

Polynomial Separation of a Shared Tensor Leg and Matrix Multiplication in Arbitrary Characteristic

cs.CC ·2026-10-12 ·Houxi Lü
theory similarity 0.54
Abstract

We improve the shared-leg separation construction in Proposition 3.1 of OpenAI, *An Upper Bound of $9/4$ for the Matrix Multiplication Exponent* (October 2, 2026). If $M$ tensor blocks have a common first space and independent matched sectors on their other two spaces, then $M+n-1$ copies of their matched sum degenerate to the full direct sum of the blocks, each tensored with an $n$-dimensional dot product. For $n=M$, this reduces the number of source copies from $5M$ to $2M-1$. The construction uses polynomial interpolation and truncated local substitution, with no roots of unity or factorial denominators. It works over every field containing enough distinct elements. We verify that the remaining spectral and discrete-growth arguments of the cited preprint are independent of characteristic. Over an algebraic closure, the replacement therefore gives $ω\leq9/4$ in every characteristic.

0.46