REVIEW 3 major objections 5 minor 11 references
Depth-first search for tensor rank and border rank over finite fields
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper gives exponential-time algorithms that determine whether a tensor over a finite field has rank at most $R$, and the same for border rank over $\mathbb{F}[x]/(x^H)$, with guaranteed correctness and polynomial space.
desk verdict Exact-rank algorithm is solid and new; border-rank half has a load-bearing proof gap in the row-reduction subroutine. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Axis-reduction is the load-bearing mechanism. For each axis $d$, the mode-$d$ unfolding of the tensor is put into reduced row echelon form and only the pivot rows are kept, producing a tensor whose dimensions are the axis ranks $r_d$; because a change of basis cannot alter rank, this preserves whether a rank-$R$ decomposition exists and maps decompositions back and forth. The exact algorithm then enumerates the last $R-n_*$ columns of every factor matrix, and for each residual tensor $\tilde T$ finds a basis of row vectors $v$ with $\operatorname{rank}(v\times_0 \tilde T)\le 1$, a condition that Lemma 1 reduces to a polynomial-time check. For border rank, the echelon reduction is replaced by a pivoting procedure over $\mathbb{F}[x]/(x^H)$ whose pivots are powers of $x$, and the rank bound for the block-diagonal normal form controls the recursion's branching factor.
What would settle it
Run the paper's border axis-reduction on every $2\times 2$ matrix over $\mathbb{F}_2[x]/(x^2)$ and compare the number of rows it returns with the true matrix rank computed by exhaustive search; a single mismatch would refute the border algorithm's correctness.
Extended reading notes
Core claim
The central claim is that tensor rank over a finite field is decided by fixing all but the first $n_*$ columns of a candidate rank-$R$ decomposition and solving a residual problem whose only remaining freedom is a row basis. After axis-reduction, any rank-$R$ decomposition forces the first factor matrix to have full row rank, so its reduced row echelon form is $[I_{n_*}\mid X]$. The residual tensor after subtracting the last $R-n_*$ columns must then admit a basis of rows $v$ for which $v\times_0 \tilde T$ has rank at most 1, and Lemma 1 makes this condition checkable in polynomial time; enumerating the residuals costs exactly the stated $|\mathbb{F}|^{(R-n_*)(\sum_d n_d)+n_*}$. For border rank, the same recursion is applied over $\mathbb{F}[x]/(x^H)$ with a generalized echelon reduction whose pivots are powers of $x$; Lemmas 3 and 4 prove that the resulting block-diagonal form has rank equal to its number of nonzero blocks, giving the factor $H$ in the exponent.
Load-bearing premise
The border-rank algorithm depends on the correctness of the sketched row-reduction over $\mathbb{F}[x]/(x^H)$; if that procedure ever returns a factorization with more rows than the true matrix rank, the border algorithm's correctness and time bound fail.
Editorial extensions
If this is right
- For any tensor over a finite field, the algorithm finds a rank-$\le R$ decomposition or proves none exists within the stated exponential bound.
- The border-rank algorithm extends the same guarantee to $\mathbb{F}[x]/(x^H)$, covering the border decompositions that underlie fast matrix multiplication constructions.
- After axis-reduction, every dimension is at most $R$, so the enumeration cost depends on the tensor's axis ranks rather than its original large dimensions.
- Because both algorithms run in polynomial space, they can be executed for small fields and small rank thresholds where brute force or heuristic search is currently the only alternative.
Reading between the lines
- The border-rank bound is only as solid as the sketched row-reduction over $\mathbb{F}[x]/(x^H)$; a formal correctness proof for that reduction is needed before the border complexity can be regarded as fully established.
- The exact algorithm's per-residual basis search is the source of the $|\mathbb{F}|^{n_*}$ factor; a more direct method of finding rank-1 rows could lower the exponent further.
- The 'fix columns, reduce threshold' recursion is a template that could be adapted to other rank notions over finite rings, provided a rank-preserving reduction to bounded dimensions exists.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents two exponential-time algorithms for deciding whether a tensor over a finite field has rank at most R. The exact-rank algorithm (Section 3) first axis-reduces the tensor, then enumerates the "tail" columns of a hypothetical rank-R CPD; for each such tail, it seeks an invertible transformation Q such that each row of Q contracts with the residual tensor to a rank-1 tensor, and then assembles a CPD. It claims O*(|F|^{(R-n_*)(sum_d n_d)+n_*}) time and polynomial space. The border-rank algorithm (Section 4) extends depth-first search to the ring F[x]/(x^H) via a proposed border axis-reduction based on a row-reduction procedure for minimum-rank matrix factorization over that ring, claiming O*(|F|^{H sum_{1<=r<=R} sum_d min(r,n_d)}) time and polynomial space. The paper includes pseudocode for both algorithms and a link to example code.
Significance. If the results are correct, the exact-rank algorithm is a significant guaranteed-correct improvement over brute force for tensor rank over finite fields, with a parameter-free worst-case bound and polynomial space; this is a rare property in the tensor-CPD literature. The border-rank extension would be the first deterministic exact algorithm with a nontrivial worst-case bound for border rank over finite fields, a problem with direct applications to fast matrix multiplication. The exact-rank part appears largely sound, but the border-rank part is currently not fully proven because the border axis-reduction subroutine is only sketched.
major comments (3)
- [4.2] The border axis-reduction procedure is only sketched. The proof that the row-reduced matrix V has the minimum number of rows relies on the assertion that V can be reduced by column operations to the diagonal normal form diag(I_{b0}, x I_{b1}, ..., x^{H-1} I_{b_{H-1}}). This step is stated without proof ("This property means that V can be reduced to the form ... using column operations"), and the paper itself observes in Section 5 that reduced row-echelon form does not always exist over F[x]/(x^H), so standard field intuition does not transfer. Since Algorithm 2 and the claimed border-rank time bound depend crucially on this subroutine computing a minimum-rank factorization, the authors must either provide a complete proof of the normal-form reduction and the minimality of the greedy row-reduction, or revise the claims if a counterexample exists.
- [4.2] The running-time analysis for Algorithm 2 is too terse. The paper states that a call branches to |F|^{H sum_d r_d} children and then says that "if we now define r_d to be the axis-d rank of the original target tensor T", the total time is O*(|F|^{H sum_{1<=r<=R} sum_d min(r,r_d)}). For this bound to follow, one must justify that the dimensions of the tensors that actually reach a recursive call with threshold r are bounded by min(r, r_d) for the original r_d. The argument presumably relies on the fact that subtracting a rank-1 tensor and then axis-reducing cannot increase the axis ranks of the current tensor (since the mode-d unfolding of the residual has the same number of rows as the current unfolding and thus rank at most r_d), but this is not stated. A formal inductive proof of the time bound is needed.
- [3.1 / Algorithm 1] The pseudocode in Algorithm 1 does not match the algorithm described in the text and used in the complexity analysis. In Section 3.1, the algorithm is defined to find Q such that each row v of Q satisfies rk(v x0 tilde T) <= 1, where tilde T = T - [[V0,...,V_{D-1}]] is the residual after removing the enumerated tail columns. However, Algorithm 1 line 9 applies axis_reduce to (v x0 T), not to (v x0 tilde T), and the expression "(v x0 T)0, :, ..., :" is ambiguous; moreover, the conditions on s_d (with d > 1 only) do not obviously test whether the full residual has rank <= 1. If the pseudocode is taken literally, it implements a different algorithm from the one for which the time bound is proved. The pseudocode should be corrected to operate on the residual tilde T and to test the rank condition on all relevant axes, or the proof should be adapted to the pseudocode.
minor comments (5)
- [3.1] In the equation following "then Q ×0 tilde T =", the list of factor matrices appears to include (A0)_{:, :n0} as the second factor; since Q ×0 tilde T has D factors, the list should be I_{n0}, (A1)_{:, :n0}, ..., (A_{D-1})_{:, :n0}. Please correct this typo.
- [4.2] In the proof of Lemma 3, the row-reduction argument over F[x] is somewhat informal; the determinant of A0 A1^T is zero by the Cauchy-Binet formula because A0 has fewer columns than rows. Consider using this cleaner justification.
- [5] The example matrix in Section 5 showing the failure of reduced row-echelon form is typeset as "[[1,1],[x]]", which is not a well-defined matrix; please clarify the dimensions and entries.
- [1] The fixed-R bound for the exact-rank algorithm is typeset in a garbled way (O*(|F|^{D · ((R+1)/D)^2/4}) appears to be a formatting error); please provide the correct expression.
- [6 / References] The reference to Conner (2024) is listed as "private communication"; since the paper supplies the proof of Lemma 3, this is acceptable, but it would be preferable to cite a public source if one exists.
Circularity Check
No circularity: the algorithms and proofs derive their results from definitions and standard field/ring linear algebra, with no fitted parameters, renamed predictions, or load-bearing self-citations.
full rationale
The paper's central claim is an algorithmic time bound for exact and border tensor rank over finite fields. The derivation chain is self-contained: axis-reduction is defined directly from the tensor's unfoldings and rank-preserving change-of-basis operations; the rank bound rd <= R is proved from the existence of a rank-R CPD; the DFS branching count follows by counting factor-matrix entries; and the main algorithm iterates over a finite set of candidate residual tensors. The border-rank algorithm relies on a row-reduction procedure over the ring F[x]/(x^H), which the paper explicitly labels as a sketch and whose minimality argument rests on Lemmas 3 and 4; the paper supplies proofs of those lemmas, and the only external citation for that step is a private communication whose mathematical content is reproduced in the paper. The conclusion's caveat that reduced row-echelon form need not exist over the border ring is an acknowledged correctness limitation of the exact-rank algorithm's generalization, not a circular step. There are no fitted parameters, no prediction-turned-fit, no uniqueness theorem imported from the authors' prior work, and no known result renamed as an organizing principle. The identified weakness in Section 4.2 is a proof gap concerning the sketched border axis-reduction subroutine; it may affect soundness if the normal-form claim fails, but it is not circularity.
Assumptions & free parameters
assumptions (3)
- ad hoc to paper The border row-reduction procedure over F[x]/(x^H) computes a minimum-rank factorization; its correctness is only sketched in Section 4.2.
- standard math Standard finite-field linear algebra (Gaussian elimination, rref, rank factorization) is available in polynomial time.
- domain assumption Tensor rank and border rank definitions over rings are as stated in Section 1 and Section 4.1; border rank inherits the fast matrix multiplication reduction from Bläser 2013.
Cite this review
Pith. "Pith review of Depth-first search for tensor rank and border rank over finite fields." pith.science (2026). https://pith.science/paper/D7HK5Y6U
@misc{pith2026241114676,
author = {Pith},
title = {Pith review of: Depth-first search for tensor rank and border rank over finite fields},
year = {2026},
howpublished = {\url{https://pith.science/paper/D7HK5Y6U}},
note = {Machine review of arXiv:2411.14676}
}
abstract
We present an $O^*\left(|\mathbb{F}|^{(R-n_*)\left(\sum_d n_d\right)+n_*}\right)$-time algorithm for determining whether a tensor of shape $n_0\times\dots\times n_{D-1}$ over a finite field $\mathbb{F}$ has rank $\le R$, where $n_*:=\max_d n_d$; we assume without loss of generality that $\forall d:n_d\le R$. We also extend this problem to its border rank analog, i.e., determining tensor rank over rings of the form $\mathbb{F}[x]/(x^H)$, and give an $O^*\left(|\mathbb{F}|^{H\sum_{1\le r\le R} \sum_d \min(r,n_d)}\right)$-time algorithm. Both of our algorithms use polynomial space.
Reference graph
Works this paper leans on
-
[1]
Alman, Josh and Hengjie, Zhang. (2023). Generalizations of Matrix Multiplication can solve the Light Bulb Problem. https://arxiv.org/abs/2311.01630
work page Pith review arXiv 2023
-
[2]
Alman, Josh and Turok, Ethan and Yu, Hantao and Zhang, Hengzhi. (2024). Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. https://arxiv.org/abs/2309.04683
work page Pith review arXiv 2024
-
[3]
Bl\"aser, Markus. (2013). Fast Matrix Multiplication. Theory of Computing, 5. https://theoryofcomputing.org/articles/gs005/
work page 2013
-
[4]
Chan, Timothy M. (2022). Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs. https://arxiv.org/abs/2211.05345
work page Pith review arXiv 2022
-
[5]
Conner, Austin. (2024). private communication
work page 2024
-
[6]
Courtois, Nicolas T. and Bard, Gregory V. and Hulme, Daniel. (2011). A New General-Purpose Method to Multiply 3x3 Matrices Using Only 23 Multiplications. https://arxiv.org/abs/1108.2830
arXiv 2011
-
[7]
Fawzi, Alhussein and Balog, Matej and Huang, Aja and Hubert, Thomas and Romera-Paredes, Bernardino and Barekatain, Mohammadamin and Novikov, Alexander and Ruiz, Francisco J. R. and Schrittwieser, Julian and Swirszcz, Grzegorz and Silver, David and Hassabis, Demis and Kohli, Pushmeet. (2022). Discovering faster matrix multiplication algorithms with reinfor...
work page 2022
-
[8]
Local Search for Fast Matrix Multiplication
Heule, Marijn J.H. and Kauers, Manuel and Seidl, Martina. Local Search for Fast Matrix Multiplication. https://arxiv.org/abs/1903.11391
work page Pith review arXiv 1903
Show all 11 references
-
[9]
H a stad, John. (1990). Journal of Algorithms, 11, 644-654. https://doi.org/10.1016/0196-6774(90)90014-6
1990 doi
-
[10]
Kauers, Manuel and Moosbauer, Jakob. (2022). Flip Graphs for Matrix Multiplication. https://arxiv.org/abs/2212.01175
2022 arXiv
-
[11]
Shitov, Yaroslav. (2016). How hard is the tensor rank?. https://arxiv.org/abs/1611.01559
2016 arXiv
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.