Pith. sign in

REVIEW 2 major objections 2 minor 50 references

The Kronecker product applied to iterated matrix multiplication yields the hypercomputant, a VNP-complete and VW[1]-complete polynomial.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-27 18:31 UTC pith:37GFZ55X

load-bearing objection The hypercomputant gives a new complete problem for VNP and VW[1] over semirings and noncommutative algebras via Kronecker product on IMM, with the membership direction needing an explicit circuit argument. the 2 major comments →

arxiv 2606.08363 v1 pith:37GFZ55X submitted 2026-06-06 cs.CC math.RA

Kronecker products and iterated matrix multiplication

Christian Ikenmeyer This is my paper
classification cs.CC math.RA
keywords Kronecker producthypercomputantVNP-completenessiterated matrix multiplicationhyperdeterminantalgebraic complexityparameterized complexityalgebraic branching programs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper shows that the Kronecker product of tensors converts the determinant polynomial into Cayley's first hyperdeterminant. Applying the same operation to iterated matrix multiplication produces a new polynomial called the hypercomputant. Hardness for VNP and VW[1] follows directly from the equivariance property of the Kronecker product, which transfers known hardness results while preserving membership in the classes. The argument holds over arbitrary commutative semirings and extends to the tensor algebra and exterior algebra, supplying canonical complete objects for noncommutative VNP and monotone VNP. Additional results include optimal algebraic branching program width lower bounds in these settings and the polystability of the hypercomputant with its isotypic components characterized by stabilizers.

Core claim

The hypercomputant is a VNP-complete and VW[1]-complete polynomial obtained from iterated matrix multiplication via the Kronecker product. Its hardness follows from the equivariance of the Kronecker product, which transfers the known hardness of the determinant or iterated matrix multiplication. This construction works over arbitrary commutative semirings, the tensor algebra, and the exterior algebra, yielding versions of noncommutative VNP and monotone VNP with the hypercomputant as the complete object.

What carries the argument

The equivariance of the Kronecker product, which transfers computational hardness from the determinant or iterated matrix multiplication to the hypercomputant while preserving membership in VNP and VW[1] across semirings, tensor algebras, and exterior algebras.

Load-bearing premise

The equivariance property of the Kronecker product transfers the known hardness of the determinant or iterated matrix multiplication directly to the hypercomputant while preserving membership in VNP and VW[1] across the listed algebraic structures.

What would settle it

An explicit small algebraic circuit for the hypercomputant over the integers, verified by direct expansion on small input sizes, would falsify the VNP-completeness claim if it contradicts the reduction via equivariance.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The hypercomputant serves as the canonical complete object for noncommutative VNP when working in the tensor algebra.
  • The hypercomputant serves as the canonical complete object for monotone VNP when working over the nonnegative reals.
  • Optimal algebraic branching program width lower bounds hold in both the noncommutative and monotone settings, though the bounds are not always identical.
  • The hypercomputant is polystable and its isotypic components are characterized by their stabilizers.

Where Pith is reading between the lines

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

  • The differing ABP width lower bounds between noncommutative and monotone settings point to distinct parameterized complexity behaviors that could be compared on other natural polynomials.
  • The same Kronecker construction might be tested on other base problems besides iterated matrix multiplication to produce additional complete objects in these algebraic settings.
  • One could evaluate the hypercomputant explicitly on small tensors to check whether its stabilizer structure matches the predicted isotypic decomposition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript defines the hypercomputant as the result of applying the Kronecker product to iterated matrix multiplication (IMM). It claims this yields a polynomial that is both VNP-complete and VW[1]-complete over arbitrary commutative semirings, the tensor algebra (giving a noncommutative VNP), and the exterior algebra, with hardness transferred via equivariance of the Kronecker product. The work also derives versions of monotone VNP, obtains optimal algebraic branching program (ABP) width lower bounds in the noncommutative and monotone settings (which are not always identical), proves polystability of the hypercomputant, and characterizes its isotypic components by their stabilizers.

Significance. If the membership arguments and equivariance-based hardness reductions hold with explicit size bounds, the hypercomputant would serve as a canonical complete problem unifying several extensions of VNP, enabling direct comparisons between noncommutative and monotone regimes via parameterized complexity. The optimal ABP lower bounds and stability results would be concrete technical contributions in those settings.

major comments (2)
  1. [Abstract and the section establishing VNP membership over semirings] The central claim requires that the hypercomputant lies in VNP (and VW[1]) over commutative semirings. Equivariance transfers hardness from IMM or determinant, but VNP membership is witnessed by an explicit polynomial-size circuit or ABP; over semirings the absence of subtraction means standard determinant circuits do not apply directly. The manuscript must therefore supply a concrete size-preserving translation from an IMM circuit to a hypercomputant circuit in this setting (see the paragraph following the definition of the hypercomputant and the subsequent completeness argument).
  2. [Section on the tensor algebra and noncommutative VNP] For the tensor-algebra version yielding noncommutative VNP, the circuit model changes because multiplication is noncommutative. The equivariance argument alone does not automatically produce a size bound in the noncommutative circuit model; an explicit construction mapping IMM circuits to hypercomputant circuits while preserving polynomial size is needed to confirm membership (see the paragraph on the tensor algebra and noncommutative VNP).
minor comments (2)
  1. [Introduction] Notation for the hypercomputant and its variants should be introduced with a single displayed equation early in the paper to avoid repeated inline definitions.
  2. [Section on ABP lower bounds] The comparison of ABP widths between noncommutative and monotone settings would benefit from a side-by-side table summarizing the bounds for each regime.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and for highlighting the need for explicit circuit constructions to establish VNP membership. We address each major comment below and will revise the manuscript to include the requested size bounds and translations.

read point-by-point responses

  1. Referee: [Abstract and the section establishing VNP membership over semirings] The central claim requires that the hypercomputant lies in VNP (and VW[1]) over commutative semirings. Equivariance transfers hardness from IMM or determinant, but VNP membership is witnessed by an explicit polynomial-size circuit or ABP; over semirings the absence of subtraction means standard determinant circuits do not apply directly. The manuscript must therefore supply a concrete size-preserving translation from an IMM circuit to a hypercomputant circuit in this setting (see the paragraph following the definition of the hypercomputant and the subsequent completeness argument).

    Authors: We agree that an explicit size-preserving translation strengthens the membership argument over semirings. The hypercomputant is defined directly via the Kronecker product applied to the IMM tensor; each output entry is a sum of products of original entries, which can be realized by a circuit whose size is at most quadratic in the dimension times the size of the IMM circuit. This construction works verbatim over any commutative semiring because it uses only addition and multiplication. We will add a dedicated paragraph after the definition that states the precise size bound (O(d^2 · s) where s is the IMM circuit size and d the dimension) and confirms membership in VNP and VW[1]. revision: yes

  2. Referee: [Section on the tensor algebra and noncommutative VNP] For the tensor-algebra version yielding noncommutative VNP, the circuit model changes because multiplication is noncommutative. The equivariance argument alone does not automatically produce a size bound in the noncommutative circuit model; an explicit construction mapping IMM circuits to hypercomputant circuits while preserving polynomial size is needed to confirm membership (see the paragraph on the tensor algebra and noncommutative VNP).

    Authors: The tensor-algebra version inherits the same Kronecker construction, now interpreted in the free tensor algebra. Because the noncommutative IMM circuit consists of matrix multiplications that remain noncommutative under the block-Kronecker embedding, the same quadratic blow-up yields a noncommutative circuit of polynomial size. We will insert an explicit mapping in the tensor-algebra section that describes how each noncommutative gate is replaced by a block of Kronecker gates, preserving the noncommutative multiplication order and giving a concrete size bound. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness transferred via external equivariance; membership claims rest on explicit algebraic constructions

full rationale

The paper derives VNP- and VW[1]-completeness of the hypercomputant by applying the Kronecker product to iterated matrix multiplication and invoking the equivariance property to map known hard instances (determinant, IMM) while preserving membership. Equivariance is presented as a standard algebraic fact applying over semirings, tensor algebra, and exterior algebra; no equation reduces the target polynomial to a fitted parameter or prior self-citation by construction. The parameterized lower bounds and polystability results are obtained via standard techniques applied to the new object. No load-bearing step collapses to a self-definition or renamed input.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The construction rests on standard algebraic properties of the Kronecker product and on the definition of VNP and VW[1] in the cited literature. The hypercomputant itself is an invented entity whose completeness is the main claim.

axioms (2)
  • standard math Kronecker product is equivariant with respect to the natural actions on tensors and polynomials.
    Invoked to transfer hardness from determinant or iterated matrix multiplication to the hypercomputant.
  • domain assumption VNP and VW[1] are defined via algebraic circuits or branching programs over the given semirings and algebras.
    Background definitions from algebraic complexity theory.
invented entities (1)
  • hypercomputant no independent evidence
    purpose: New polynomial obtained by Kronecker product on iterated matrix multiplication that serves as the complete object for VNP and VW[1] in multiple settings.
    Defined in the paper; no independent existence or falsifiable prediction outside the construction is stated in the abstract.

pith-pipeline@v0.9.1-grok · 5694 in / 1543 out tokens · 24595 ms · 2026-06-27T18:31:55.444203+00:00 · methodology

0 comments
read the original abstract

We observe that the Kronecker product of tensors is the operation that converts the determinant polynomial into Cayley's first hyperdeterminant. We apply the Kronecker product to iterated matrix multiplication, which results in the hypercomputant, a VNP-complete and VW[1]-complete polynomial whose hardness we prove via the equivariance of the Kronecker product. The construction works over arbitrary commutative semirings and also for the tensor algebra and the exterior algebra. For the tensor algebra this gives a version of "noncommutative VNP", and for polynomials over the nonnegative real numbers this gives a version of "monotone VNP", each with the hypercomputant as the complete object. We take a parameterized complexity viewpoint and compare the noncommutative setting and the monotone setting. Using standard techniques we obtain optimal algebraic branching program width lower bounds in both settings, and these are notably not always the same. We also prove the polystability of the hypercomputant and that its isotypic components are characterized by their stabilizer.

Figures

Figures reproduced from arXiv: 2606.08363 by Christian Ikenmeyer.

Figure 1
Figure 1. Figure 1: Removal of constant edges from ABPs. Proof. If w(F) ≤ r, then F ≤ Ξn,d, so there is T ∈ End with T(Ξn,d) = F. We take the width n ABP that computes Ξn,d and apply T to each edge label to obtain a width n ABP that computes F. For the other direction, we are given a width r ABP that computes F [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An ABP that computes f7,3. The vertex label at each vertex v is the weighted sum of all s-v-paths. 3.10 Example. The elementary symmetric polynomial is defined as en,d = X 1≤i1<i2<···<id≤n xi1 · · · xid . Its layered variant is defined as fn,d = X 1≤i1<i2<···<id≤n x (1) i1 · · · x (d) id . Clearly en,d ≤ fn,d by mapping x (k) i to xi . We have fn,d = fn−1,d−1 · x (d) n + fn−1,d 8 [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 3
Figure 3. Figure 3: An ABP that computes det3 = χ3,3. and this recursion can be used directly to construct a width n ABP that computes fn,d, see [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Formal implications between conjectures. The setting is [PITH_FULL_IMAGE:figures/full_fig_p029_4.png] view at source ↗

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

50 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    o bler, Uwe Sch \

    Vikraman Arvind, Johannes K \"o bler, Uwe Sch \"o ning, and Rainer Schuler. If N P has polynomial-size circuits, then M A = A M . Theoretical Computer Science , 137(2):279--282, 1995

    1995

  2. [2]

    On complexity of the subpattern problem

    Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM Journal on Discrete Mathematics , 22(2):629--649, 2008

    2008

  3. [3]

    Tensor slice rank and C ayley's first hyperdeterminant

    Alimzhan Amanov and Damir Yeliussizov. Tensor slice rank and C ayley's first hyperdeterminant. Linear Algebra and its Applications , 656:224--246, 2023

    2023

  4. [4]

    R.B. Bapat. Mixed discriminants of positive semidefinite matrices. Linear Algebra and its Applications , 126:107--124, 1989

    1989

  5. [5]

    New algorithms for linear k-matroid intersection and matroid k-parity problems

    Alexander I Barvinok. New algorithms for linear k-matroid intersection and matroid k-parity problems. Mathematical Programming , 69(1):449--470, 1995

    1995

  6. [6]

    Parameterized Valiant’s Classes

    Markus Bl\" a ser and Christian Engels. Parameterized Valiant’s Classes . In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) , volume 148 of LIPIcs , pages 3:1--3:14, 2019. The arXiv version contains the full proofs: 1907.12287v2

    work page arXiv 2019

  7. [7]

    Fundamental invariants of orbit closures

    Peter B \"u rgisser and Christian Ikenmeyer. Fundamental invariants of orbit closures. Journal of Algebra , 477:390--434, 2017

    2017

  8. [8]

    Algebraic branching programs, border complexity, and tangent spaces

    Markus Bl \"a ser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic branching programs, border complexity, and tangent spaces. In 35th Computational Complexity Conference , 2020

    2020

  9. [9]

    Fast matrix multiplication

    Markus Bl \"a ser. Fast matrix multiplication. Theory of Computing , pages 1--60, 2013

    2013

  10. [10]

    An overview of mathematical issues arising in the geometric complexity theory approach to V P V N P

    Peter B \"u rgisser, Joseph M Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the geometric complexity theory approach to V P V N P . SIAM Journal on Computing , 40(4):1179--1209, 2011

    2011

  11. [11]

    C ook's versus V aliant's hypothesis

    Peter B \"u rgisser. C ook's versus V aliant's hypothesis. Theoretical Computer Science , 235(1):71--88, 2000

    2000

  12. [12]

    M \'e moire sur les hyperd \'e terminants

    MA Cayley. M \'e moire sur les hyperd \'e terminants. 1846

  13. [13]

    An efficient tree decomposition method for permanents and mixed discriminants

    Diego Cifuentes and Pablo A Parrilo. An efficient tree decomposition method for permanents and mixed discriminants. Linear Algebra and its Applications , 493:45--81, 2016

    2016

  14. [14]

    R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, London, UK, 2013

    2013

  15. [15]

    Permanents of d-dimensional matrices

    Stephen J Dow and Peter M Gibson. Permanents of d-dimensional matrices. Linear Algebra and its Applications , 90:133--145, 1987

    1987

  16. [16]

    Some concrete questions on the border complexity of polynomials

    Michael Forbes. Some concrete questions on the border complexity of polynomials. Workshop on Algebraic Complexity Theory (WACT), https://www.youtube.com/watch?v=1HMogQIHT6Q, 2016

    2016

  17. [17]

    Geometric aspects of iterated matrix multiplication

    Fulvio Gesmundo. Geometric aspects of iterated matrix multiplication. Journal of Algebra , 461:42--64, 2016

    2016

  18. [18]

    An Upper Bound for the Permanent versus Determinant Problem

    Bruno Grenet. An Upper Bound for the Permanent versus Determinant Problem . Manuscript, 2011

    2011

  19. [19]

    Classical complexity and quantum entanglement

    Leonid Gurvits. Classical complexity and quantum entanglement. Journal of Computer and System Sciences , 69(3):448--484, 2004. Special Issue on STOC 2003

    2004

  20. [20]

    On the complexity of mixed discriminants and related problems

    Leonid Gurvits. On the complexity of mixed discriminants and related problems. In Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29--September 2, 2005. Proceedings 30 , pages 447--458. Springer, 2005

    2005

  21. [21]

    Most tensor problems are N P -hard

    Christopher J Hillar and Lek-Heng Lim. Most tensor problems are N P -hard. Journal of the ACM (JACM) , 60(6):1--39, 2013

    2013

  22. [22]

    Geometric complexity theory and orbit closures of homogeneous forms

    Jesko H \"u ttenhain. Geometric complexity theory and orbit closures of homogeneous forms . PhD thesis, TU Berlin, 2017

    2017

  23. [23]

    On the gradient of the coefficient of the characteristic polynomial

    Christian Ikenmeyer. On the gradient of the coefficient of the characteristic polynomial. arXiv:2511.04954, 2025

    work page arXiv 2025

  24. [24]

    Field-independent Kronecker-plethysm isomorphisms

    Christian Ikenmeyer, Heidi Omar, and Dimitrios Tsintsilidas. Field-independent kronecker-plethysm isomorphisms. arXiv:2509.10069v1, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  25. [25]

    Richard M. Karp. Reducibility among Combinatorial Problems , pages 85--103. 1972

    1972

  26. [26]

    Instability in invariant theory

    George R Kempf. Instability in invariant theory. Annals of Mathematics , 108(2):299--316, 1978

    1978

  27. [27]

    Karp and Richard J

    Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L'Enseignement Math\'ematique , 1982

    1982

  28. [28]

    Monotone arithmetic complexity of graph homomorphism polynomials

    Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. Monotone arithmetic complexity of graph homomorphism polynomials. Algorithmica , 85(9):2554--2579, 2023

    2023

  29. [29]

    Tensors: geometry and applications: geometry and applications , volume 128

    Joseph M Landsberg. Tensors: geometry and applications: geometry and applications , volume 128. American Mathematical Soc., 2011

    2011

  30. [30]

    Geometric complexity theory: an introduction for geometers

    Joseph M Landsberg. Geometric complexity theory: an introduction for geometers. Annali dell'universita'di Ferrara , 61(1):65--117, 2015

    2015

  31. [31]

    J. S. Lomont and M. S. Cheena. A multilinearity property of determinant functions. Linear and Multilinear Algebra , 14(3):199--223, 1983

    1983

  32. [32]

    Adh \'e rences d'orbite et invariants

    Domingo Luna. Adh \'e rences d'orbite et invariants. Inventiones mathematicae , 29(3):231--238, 1975

    1975

  33. [33]

    The L ean M athematical L ibrary

    The mathlib C ommunity. The L ean M athematical L ibrary. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs , CPP 2020, New Orleans, LA, USA, January 2020. ACM

    2020

  34. [34]

    Permanents , volume 6

    Henryk Minc. Permanents , volume 6. Cambridge University Press, 1984

    1984

  35. [35]

    Geometric complexity theory I : An approach to the P vs.\ NP and related problems

    Ketan D Mulmuley and Milind Sohoni. Geometric complexity theory I : An approach to the P vs.\ NP and related problems. SIAM Journal on Computing , 31(2):496--526, 2001

    2001

  36. [36]

    Lower bounds for non-commutative computation

    Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing , pages 410--418, 1991

    1991

  37. [37]

    On the complexity of the subgraph problem

    Jaroslav Ne s et r il and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae , 26(2):415--419, 1985

    1985

  38. [38]

    Mixed discriminants connected with positive semidefinite quadratic forms

    Alexey Andreevich Panov. Mixed discriminants connected with positive semidefinite quadratic forms. In Doklady Akademii Nauk , volume 282, pages 273--276. Russian Academy of Sciences, 1985

    1985

  39. [39]

    Inversion of matrices over a commutative semiring

    Christophe Reutenauer and Howard Straubing. Inversion of matrices over a commutative semiring. Journal of algebra , 88(2):350--360, 1984

    1984

  40. [40]

    A survey of lower bounds in arithmetic circuit complexity

    Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey , 95, 2015. version 9.0.3

    2015

  41. [41]

    A lower bound on the number of additions in monotone computations

    Claus-Peter Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science , 2(3):305--315, 1976

    1976

  42. [42]

    Sampling of partially distinguishable bosons and the relation to the multidimensional permanent

    Malte C Tichy. Sampling of partially distinguishable bosons and the relation to the multidimensional permanent. Physical Review A , 91(2):022316, 2015

    2015

  43. [43]

    Classes of arithmetic circuits capturing the complexity of computing the determinant

    Seinosuke Toda. Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Information and Systems , 75(1):116--124, 1992

    1992

  44. [44]

    On the complexity of proof in propositional calculus

    Grigori S Tseitin. On the complexity of proof in propositional calculus. In Studies in Constructive Mathematics and Mathematical Logic, Part II , volume 8 of Zap. Nauchn. Sem. LOMI , pages 234--259. Nauka, Leningrad, 1968. Leningrad. Otdel

    1968

  45. [45]

    On the complexity of derivation in propositional calculus

    Grigori S Tseitin. On the complexity of derivation in propositional calculus. In Automation of reasoning: 2: Classical papers on computational logic 1967--1970 , pages 466--483. Springer, 1983

    1967

  46. [46]

    Completeness classes in algebra

    Leslie Valiant. Completeness classes in algebra. In Proceedings of the ACM Symposium on Theory of Computing , pages 249--261, 1979

    1979

  47. [47]

    Reducibility by algebraic projections

    Leslie Valiant. Reducibility by algebraic projections. L'Enseignement Math\'ematique , (28):253--268, 1982

    1982

  48. [48]

    L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing , 12(4):641--644, 1983

    1983

  49. [49]

    Generalized semialgebras over semirings

    Hanns Joachim Weinert. Generalized semialgebras over semirings. In Semigroups Theory and Applications: Proceedings of a Conference held in Oberwolfach, Feb. 23--Mar. 1, 1986 , pages 380--416. Springer, 1986

    1986

  50. [50]

    Separating monotone V P and V N P

    Amir Yehudayoff. Separating monotone V P and V N P . In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 425--429, 2019

    2019