pith. sign in

arxiv: 2607.02241 · v1 · pith:5WIEWD4Dnew · submitted 2026-07-02 · 💻 cs.CC · cs.DS

Partition Rank and Algebraic Circuit Lower Bounds

Cornelius Brand , Petteri Kaski , Jiaheng Wang This is my paper

Pith reviewed 2026-07-03 01:33 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords partition rankmultiplicative complexityarithmetic circuitstensor rankslice rankNP-hardnessStrassen complexityhyperclique conjecture
0
0 comments X

The pith

Partition ranks bound the multiplicative complexity of arithmetic circuits from below for any constant degree of multilinearity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper connects a generalized notion of tensor rank called partition rank to the multiplicative complexity of arithmetic circuits. It establishes that these ranks lower-bound complexity for multilinear functions of any fixed degree, generalizing the bilinear characterization due to Strassen. This link suggests that rank-based methods can now apply to higher-degree problems in algebraic complexity and to questions such as the hyperclique conjecture.

Core claim

Partition ranks allow us to control the multiplicative complexity, and thus arithmetic complexity, in any constant degree of multilinearity from below, while recovering Strassen's seminal characterization in the bilinear case.

What carries the argument

Partition rank in Naslund's framework, a generalized tensor rank obtained by partitioning the variable indices and summing ordinary ranks over the blocks.

If this is right

  • Arithmetic circuit lower bounds become available through partition-rank calculations for any fixed multilinearity degree.
  • Rank methods gain potential traction on the hyperclique conjecture via this generalization.
  • Partition ranks relate directly to tensor slice rank and its symmetric variant.
  • The symmetric slice rank admits a simple NP-hardness proof.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If partition ranks turn out easier to bound explicitly than classical ranks, the connection could produce new concrete circuit lower bounds.
  • The same partition technique might extend to other circuit models such as formulas or branching programs.
  • Links to slice rank open the possibility of importing extremal-set techniques into algebraic complexity.

Load-bearing premise

Naslund's partition-rank framework can be directly connected to multiplicative complexity in arithmetic circuits for higher-degree multilinearity in the manner asserted.

What would settle it

An explicit multilinear polynomial whose minimal multiplicative complexity in an arithmetic circuit is strictly smaller than its partition rank would falsify the claimed lower bound.

read the original abstract

Strassen's theory of bilinear complexity provides a mathematical characterization of the arithmetic complexity of primitives such as matrix multiplication via the rank of tensors. However, the connection to tensor rank is known to break down in higher degrees of multilinearity. In this work, we highlight an unexplored connection between a generalized notion of tensor rank, which can be defined in Naslund's framework of partition ranks (JCTA 2020), and multiplicative complexity. These partition ranks allow us to control the multiplicative complexity, and thus arithmetic complexity, in any constant degree of multilinearity from below, while recovering Strassen's seminal characterization in the bilinear case. This enables novel potential applications of the rank-based approaches to problems in fine-grained algorithms and complexity, such as the hyperclique conjecture of Lincoln-Williams-Vassilevska Williams (SODA 2018). Moreover, we exhibit connections to established notions of rank, such as tensor slice rank (in the sense of Tao and Sawin), as well as its symmetric variant. For computing the latter symmetric variant, we point out a simple NP-hardness proof, contrasting the rather involved NP-hardness proof for ordinary, non-symmetric tensor slice rank by Bl\"aser et al. (SODA 2021).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that Naslund's partition ranks provide lower bounds on the multiplicative complexity (hence arithmetic complexity) of arithmetic circuits computing d-linear maps for any constant d, recovering Strassen's tensor-rank characterization exactly when d=2. It further relates partition rank to tensor slice rank (Tao-Sawin) and its symmetric variant, gives a simple NP-hardness proof for computing the symmetric slice rank, and suggests applications to the hyperclique conjecture.

Significance. If the claimed reduction from circuit multiplications to partitions holds for d>2, the work supplies a new rank-based tool for algebraic circuit lower bounds beyond the bilinear setting and could feed into fine-grained complexity. The simple NP-hardness argument for symmetric slice rank is a clear, self-contained contribution.

major comments (2)
  1. [Abstract / Main theorem on multiplicative complexity] Abstract and the statement of the main connection (presumably §3 or the theorem relating partition rank to multiplicative complexity): the claim that partition rank lower-bounds the number of multiplications for d>2 requires an explicit inequality or substitution. Given a circuit with m multiplication gates, one must construct a partition of the index set of size at most m such that the output tensor lies in the span defined by that partition. No such mapping is visible in the abstract; if the body only invokes the d=2 case and asserts the extension without deriving the partition from the gates, the central lower-bound statement does not follow.
  2. [Section developing the partition-rank to circuit connection] The generalization beyond Strassen's bilinear characterization is load-bearing for all claimed applications (including hyperclique). The manuscript must therefore supply the concrete reduction for constant d>2 rather than relying on the Naslund framework alone; absence of this step leaves the higher-degree claim unsubstantiated.
minor comments (2)
  1. [Introduction / Main results] Add equation numbers to the formal statement of the partition-rank lower bound so that the precise inequality relating rank to multiplication count can be referenced.
  2. [Section on symmetric slice rank] The NP-hardness proof for symmetric slice rank is presented as simple; include a self-contained paragraph or short subsection so readers can verify it without external references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater explicitness in the central reduction. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / Main theorem on multiplicative complexity] Abstract and the statement of the main connection (presumably §3 or the theorem relating partition rank to multiplicative complexity): the claim that partition rank lower-bounds the number of multiplications for d>2 requires an explicit inequality or substitution. Given a circuit with m multiplication gates, one must construct a partition of the index set of size at most m such that the output tensor lies in the span defined by that partition. No such mapping is visible in the abstract; if the body only invokes the d=2 case and asserts the extension without deriving the partition from the gates, the central lower-bound statement does not follow.

    Authors: We agree that the abstract should state the bound explicitly and that the derivation must be self-contained. Section 3 does construct the partition by associating each multiplication gate with a block that respects the d index sets, but the presentation can be tightened. In the revision we will add the inequality "partition rank ≤ number of multiplications" to the abstract and insert a short lemma that explicitly maps the gates of a d-linear circuit to a partition of size at most m. revision: yes

  2. Referee: [Section developing the partition-rank to circuit connection] The generalization beyond Strassen's bilinear characterization is load-bearing for all claimed applications (including hyperclique). The manuscript must therefore supply the concrete reduction for constant d>2 rather than relying on the Naslund framework alone; absence of this step leaves the higher-degree claim unsubstantiated.

    Authors: The section does supply the reduction by lifting the bilinear argument to the partition-rank definition for constant d. Nevertheless, the referee is correct that a fully self-contained derivation, independent of external references to Naslund, would strengthen the paper. We will expand the section with a direct proof that any d-linear circuit with m multiplications yields a partition of size ≤ m whose span contains the output tensor. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation relies on external Naslund framework and Strassen characterization

full rationale

The paper explicitly cites Naslund (JCTA 2020) for the partition-rank definition and positions its contribution as highlighting a connection to multiplicative complexity while recovering the known bilinear case from Strassen. No self-citations appear in the abstract or described claims, no parameters are fitted to data, and no equation is shown reducing to a prior result by the same authors. The central claim is therefore an asserted link between independent prior notions rather than a self-referential reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of Naslund's partition-rank definition to control multiplicative complexity; this is treated as a domain assumption imported from prior work rather than derived here.

axioms (1)
  • domain assumption Naslund's framework of partition ranks (JCTA 2020) defines a generalized tensor rank that interacts with multiplicative complexity as required.
    The paper invokes this prior framework to extend Strassen's characterization.

pith-pipeline@v0.9.1-grok · 5747 in / 1169 out tokens · 32851 ms · 2026-07-03T01:33:58.259975+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 18 canonical work pages · 2 internal anchors

  1. [1]

    Small subalgebras of polynomial rings and Stillman’s conjecture.J

    Tigran Ananyan and Melvin Hochster. Small subalgebras of polynomial rings and Stillman’s conjecture.J. Amer. Math. Soc., 33(1):291–309, 2020.doi:10.1090/jams/932. 5

    work page doi:10.1090/jams/932 2020

  2. [2]

    On the strength of general polynomials.Linear Multilinear Algebra, 70(21):6114–6140, 2022.doi:10.1080/03081087.2021.1947955

    Arthur Bik and Alessandro Oneto. On the strength of general polynomials.Linear Multilinear Algebra, 70(21):6114–6140, 2022.doi:10.1080/03081087.2021.1947955. 5

    work page doi:10.1080/03081087.2021.1947955 2022

  3. [3]

    Number 5 in Graduate Surveys

    Markus Bläser.Fast Matrix Multiplication. Number 5 in Graduate Surveys. Theory of Computing Library, 2013. doi:10.4086/toc.gs.2013.005. 2

    work page doi:10.4086/toc.gs.2013.005 2013

  4. [4]

    On the orbit closure containment problem and slice rank of tensors

    Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. On the orbit closure containment problem and slice rank of tensors. In Dániel Marx, editor,Proceedings of the 2021 ACM- SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2565–2584. SIAM, 2021.doi:10.1137/1.97816119...

    work page doi:10.1137/1.9781611976465.152 2021

  5. [5]

    Beyond bilinear complexity: What works and what breaks with many modes?, 2026

    Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang. Beyond bilinear complexity: What works and what breaks with many modes?, 2026. (to appear in CCC 2026). arXiv:2602.11975. 5

    work page arXiv 2026

  6. [6]

    Amin Shokrollahi.Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]

    Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi.Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer- Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig.doi:10.1007/978-3-662-03338-8. 1, 3

    work page doi:10.1007/978-3-662-03338-8 1997

  7. [7]

    The Chasm at Depth Four, and Tensor Rank : Old results, new insights

    Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V Vinay. The chasm at depth four, and tensor rank: Old results, new insights, 2017.arXiv:1606.04200. 5

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  8. [8]

    Golub, Lek-Heng Lim, and Bernard Mourrain

    Pierre Comon, Gene H. Golub, Lek-Heng Lim, and Bernard Mourrain. Symmetric tensors and symmetric tensor rank.SIAM J. Matrix Anal. Appl., 30(3):1254–1279, 2008.doi:10.1137/060661569. 5

    work page doi:10.1137/060661569 2008

  9. [9]

    Erratum: A counterexample to Comon’s conjecture.SIAM J

    Jan Draisma. Erratum: A counterexample to Comon’s conjecture.SIAM J. Appl. Algebra Geom., 8(1):225, 2024. doi:10.1137/23M1623781. 5

    work page doi:10.1137/23m1623781 2024

  10. [10]

    Degree-restricted strength de- compositions and algebraic branching programs

    Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov. Degree-restricted strength de- compositions and algebraic branching programs. In Anuj Dawar and Venkatesan Guruswami, editors,42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, IIT Madras, Chennai, India, December 18-2...

    work page doi:10.4230/lipics.fsttcs.2022.20 2022

  11. [11]

    Tensor rank is NP-complete.J

    Johan Håstad. Tensor rank is NP-complete.J. Algorithms, 11(4):644–654, 1990.doi:10.1016/0196- 6774(90)90014-6. 4

    work page doi:10.1016/0196- 1990

  12. [12]

    Superpolynomial lower bounds against low-depth algebraic circuits.Commun

    Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits.Commun. ACM, 67(2):101–108, 2024.doi:10.1145/3611094. 5

    work page doi:10.1145/3611094 2024

  13. [13]

    Ryan Williams

    Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor,Proceedings of the Twenty-Ninth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236–1252. SIAM, 2018.doi:10.1137/1.9781611975031.80. 2 11

    work page doi:10.1137/1.9781611975031.80 2018

  14. [14]

    The partition rank of a tensor andk-right corners inFn q.J

    Eric Naslund. The partition rank of a tensor andk-right corners inFn q.J. Combin. Theory Ser. A, 174:105190, 25, 2020.doi:10.1016/j.jcta.2019.105190. 2, 5

    work page doi:10.1016/j.jcta.2019.105190 2020

  15. [15]

    Tensor-rank and lower bounds for arithmetic formulas.J

    Ran Raz. Tensor-rank and lower bounds for arithmetic formulas.J. ACM, 60(6):40:1–40:15, 2013.doi:10.1145/ 2535928. 5

    2013

  16. [16]

    The complexity of tensor rank.Theory Comput

    Marcus Schaefer and Daniel Štefankovič. The complexity of tensor rank.Theory Comput. Syst., 62(5):1161–1174, 2018.doi:10.1007/S00224-017-9800-Y. 4

    work page doi:10.1007/s00224-017-9800-y 2018

  17. [17]

    How hard is the tensor rank?

    Yaroslav Shitov. How hard is the tensor rank?, 2016.arXiv:1611.01559. 4

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  18. [18]

    Gaussian elimination is not optimal.Numer

    Volker Strassen. Gaussian elimination is not optimal.Numer. Math., 13:354–356, 1969.doi:10.1007/BF02165411. 1

    work page doi:10.1007/bf02165411 1969

  19. [19]

    Vermeidung von Divisionen.J

    Volker Strassen. Vermeidung von Divisionen.J. Reine Angew. Math., 264:184–202, 1973.doi:10.1515/ crll.1973.264.184. 1, 2

    1973

  20. [20]

    Tensor rank is hard to approximate

    Joseph Swernofsky. Tensor rank is hard to approximate. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, Princeton, NJ, USA, August 20-22, 2018, LIPIcs, pages 26:1–26:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 201...

    work page doi:10.4230/lipics.approx-random.2018.26 2018

  21. [21]

    A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound

    Terence Tao. A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound. URL: https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach- ellenberg-gijswijt-capset-bound/. 4

    2016

  22. [22]

    slice rank

    Terence Tao and Will Sawin. Notes on the “slice rank” of tensors. URL:https://terrytao.wordpress.com/2016/ 08/24/notes-on-the-slice-rank-of-tensors/. 4

    2016

  23. [23]

    Torrance

    Douglas A. Torrance. Generic forms of low Chow rank.J. Algebra Appl., 16(3):1750047, 10, 2017.doi:10.1142/ S0219498817500475. 5 12

    2017