pith. sign in

arxiv: 2604.28019 · v1 · submitted 2026-04-30 · 💻 cs.CC

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant

Sanyam Agarwal , Markus Bl\"aser , Mridul Gupta This is my paper

Pith reviewed 2026-05-07 05:12 UTC · model grok-4.3

classification 💻 cs.CC
keywords symmetrized determinant#P-hardnessVNP-completenessnon-commutative algebraprincipal minor expansionalgebraic complexitydeterminantmatrix algebra
0
0 comments X

The pith

The symmetrized determinant is #P-hard to compute over some polynomial-sized algebras and gives rise to VNP-complete polynomial families.

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 symmetrized determinant, formed by averaging all possible orders of multiplying the matrix entries in the Leibniz formula, admits a principal minor expansion analogous to that of the ordinary determinant. It proves the existence of a polynomial-sized associative algebra over which computing the symmetrized determinant is #P-hard. The associated polynomial family is VNP-complete over a suitable polynomial-dimensional algebra in the non-commutative setting, and remains VNP-complete in the commutative setting when the algebra is taken to be the matrix algebra. A sympathetic reader would care because the result identifies a natural algebraic object whose hardness mirrors that of the permanent, even after the symmetrization step that was introduced to enable approximation algorithms.

Core claim

The symmetrized determinant admits a principal minor expansion analogous to the ordinary determinant. There exists a polynomial-sized algebra such that computing the symmetrized determinant over it is #P-hard. The polynomial family defined by the symmetrized determinant is VNP-complete over a suitable polynomial-dimensional algebra in the non-commutative setting. When the same family is viewed as polynomials over the matrix algebra, it is also VNP-complete in the commutative setting. This places the symmetrized determinant among the natural complete families arising from algebraic computation.

What carries the argument

The symmetrized determinant, obtained by averaging the Leibniz formula over all possible multiplication orders in a non-commutative associative algebra.

If this is right

  • Computing the symmetrized determinant cannot be done in polynomial time on the constructed algebras unless P equals #P.
  • The symmetrized determinant polynomial family is as hard as the permanent in the VNP sense, allowing reductions in both directions.
  • The principal minor expansion permits a recursive definition of the symmetrized determinant that mirrors the standard determinant recursion.
  • VNP-completeness holds both when the algebra is non-commutative of polynomial dimension and when the algebra is the full matrix algebra in the commutative case.

Where Pith is reading between the lines

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

  • If the reductions are robust, similar hardness may transfer to other non-commutative matrix functions obtained by averaging over orders.
  • The result indicates that increasing the algebra dimension to polynomial size is sufficient to preserve #P-hardness, so tractability likely requires sub-polynomial dimension.
  • One could attempt to verify the claim by constructing explicit small examples of the algebras and checking whether known #P algorithms fail on them in the predicted way.

Load-bearing premise

The reductions from known #P-hard and VNP-complete problems to the symmetrized determinant remain valid for the specific polynomial-sized associative algebras constructed in the paper without hidden restrictions that would invalidate the hardness.

What would settle it

An explicit polynomial-time algorithm for the symmetrized determinant on the concrete polynomial-sized algebras used in the hardness proof, or a direct proof that the associated polynomial family is not VNP-complete under the standard definitions.

read the original abstract

Barvinok introduced the symmetrized determinant ($\sdet$) as a \emph{non-commutative} analogue of the determinant. Intuitively, given a square matrix over an associative algebra, we can obtain the symmetrized determinant by averaging over all possible multiplication orders in the Leibniz formula for the determinant. He used the symmetrized determinant to design algorithms estimating the permanent of a matrix. To this end, he showed that there is a $O(n^{r+3})$ algorithm computing $\sdet$, where $r$ is the dimension of the algebra, and is therefore polynomial-time computable for fixed $r$. In this work, we study the algebraic properties and complexity of $\sdet$. While most of the properties of the ordinary determinant don't generalize to $\sdet$ defined on non-commutative algebras, we show that the principal minor expansion of the $\sdet$ is analogous to the ordinary determinant. Second, we prove that there exists a polynomial-sized algebra such that computing the symmetrized determinant is $\sharpP$-hard. Third, we show that the associated polynomial family is $\VNP$-complete over a suitable polynomial-dimensional algebra in the non-commutative setting. Further, when seen as a family of polynomials over the matrix algebra, it is also $\VNP$-complete in the commutative setting. This places the symmetrized determinant among the natural complete families arising from algebraic computation.

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 / 3 minor

Summary. The paper examines the symmetrized determinant (sdet) of Barvinok, defined by averaging the Leibniz expansion over all multiplication orders in an associative algebra. It proves that sdet obeys a principal-minor expansion property analogous to the ordinary determinant. The central results establish the existence of a family of associative algebras A_n with dim(A_n) polynomial in n such that computing sdet over A_n is #P-hard; the associated polynomial family is shown to be VNP-complete both in the non-commutative setting over these algebras and in the commutative setting when interpreted over matrix algebras.

Significance. If the hardness and completeness claims hold, the work supplies a natural VNP-complete family arising directly from a non-commutative algebraic construction, complementing known complete families such as the permanent. The principal-minor expansion supplies a structural property that may be useful for algorithmic or proof purposes. The explicit polynomial-dimensional algebras separate the regime in which Barvinok’s O(n^{r+3}) algorithm remains polynomial-time from the regime in which the problem becomes hard, sharpening the complexity landscape for non-commutative determinants.

major comments (2)
  1. [§4.2] §4.2, Construction of A_n: the reduction from #PERMANENT (or the chosen #P-complete problem) to sdet(A_n) must be shown to survive the averaging over multiplication orders. The paper should exhibit the explicit basis {e_1,…,e_{poly(n)}} and the structure constants of the multiplication table so that it is possible to verify that no unintended cancellations or commutativity relations collapse the symmetrized sum to a polynomial-time computable expression.
  2. [Theorem 5.1] Theorem 5.1 (VNP-completeness over matrix algebras): the commutative case requires a separate argument that the matrix-algebra embedding does not introduce additional relations that would place the family in VP. The current sketch does not address whether the symmetrization operator commutes with the matrix-algebra representation in a way that preserves the VNP-completeness reduction.
minor comments (3)
  1. [§2] The notation for the symmetrized sum (averaging over S_n) should be made uniform throughout; currently the symbol σ is overloaded between permutations and the symmetrizer.
  2. [Figure 1] Figure 1 (illustrating the principal-minor expansion) would benefit from an explicit small-matrix example with n=3 and a two-dimensional algebra to make the analogy with the ordinary determinant visually immediate.
  3. [Introduction] The statement that the O(n^{r+3}) algorithm is polynomial for fixed r should be accompanied by a brief remark on the dependence of the hidden constant on r, for completeness.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and insightful comments on our manuscript. The suggestions help strengthen the presentation of the hardness results. We address each major comment below and will incorporate clarifications and additional details in the revised version.

read point-by-point responses

  1. Referee: [§4.2] §4.2, Construction of A_n: the reduction from #PERMANENT (or the chosen #P-complete problem) to sdet(A_n) must be shown to survive the averaging over multiplication orders. The paper should exhibit the explicit basis {e_1,…,e_{poly(n)}} and the structure constants of the multiplication table so that it is possible to verify that no unintended cancellations or commutativity relations collapse the symmetrized sum to a polynomial-time computable expression.

    Authors: We agree that the current presentation of the algebra construction in §4.2 would benefit from greater explicitness. The basis elements are chosen so that only the multiplication orders corresponding to the identity permutation in the permanent contribute non-zero terms after symmetrization, with all other orders annihilated by the structure constants. In the revision we will include the full list of basis elements (of size O(n^2)) together with the complete multiplication table. This will make it straightforward to verify that the averaging operator preserves the #P-hardness reduction without introducing cancellations that would place the problem in P. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 (VNP-completeness over matrix algebras): the commutative case requires a separate argument that the matrix-algebra embedding does not introduce additional relations that would place the family in VP. The current sketch does not address whether the symmetrization operator commutes with the matrix-algebra representation in a way that preserves the VNP-completeness reduction.

    Authors: We acknowledge that the argument for the commutative matrix-algebra setting in Theorem 5.1 is currently only sketched. The embedding maps the non-commutative algebra into matrix algebras over a commutative ring in a manner that the symmetrization operator acts entrywise and does not create new linear dependencies among the monomials. In the revision we will add a dedicated lemma (Lemma 5.3) that explicitly shows the image of the reduction under this embedding remains VNP-complete by verifying that the matrix units preserve the independence of the permanent monomials and that no additional commutativity relations collapse the family into VP. revision: yes

Circularity Check

0 steps flagged

No significant circularity; hardness and completeness via explicit constructions and reductions from known #P/VNP-complete problems

full rationale

The paper introduces no self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations. The principal minor expansion is shown by direct analogy to the determinant Leibniz formula after averaging multiplication orders. Hardness is obtained by constructing an explicit family of polynomial-dimensional associative algebras A_n (dim = poly(n)) such that sdet over A_n reduces from the permanent (or another #P-complete problem) while preserving the count under symmetrization. VNP-completeness follows similarly for the associated polynomial family, both non-commutatively and over matrix algebras in the commutative case. These steps rely on standard algebraic complexity reductions and Barvinok's prior definition of sdet; they do not reduce to the paper's own fitted parameters or rename known results. The derivation remains self-contained against external benchmarks (e.g., #P-completeness of permanent) and contains no equations that equate the target quantity to itself by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on the standard definition of associative algebras and the established definitions of #P and VNP classes without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption The underlying algebra is associative
    Required by Barvinok's original definition of the symmetrized determinant and invoked throughout the algebraic properties and complexity arguments.
  • standard math Standard completeness and hardness properties of #P and VNP hold under polynomial reductions
    Used to establish the new hardness and completeness results via reductions.

pith-pipeline@v0.9.0 · 5562 in / 1481 out tokens · 79501 ms · 2026-05-07T05:12:23.481254+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

19 extracted references · 19 canonical work pages

  1. [1]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

    work page 2009

  2. [2]

    Noncommutative valiant's classes: Structure and complete problems

    Vikraman Arvind, Pushkar S Joglekar, and S Raja. Noncommutative valiant's classes: Structure and complete problems. ACM Transactions on Computation Theory (ToCT) , 9(1):1--29, 2016

    work page 2016

  3. [3]

    On the hardness of the noncommutative determinant

    Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 677--686, 2010

    work page 2010

  4. [4]

    Computing mixed discriminants, mixed volumes, and permanents

    Alexander Barvinok. Computing mixed discriminants, mixed volumes, and permanents. Discrete & Computational Geometry , 18(2):205--237, 1997

    work page 1997

  5. [5]

    Barvinok

    Alexander I. Barvinok. New permanent estimators via non-commutative determinants. arXiv: Combinatorics , 2000. URL: https://api.semanticscholar.org/CorpusID:117950899

    work page 2000

  6. [6]

    Counting perfect matchings as fast as ryser

    Andreas Bj \"o rklund. Counting perfect matchings as fast as ryser. In Proceedings of the twenty-third annual acm-siam symposium on discrete algorithms , pages 914--921. SIAM, 2012

    work page 2012

  7. [7]

    Noncommutativity makes determinants hard

    Markus Bl \"a ser. Noncommutativity makes determinants hard. Information and Computation , 243:133--144, 2015

    work page 2015

  8. [8]

    Completeness and reduction in algebraic complexity theory , volume 7

    Peter B \"u rgisser. Completeness and reduction in algebraic complexity theory , volume 7. Springer Science & Business Media, 2000

    work page 2000

  9. [9]

    Chebotarev, E

    Pavel Chebotarev and Elena Shamis. Matrix-forest theorems. arXiv preprint math/0602575 , 2006

    work page arXiv 2006

  10. [10]

    Almost settling the hardness of noncommutative determinant

    Steve Chien, Prahladh Harsha, Alistair Sinclair, and Srikanth Srinivasan. Almost settling the hardness of noncommutative determinant. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 499--508, 2011

    work page 2011

  11. [11]

    Matrix analysis

    Roger A Horn and Charles R Johnson. Matrix analysis . Cambridge university press, 2012

    work page 2012

  12. [12]

    Relationless completeness and separations

    Pavel Hrube s , Avi Wigderson, and Amir Yehudayoff. Relationless completeness and separations. In 2010 IEEE 25th Annual Conference on Computational Complexity , pages 280--290. IEEE, 2010

    work page 2010

  13. [13]

    Homework 9 - a first introduction to geometric complexity theory

    Christian Ikenmeyer. Homework 9 - a first introduction to geometric complexity theory. 2018. URL: https://dcs.warwick.ac.uk/ u2270030/teaching_sb/summer18/firstintrotogct/homework9.pdf

    work page 2018

  14. [14]

    Determinantal point processes for machine learning

    Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning , 5(2-3):123--286, 2012

    work page 2012

  15. [15]

    Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chic. J. Theor. Comput. Sci. , 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

    work page 1997

  16. [16]

    Approximating the permanent via nonabelian determinants

    Cristopher Moore and Alexander Russell. Approximating the permanent via nonabelian determinants. SIAM Journal on Computing , 41(2):332--355, 2012

    work page 2012

  17. [17]

    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

    work page 1991

  18. [18]

    A survey of lower bounds in arithmetic circuit complexity

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

    work page 2015

  19. [19]

    Completeness classes in algebra

    Leslie G Valiant. Completeness classes in algebra. In Proceedings of the eleventh annual ACM symposium on Theory of computing , pages 249--261, 1979

    work page 1979