{"id":"6bb27854-26af-44c3-aed0-559b123c9480","arxiv_id":"2411.14676","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An exact algorithm with O*(|F|^{(R-max_d n_d)(sum_d n_d)+max_d n_d}) time decides tensor rank over finite fields, with a border-rank variant over F[x]/(x^H).","lead":"This paper presents faster exponential-time algorithms that decide, with certainty, whether a given tensor over a finite field has rank at most R, and the border-rank analogue. The speedup comes from a reduction step that shrinks the tensor's dimensions before a depth-first search over candidate decompositions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Border axis-reduction in Section 4.2 is only sketched; if its row-reduction/normal-form claim fails, Algorithm 2 and the border-rank time bound are unsound.","rationale":"The exact tensor-rank algorithm in Section 3 is presented with a coherent correctness argument: the axis-reduction step is valid, the rref(A0) structure follows from the axis-reduced rank, and the enumeration plus reconstruction of Q is plausible and matches the stated complexity. I found no concrete flaw there. The border-rank algorithm, by contrast, rests on a row-reduction procedure over a non-field ring whose optimality proof is only sketched; the paper itself calls it a sketch and acknowledges that standard row-echelon intuition fails. This is exactly the reader's weakest-assumption point, and it is load-bearing because a wrong minimum-rank factorization in border axis_reduce would invalidate both the algorithm's correctness and its time bound. The proposed test would provide a concrete falsification check. Since the concern is the same gap already identified by the reader, and the appropriate disposition remains CONDITIONAL, I recommend no change to the reader's verdict.","tokens_in":9935,"tokens_out":39401,"duration_ms":428283,"concrete_test":"Implement the sketched greedy row-reduction over F_2[x]/(x^H) for H=2,3,4 and compare, for every 2x2 and 3x3 matrix (exhaustive, or a large random sample if exhaustive is too large), its output row count with the true minimum r computed by exhaustive search over all factorizations M = U V. Any mismatch would refute Algorithm 2; a clean run would increase confidence but would not by itself close the proof gap. Separately, formalize the column-reduction step: prove that row i of the row-reduced V has every entry divisible by x^{h_i} and that pivot columns have zeros below the pivot, then exhibit the explicit column operations that reach the diagonal normal form without changing the number of rows.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The border-rank algorithm depends on a row-reduction procedure over F[x]/(x^H) that the paper explicitly introduces as a sketch (Section 4.2, \"We sketch the following procedure for row-reduction on M\"). The proof that the resulting V has the minimum number of rows hinges on two assertions: (1) V can be transformed by column operations into the diagonal normal form diag(I_{b0}, x I_{b1}, ..., x^{H-1} I_{bH-1}), and (2) Lemmas 3-4 then imply the rank equals the number of nonzero diagonal blocks. Lemma 4 is proven using Lemma 3, but the column-reduction step is not actually demonstrated; the text only says \"This property means that V can be reduced to the form ... using column operations.\" The paper's own conclusion states that reduced row-echelon form does not always exist over this ring and that a full-rank square matrix need not be invertible, so ordinary field intuition does not transfer. If the greedy procedure ever outputs a row count larger than the true minimum rank of M, then border axis_reduce computes wrong dimensions and ranks, breaking both the correctness of Algorithm 2 and the claimed O*(|F|^{H sum min(r, n_d)}) bound. This is a proof gap rather than a demonstrated counterexample, but it is the least securely supported link in the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10214,"tokens_out":34989,"duration_ms":314365,"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":[{"comment":"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.","section":"4.2"},{"comment":"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.","section":"4.2"},{"comment":"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.","section":"3.1 / Algorithm 1"}],"minor_comments":[{"comment":"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.","section":"3.1"},{"comment":"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.","section":"4.2"},{"comment":"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.","section":"5"},{"comment":"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.","section":"1"},{"comment":"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.","section":"6 / References"}],"recommendation":"major_revision","confidential_remarks":"The exact-rank algorithm appears to be a solid contribution, and the paper is generally well motivated. The main weakness is the border-rank section: the border axis-reduction subroutine is not rigorously established, and the pseudocode for the exact-rank algorithm has discrepancies with the text. Given that the border-rank claim is load-bearing and currently unproven, a major revision is appropriate. The authors may consider either providing a complete proof of the border row-reduction procedure or separating the border-rank results from the paper if they remain unresolved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it so you don't have to: the exact-rank algorithm is the real contribution, and it looks right; the border-rank half is a sketch with a load-bearing gap. The paper gives a deterministic, guaranteed-correct exponential-time algorithm for tensor rank over finite fields with exponent (R-n_*)(sum n_d)+n_*, improving over brute force. The key trick—axis-reduce the tensor so every mode has length at most R, then fix the first n_0 columns of every factor matrix and solve a rank-at-most-1 residue problem—is clever and new as far as I know. The proof in Section 3 is careful, and the complexity analysis checks out. The code being public helps.\n\nThe border-rank extension is where I get cautious. To run the same DFS over F[x]/(x^H), the paper needs a border analog of axis-reduction, i.e., minimum-rank factorization of a matrix over that ring. The procedure in Section 4.2 is explicitly sketched, and the proof that it returns a minimum row count relies on an asserted normal form: that the row-reduced V can be put into diag(I_{b0}, x I_{b1}, ..., x^{H-1} I_{b_{H-1}}) by column operations. That column-reduction step is not demonstrated. This matters because the paper itself notes rref does not always exist over this ring, so the usual field intuition does not transfer. If the greedy row-reduction can overestimate the minimum rank, Algorithm 2 and the claimed O*(|F|^{H sum min(r,n_d)}) bound collapse. I do not see a counterexample, and Lemma 3's proof is fine (the private communication is actually proven in the text), so this looks repairable rather than fatal. But as written, the border-rank correctness is not established.\n\nMinor: the time bound in Section 4.2 is stated with r_d (axis-ranks of the target) while the abstract uses n_d; that is fine since r_d <= n_d, but the paper could be clearer that the advertised bound is the weaker, handier one.\n\nVerdict: this deserves a serious referee. The exact-rank part alone is worth publishing, and the border-rank gap is specific enough to be fixed by a revision. I would send it out.","headline":"Exact-rank algorithm is solid and new; border-rank half has a load-bearing proof gap in the row-reduction subroutine.","tokens_in":10677,"tokens_out":4551,"would_cite":true,"duration_ms":40981,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","68Q25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tensor rank","border rank","finite fields","canonical polyadic decomposition","depth-first search","axis-reduction","matrix multiplication","polynomial space"],"falsifier":"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.","tokens_in":9720,"feed_emoji":"🔢","tokens_out":13927,"duration_ms":121423,"temperature":0.7,"pith_summary":"This paper presents exponential-time algorithms that determine whether a tensor over a finite field has rank at most $R$, returning a decomposition if one exists and proving impossibility otherwise; the same guarantee is given for border rank over the ring $\\mathbb{F}[x]/(x^H)$. The exact-rank algorithm runs in $O^*(|\\mathbb{F}|^{(R-n_*)(\\sum_d n_d)+n_*})$ time, where $n_*$ is the largest dimension of the tensor, and the border-rank algorithm runs in $O^*(|\\mathbb{F}|^{H\\sum_{1\\le r\\le R}\\sum_d \\min(r,n_d)})$ time. Both algorithms use only polynomial space. The key to both is axis-reduction, a rank-preserving transformation that shrinks every dimension to at most $R$, followed by a depth-first enumeration that fixes one column of each factor matrix at a time. These bounds improve substantially on the brute-force cost $|\\mathbb{F}|^{R\\sum_d n_d}$ and, if correct, supply a deterministic way to certify the absence of low-rank decompositions.","feed_headline":"Exact tensor-rank search over finite fields beats brute force","feed_subtitle":"New depth-first algorithms decide rank and border rank in guaranteed time, using only polynomial memory.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines border rank and states that border CPDs of the matrix-multiplication tensor yield fast matrix multiplication; the border-rank problem the paper solves is framed with this definition.","marker":"(Bläser, 2013)"},{"why":"Proves NP-completeness of tensor rank over finite fields, the hardness result that makes the exponential-time improvements meaningful.","marker":"(Håstad, 1990)"},{"why":"Supplies the rank computation for $x^h I_n$ over $\\mathbb{F}[x]/(x^H)$ used in Lemma 3, the fact that makes the border axis-reduction's row count a true rank bound.","marker":"(Conner, 2024)"},{"why":"Shows tensor rank over the integers is undecidable, motivating the restriction to finite fields.","marker":"(Shitov, 2016)"}],"fun_headline_variants":["Tensor rank over finite fields decided by new DFS","Exact tensor and border rank via depth-first search","Polynomial-space algorithm for tensor rank over finite fields","Depth-first search decides tensor rank over finite fields","Guaranteed-time algorithm for tensor rank over finite fields"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tensor rank over finite fields decided by new DFS","Exact tensor and border rank via depth-first search","Polynomial-space algorithm for tensor rank over finite fields","Depth-first search decides tensor rank over finite fields","Guaranteed-time algorithm for tensor rank over finite fields"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000689,"raw_usage":{"total_tokens":3116,"prompt_tokens":933,"completion_tokens":2183,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":2118}},"tokens_in":549,"tokens_out":2183,"duration_ms":15686,"temperature":1.0,"reasoning_tokens":2118,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:03:23.579130+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the rank computation for $x^h I_n$ over $\\mathbb{F}[x]/(x^H)$ used in Lemma 3, the fact that makes the border axis-reduction's row count a true rank bound."}],"review_version":1}