Pith. sign in

REVIEW 4 major objections 3 minor 91 references

Quantum determinants can be computed by small algebraic branching programs.

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 · deepseek-v4-flash

2026-08-02 05:56 UTC pith:D4GSGAZW

load-bearing objection Multiparameter q extension is unproven as written; the RQ and one-parameter q cases look correct and are the real contribution. the 4 major comments →

arxiv 2607.13186 v1 pith:D4GSGAZW submitted 2026-07-14 math.QA cs.DMcs.DSmath.CO

Quantum determinants in polynomial time

Igor Pak , Daniel Soskin This is my paper
classification math.QA cs.DMcs.DSmath.CO MSC 15A1516T2068Q2505A05
keywords quantum determinantright-quantum matricesCayley determinantMoore determinantValiant determinantalgebraic branching programnoncommutative permanentclow sequences
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 aims to show that the Cayley determinant of a right-quantum (RQ) matrix—a noncommutative determinant whose entries obey quantum-group relations—can be computed by an algebraic branching program of polynomial (cubic) size, over the rationals and for every nonzero multiplicative parameter q. This is surprising because for the free noncommutative algebra the same polynomial requires exponential-size branching programs. The proof establishes a three-way equality between the Cayley, Moore, and Valiant determinants for q-RQ matrices, then adapts a standard dynamic-programming construction for the commutative determinant to compute the Valiant form. At q = -1 it yields an exact polynomial-time algorithm for the noncommutative permanent of antisymmetric right-quantum matrices—an unusual exact permanent computation.

Core claim

The central discovery is Theorem 4.1: for any q-RQ matrix, the column-ordered Cayley determinant, the cycle-ordered Moore determinant, and the closed-walk (clow) Valiant determinant coincide as elements of the q-RQ algebra. This is not true in the free algebra; the equality exploits the commutation and two-by-two minor relations. Theorem 1.1 then follows by combining the equality with a polynomial-size branching program that evaluates the Valiant determinant directly from its clow-sequence definition, with the q-weights factored through a factorization lemma. Consequently, exact determinant and, at q = -1, exact permanent evaluation become tractable for these quantum matrix algebras.

What carries the argument

The load-bearing objects are three noncommutative determinant forms: the Cayley determinant (sum over permutations in column order), the Moore determinant (sum over cycle decompositions), and the Valiant determinant (sum over all closed-walk 'clow' sequences). The argument uses two bijective/combinatorial transformations—a rank-increasing swap map on balanced words for the Cayley–Moore equality, and a type-by-type cancellation of non-cycle-decomposition clow sequences for the Moore–Valiant equality—together with a factorization lemma that reduces q-weights of clow sequences to products over single clows. The most delicate part is the type-3 cancellation, which pairs leftover terms with cycle

Load-bearing premise

The proof leans on the claim that the 'type-3' leftover clow sequences admit a sign-reversing bijection that matches their q-weights exactly with cycle decompositions of a q-RQ matrix with two equal columns, whose determinant is known to vanish.

What would settle it

For n = 3 with generic parameters q12, q13, q23, write out the six type-3 clow sequences on {1,2,2,3}, compute their q-weighted signed sum T3 as in the paper's Example 8.19, and simplify using the q-RQ relations; if a single monomial in the entries survives, the collective cancellation fails. Alternatively, evaluate Cdet_q and Vdet_q on an explicit 4x4 q-RQ matrix with noncommuting entries and compare the two polynomials.

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

If this is right

  • Polynomial-time computation of Cayley determinants of RQ matrices is achieved, giving the first positive complexity result for quantum-matrix determinants.
  • At q = -1, the same ABP computes the noncommutative permanent of antisymmetric right-quantum matrices exactly in polynomial time.
  • The result extends to the multiparameter q-deformation, covering q-CF and q-RQ matrices uniformly.
  • The construction is division-free and of size O(n^3), so the algorithm is explicit and uniform over all nonzero parameter choices.
  • The equality Cdet = Mdet = Vdet isolates a structural property of RQ algebras that may hold for other R-matrix deformations.

Where Pith is reading between the lines

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

  • If the type-3 cancellation can be formalized as a genuine weight-matching involution rather than a many-to-many correspondence, the same proof scheme might extend to generalized R-matrix algebras, a direction the authors suggest for Belavin–Drinfeld structures.
  • The exact permanent result at q = -1 is a natural stress test: implementing the ABP for small antisymmetric matrices and comparing its output with direct summation for n = 4 would expose any residual mismatch in the collective cancellation.
  • A concrete extension would be to replace the sign character in Cdet_q by other characters to obtain quantum immanants; the Cayley–Moore swap step would likely still work, but the Moore–Valiant cancellation would probably require new arguments.

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

4 major / 3 minor

Summary. The paper claims a polynomial-size algebraic branching program (ABP) computing the q-Cayley determinant of q-right-quantum (q-RQ) matrices, including a multiparameter deformation, and hence, at q=-1, an exact polynomial-time ABP for the Cayley permanent of antisymmetric right-quantum matrices. The proof strategy is to prove Theorem 4.1, the equality Cdet_q(A)=Mdet_q(A)=Vdet_q(A) for q-RQ matrices, and then to compute the Valiant determinant by an explicit dynamic-programming ABP modeled on Mahajan–Vinay. The paper proves the Cartier–Foata case cleanly, gives an explicit O(n^3) ABP for the Valiant determinant in the free algebra, and then attempts to transfer the RQ/q-RQ equality through type-1, type-2, and type-3 collective cancellations of clow sequences.

Significance. If the main theorem is correct, it is a striking positive result: a noncommutative determinant of quantum-matrix type computable by a polynomial-size ABP, despite Nisan-type lower bounds for the free algebra, and an unusual exact permanent computation at q=-1. The Dynamic Programming Lemma 4.4 is explicit and appears sound, and the Cartier–Foata section gives a clean weight-preserving argument. There are no fitted parameters and no circular reliance on the main equality: the paper builds on the published parameter-free bijective result [KP07] for the CF/q-CF part, which is legitimate. However, the transfer of the RQ cancellation argument to the multiparameter q-RQ setting contains load-bearing gaps, and one step used repeatedly is false as stated. The full claim of Theorem 1.1 is therefore not established by the present proof.

major comments (4)
  1. [§9.6, Lemma 9.6 and Eq. (3.2)] The auxiliary matrix Q, obtained by replacing the first column of A by the k-th column, is not generally q-RQ for multiparameter q. The assertion that this is true because the columns of Q form a subcollection of columns of A ignores that the q_{ij} parameters in (3.2) depend on the column positions of Q, not on the original column labels. Concretely, take n=3, k=2, q_{12}=u, q_{13}=v, q_{23}=w with v≠w. Comparing the defining relation (3.2) for Q (with k=2, ℓ=3, i=1, j=3) with the corresponding relation for A yields (w-v)(a_{22}a_{33}-w a_{32}a_{23})=0 in B^q_n. No relation in the q-RQ ideal forces a_{22}a_{33}=w a_{32}a_{23} for generic A; at q=1 this would assert a commutativity that is not present. Thus Q∉B^q_n in general. Consequently the applications of Theorem 9.1 and Lemma 3.1 to Q in Lemma 9.6 are unjustified, and the type-3 collective cancellation, and hence Vdet_q=Mdet_q, is n
  2. [§9.1, proof of Theorem 9.1] The proof asserts that when a swap a_{ℓ j} a_{k i} is replaced by a_{k i} a_{ℓ j}, relations (3.2) give a_{ℓ j} a_{k i}=c a_{k i} a_{ℓ j} with one of the three scalar factors c. This is false in the q-RQ algebra for k≠ℓ: the second relation in (3.2) is a four-term identity, not a monomial equality. The q=1 RQ proof of Lemma 8.1 correctly uses a pairwise cancellation involving two partner q-sequences and the full four-term relation; the q-RQ proof as written instead treats the relation as a single-term swap. Therefore the claimed sign-preserving, weight-preserving involution Ψ is not established, and Cdet_q=Mdet_q in Lemma 4.2 needs a genuinely pairwise argument through (3.2).
  3. [§8.4, Remark 8.13, applied in §9.2] The reduction of the support to an interval {1,...,k,k,...,n} by relabelling larger elements is not an invariant operation for multiparameter q. The q-weights (3.10) contain products of q_{ij} attached to the actual labels, and a relabelling of support elements changes those scalars unless the parameter array is transformed as well. No such transformation is supplied. This WLOG reduction is used throughout the type-3 proof, including Lemma 9.6's normalization to head h=1, so the collective cancellation argument is not valid for generic multiparameter arrays as written.
  4. [§9.6, proof of Lemma 9.6] Independently of the Q∈B^q_n problem, the asserted sign-reversing, weight-matching bijection between type-3 q-clow sequences and cycle decompositions of Q is not proved. The text says the q-weights match 'as in the proof of Lemma 7.4', but Lemma 7.4 is a Cartier–Foata statement; in the q-RQ setting the bijection must track the q-inversion factors (7.1) across the deletion of the repeated vertex k. Because the q parameters for Q differ from those of the original clow-word positions, this matching is exactly where the multiparameter issue is most delicate, and the manuscript provides no calculation.
minor comments (3)
  1. [§5 and §6] Typos: 'we proof that' should be 'we prove that'; the same verb form appears in a few places. This is purely editorial.
  2. [§9.2] Lemma 9.3 is proved before Lemma 9.6 is stated but invokes it for smaller support size. A forward reference or a reorganization of the induction would improve readability.
  3. [Theorem 1.1] The statement says 'polynomial time' while the ABP has coefficients involving the arbitrary nonzero complex numbers q_{ij}; the intended field/model of computation (e.g., algebraic computation over Q when q_{ij}∈Q) should be stated explicitly.

Circularity Check

0 steps flagged

No significant circularity: the central determinantal equality is established by explicit combinatorial arguments, and the ABP is a direct construction; only minor self-citations appear and they are not load-bearing.

full rationale

The paper's main claim is Theorem 1.1, which follows from Theorem 4.1: Cdet_q = Mdet_q = Vdet_q for q-RQ matrices. The Cdet_q = Mdet_q direction is proved by a many-to-many bijection generalizing the Konvalinka-Pak approach, not by assuming the equality; the proof tracks q-weights under adjacent swaps and uses the defining relations (3.2). The Mdet_q = Vdet_q direction is proved by a collective cancellation of non-cycle clow sequences grouped into types; the type-3 cancellation reduces the signed sum to Cdet_q(Q)=0 via Lemma 3.1. That lemma is a known algebraic property cited to several sources, including [KP07] by one of the present authors, but also to independent non-overlapping papers (CFR09, CFRS14, FH07a, GLZ06, Sil21), and it is not the same statement as the theorem being proved. No fitted parameter is renamed as a prediction: Lemma 4.4 is an explicit dynamic-programming construction of an ABP that computes Vdet_q directly from its clow-sequence definition, and Theorem 4.1 then transfers that computation to Cdet_q. There is no imported uniqueness theorem, no ansatz smuggled through a citation, and no known result merely renamed. The self-citations to [KP07] are used as a bijective technique and for the equal-column vanishing lemma; they are real, published, parameter-free results and are not the sole load-bearing support. Thus the derivation chain does not reduce to its own inputs by construction. A separate correctness concern exists in Lemma 9.6, where the auxiliary matrix Q may not inherit the q-RQ relations in the multiparameter case; that is a potential proof gap, not a circularity of the kind scored here.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No numbers are fitted; the q_{ij} are symbolic parameters of the algebra. The load-bearing inputs pulled from outside the paper are the quantum-matrix relations, the equal-column vanishing lemma, and the KP07 bijection.

axioms (4)
  • domain assumption q-RQ algebra relations (3.2) (with specializations q=1, q=-1) define the matrix model; the second relation is the 2x2 minor/column identity.
    The paper's entire setting and all cancellations rely on these quadratic relations holding in the algebra B^q_n (Section 3.2).
  • standard math Lemma 3.1: Cdet_q(A)=0 for q-RQ matrices with two equal columns.
    Invoked to zero out residual type-3 terms in Lemmas 8.18 and 9.6; the paper cites [CFR09], [CFRS14], [FH07a], [GLZ06], [KP07], [Sil21] and omits the proof.
  • domain assumption Konvalinka-Pak bijection: Cdet=Mdet for RQ matrices (Lemma 8.1).
    The paper's proof of Lemma 8.1 sketches the [KP07] map Psi; Theorem 9.1 extends it to q-RQ by tracking q-weights, so the prior theorem is load-bearing.
  • standard math Mahajan-Vinay clow-sequence framework for determinant ABP (MV97/Rote01).
    The clow/partial-clow recursion in Section 6 is a q-deformation of the MV97 construction; the paper re-proves it as Lemma 4.4 but relies on the standard framing.

pith-pipeline@v1.3.0-alltime-deepseek · 28458 in / 21818 out tokens · 192913 ms · 2026-08-02T05:56:40.373687+00:00 · methodology

0 comments
read the original abstract

We give an algebraic branching program of polynomial size which computes Cayley determinant of right quantum matrices. This is a rare example of an efficient computation of a noncommutative determinant, and the first such example for quantum groups. We extend the results to the $q$-Cayley determinant of $q$-right quantum matrices, as well as to their multiparameter generalization. The proofs are entirely combinatorial, as we relate Cayley, Moore and Valiant determinants using bijections/involutions on words. We then employ the celebrated determinant construction of Mahajan and Vinay (SODA'97), to obtain the results.

Figures

Figures reproduced from arXiv: 2607.13186 by Daniel Soskin, Igor Pak.

Figure 8
Figure 8. Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p015_8.png] view at source ↗
Figure 8
Figure 8. Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p016_8.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

91 extracted references · 5 linked inside Pith

  1. [1]

    Scott Aaronson, ? = , in Open problems in mathematics, Springer, Cham, 2016, 1--122

    2016

  2. [2]

    Abeles, Nineteenth century roots of quasideterminants, Linear Algebra Appl

    Francine F. Abeles, Nineteenth century roots of quasideterminants, Linear Algebra Appl. 435 (2011), 1019--1024

    2011

  3. [3]

    Sanyam Agarwal, Markus Bl\"aser and Mridul Gupta, On the principal minor expansion and complexity of the symmetrized determinant, preprint (2026), 18 pp.; arXiv:2604.28019

    Pith/arXiv arXiv 2026

  4. [4]

    Vikraman Arvind and Srikanth Srinivasan, On the hardness of the noncommutative determinant, Comput.\ Complexity 27 (2018), 1--29; extended abstract in Proc.\ 42nd STOC (2010), 677--686

    2018

  5. [5]

    3, 57--65

    Helmer Aslaksen, Quaternionic determinants, Math.\ Intelligencer 18 (1996), no. 3, 57--65

    1996

  6. [6]

    Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC ^1 , J

    David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC ^1 , J. Comput.\ System Sci. 38 (1989), 150--164; extended abstract in Proc.\ 18th STOC (1986), 1--5

    1989

  7. [7]

    Berezin, Introduction to superanalysis, Reidel, Dordrecht, 1987, 424 pp

    Felix A. Berezin, Introduction to superanalysis, Reidel, Dordrecht, 1987, 424 pp

    1987

  8. [8]

    Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures Algorithms 14 (1999), 29--61

    1999

  9. [9]

    Alexander Barvinok, New permanent estimators via non-commutative determinants, preprint (2000), 13 pp.; arXiv:math/0007153

    Pith/arXiv arXiv 2000

  10. [10]

    Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform

    Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett. 18 (1984), 147--150

    1984

  11. [11]

    Bird, A simple division-free algorithm for computing determinants, Inform.\ Process.\ Lett

    Richard S. Bird, A simple division-free algorithm for computing determinants, Inform.\ Process.\ Lett. 111 (2011), 1072--1074

    2011

  12. [12]

    243 (2015), 133--144; extended abstract in Proc.\ 40th ICALP (2013), 172--183

    Markus Bl\"aser, Noncommutativity makes determinants hard, Inform.\ and Comput. 243 (2015), 133--144; extended abstract in Proc.\ 40th ICALP (2013), 172--183

    2015

  13. [13]

    Mulmuley and Milind Sohoni, Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem, Mem.\ AMS 235 (2015), no

    Jonah Blasiak, Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem, Mem.\ AMS 235 (2015), no. 1109, 160 pp

    2015

  14. [14]

    and Control 52 (1982), 241--256; extended abstract in Proc.\ 23rd FOCS (1982), 65--71

    Allan Borodin, Joachim von zur Gathen and John Hopcroft, Fast parallel matrix and GCD computations, Inform. and Control 52 (1982), 241--256; extended abstract in Proc.\ 23rd FOCS (1982), 65--71

    1982

  15. [15]

    Brown and Ken R

    Ken A. Brown and Ken R. Goodearl, Lectures on algebraic quantum groups, Birkh\"auser, Basel, 2002, 348 pp

    2002

  16. [16]

    Peter B\"urgisser, Completeness and reduction in algebraic complexity theory, Springer, Berlin, 2000, 168 pp

    2000

  17. [17]

    Peter B\"urgisser, Completeness classes in algebraic complexity theory, to appear in Foundations of Computation and Machine Learning: The Work of Leslie Valiant, ACM, 2026; arXiv:2406.06217

    Pith/arXiv arXiv 2026

  18. [18]

    Sokal and Andrea Sportiello, Noncommutative determinants, Cauchy--Binet formulae, and Capelli-type identities I

    Sergio Caracciolo, Alan D. Sokal and Andrea Sportiello, Noncommutative determinants, Cauchy--Binet formulae, and Capelli-type identities I. Generalizations of the Capelli and Turnbull identities, Electron.\ J.\ Combin. 16 (2009), no. 1, RP 103, 43 pp

    2009

  19. [19]

    85, Springer, Berlin, 1969, 88 pp.; available at tinyurl.com/4zv2x3pt http://www.mat.univie.ac.at/\ \/slc/books/cartfoa.html

    Pierre Cartier and Dominique Foata, Probl\` e mes combinatoires de commutation et r\' e arrangements , Lecture Notes in Mathematics, No. 85, Springer, Berlin, 1969, 88 pp.; available at tinyurl.com/4zv2x3pt http://www.mat.univie.ac.at/\ \/slc/books/cartfoa.html

    1969

  20. [20]

    26 (1845), 141--145

    Arthur Cayley, On certain results relating to quaternions, Philos.\ Mag. 26 (1845), 141--145

  21. [21]

    Alexander Chervov and Gregorio Falqui, Manin matrices and Talalaev's formula, J. Phys. A 41 (2008), no. 19, 194006, 28 pp

    2008

  22. [22]

    43 (2009), 239--315

    Alexander Chervov, Gregorio Falqui and Vladimir Rubtsov, Algebraic properties of Manin matrices I, Adv.\ Appl.\ Math. 43 (2009), 239--315

    2009

  23. [23]

    60 (2014), 25--89

    Alexander Chervov, Gregorio Falqui, Vladimir Rubtsov and Alexey Silantyev, Algebraic properties of Manin matrices II: q -analogues and integrable systems, Adv.\ Appl.\ Math. 60 (2014), 25--89

    2014

  24. [24]

    Rasmussen and Alistair Sinclair, Clifford algebras and approximating the permanent, J

    Steve Chien, Lars E. Rasmussen and Alistair Sinclair, Clifford algebras and approximating the permanent, J. Comput.\ System Sci. 67 (2003), 263--290; extended abstract in Proc.\ 34th STOC (2002), 222--231

    2003

  25. [25]

    37 (2007), 252--266; extended abstract in Proc.\ 45th FOCS (2004), 352--361

    Steve Chien and Alistair Sinclair, Algebras with polynomial identities and computing the determinant, SIAM J.\ Comput. 37 (2007), 252--266; extended abstract in Proc.\ 45th FOCS (2004), 352--361

    2007

  26. [26]

    Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan, Almost settling the hardness of noncommutative determinant, in Proc.\ 43rd STOC (2011), 499--508

    2011

  27. [27]

    Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, in Proc.\ 5th FCT (1985), 63--69

    Alexander L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, in Proc.\ 5th FCT (1985), 63--69

    1985

  28. [28]

    Radu Curticapean, A full complexity dichotomy for immanant families, in Proc.\ 53rd STOC (2021), 1770--1783

    2021

  29. [29]

    Jean Dieudonn\'e, Les d\'eterminants sur un corps non commutatif (in French), Bull.\ SMF 71 (1943), 27--45

    1943

  30. [30]

    Frenkel, Isomorphism of two realizations of quantum affine algebra U_q( gl (n)) , Comm.\ Math.\ Phys

    Jin Tai Ding and Igor B. Frenkel, Isomorphism of two realizations of quantum affine algebra U_q( gl (n)) , Comm.\ Math.\ Phys. 156 (1993), 277--300

    1993

  31. [31]

    Draxl, Skew fields, Cambridge Univ.\ Press, Cambridge, 1983, 182 pp

    Peter K. Draxl, Skew fields, Cambridge Univ.\ Press, Cambridge, 1983, 182 pp

    1983

  32. [32]

    B 71B (1967), 241--245

    Jack Edmonds, Systems of distinct representatives and linear algebra, J.\ Res.\ Nat.\ Bur.\ Standards, Sect. B 71B (1967), 241--245

    1967

  33. [33]

    Pavel Etingof, Travis Schedler and Olivier Schiffmann, Explicit quantization of dynamical r -matrices for finite dimensional semisimple Lie algebras, Jour.\ AMS 13 (2000), 595--609

    2000

  34. [34]

    3 (1999), 345--351

    Pavel Etingof and Vladimir Retakh, Quantum determinants and quasideterminants, Asian J.\ Math. 3 (1999), 345--351

    1999

  35. [35]

    Faddeev, Nikolai Yu

    Lyudvig D. Faddeev, Nikolai Yu. Reshetikhin and Leon A. Takhtajan, Quantization of Lie groups and Lie algebras, in Algebraic analysis, Vol. I, Academic Press, Boston, MA, 1988, 129--139

    1988

  36. [36]

    Dominique Foata, \' E tude alg\' e brique de certains probl\` e mes d'analyse combinatoire et du calcul des probabilit\' e s (in French), Publ.\ Inst.\ Statist.\ Univ.\ Paris 14 (1965), 81--241

    1965

  37. [37]

    Algebra 307 (2007), no

    Dominique Foata and Guo-Niu Han, A new proof of the Garoufalidis--L\^e--Zeilberger Quantum MacMahon Master Theorem, J. Algebra 307 (2007), no. 1, 424--431

    2007

  38. [38]

    423 (2007), no

    Dominique Foata and Guo-Niu Han, Specializations and extensions of the quantum MacMahon Master Theorem, Linear Algebra Appl. 423 (2007), no. 2--3, 445--455

    2007

  39. [39]

    27 (2008), 163--172

    Dominique Foata and Guo-Niu Han, A basis for the right quantum algebra and the `` 1=q '' principle, J.\ Algebraic Combin. 27 (2008), 163--172

    2008

  40. [40]

    20 (2020), 223--290; extended abstract in Proc.\ 57th FOCS (2016), 109--117

    Ankit Garg, Leonid Gurvits, Rafael Oliveira and Avi Wigderson, Operator scaling: theory and applications, Found.\ Comput.\ Math. 20 (2020), 223--290; extended abstract in Proc.\ 57th FOCS (2016), 109--117

    2020

  41. [41]

    Stavros Garoufalidis, Thang T. Q. L\^e and Doron Zeilberger, The quantum MacMahon Master Theorem, Proc.\ Natl.\ Acad.\ Sci.\ USA 103 (2006), no. 38, 13928--13931

    2006

  42. [42]

    Wilson, Quasideterminants, Adv.\ Math

    Israel Gelfand, Sergei Gelfand, Vladimir Retakh and Robert L. Wilson, Quasideterminants, Adv.\ Math. 193 (2005), 56--141

    2005

  43. [43]

    25 (1991), no

    Israel Gelfand and Vladimir Retakh, Determinants of matrices over noncommutative rings, Funct.\ Anal.\ Appl. 25 (1991), no. 2, 91--102

    1991

  44. [44]

    26 (1992), no

    Israel Gelfand and Vladimir Retakh, A theory of non-commutative determinants and characteristic functions of graphs, Funct.\ Anal.\ Appl. 26 (1992), no. 4, 1--20

    1992

  45. [45]

    Craig Gentry, Noncommutative determinant is hard: a simple proof using an extension of Barrington's theorem, in Proc.\ 29th CCC, 2014, 181--187

    2014

  46. [46]

    Victor Ginzburg and Shrawan Kumar, Cohomology of quantum groups at roots of unity, Duke Math. J. 69 (1993), 179--198

    1993

  47. [47]

    Godsil and Ivan Gutman, On the matching polynomial of a graph, in Algebraic methods in graph theory, North-Holland, Amsterdam, 1981, 241--249

    Christopher D. Godsil and Ivan Gutman, On the matching polynomial of a graph, in Algebraic methods in graph theory, North-Holland, Amsterdam, 1981, 241--249

    1981

  48. [48]

    Goulden and David M

    Ian P. Goulden and David M. Jackson, Combinatorial enumeration, John Wiley, New York, 1983, 569 pp

    1983

  49. [49]

    Goulden and David M

    Ian P. Goulden and David M. Jackson, Immanants of combinatorial matrices, J. Algebra 148 (1992), 305--324

    1992

  50. [50]

    Mustafa Hajij and Jesse Levitt, An efficient algorithm to compute the colored Jones polynomial, preprint (2018), 20 pp.; arXiv:1804.07910

    Pith/arXiv arXiv 2018

  51. [51]

    Ph\`ung H\^ o Hai and Martin Lorenz, Koszul algebras and the quantum MacMahon master theorem, Bull.\ LMS 39 (2007), 667--676

    2007

  52. [52]

    Hodges, Introduction to Belavin--Drinfeld quantum groups, in Recent advances in noncommutative algebra and geometry, AMS, Providence, RI, 2024, 111--124

    Timothy J. Hodges, Introduction to Belavin--Drinfeld quantum groups, in Recent advances in noncommutative algebra and geometry, AMS, Providence, RI, 2024, 111--124

    2024

  53. [53]

    11 (2015), 357--393; extended abstract in Proc.\ 5th ICTS (2014), 49--65

    Pavel Hrube s and Avi Wigderson, Non-commutative arithmetic circuits with division, Theory Comput. 11 (2015), 357--393; extended abstract in Proc.\ 5th ICTS (2014), 49--65

    2015

  54. [54]

    Pavel Hrube s , Avi Wigderson and Amir Yehudayoff, Non-commutative circuits and the sum-of-squares problem, Jour.\ AMS 24 (2011), 871--898; extended abstract in Proc.\ 42nd STOC (2010), 667--676

    2011

  55. [55]

    Shih-Han Hung and En-Jui Kuo The computational complexity of quantum determinants, preprint (2023), 36 pp.; arXiv:2302.08083

    Pith/arXiv arXiv 2023

  56. [56]

    Vu Huynh and Thang T. Q. L\^e, On the colored Jones polynomial and the Kashaev invariant, Jour.\ Math.\ Sci. 146 (2007), 5490--5504

    2007

  57. [57]

    Laurent Hyafil, The power of commutativity, in Proc.\ 18th FOCS, (1977), 171--174

    1977

  58. [58]

    Christian Ikenmeyer, On the gradient of the coefficient of the characteristic polynomial, preprint (2025), 30 pp.; arXiv:2511.04954

    arXiv 2025

  59. [59]

    ACM 51 (2004), 671--697; extended abstract in Proc.\ 33rd STOC (2001), 712--721

    Mark Jerrum, Alistair Sinclair and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004), 671--697; extended abstract in Proc.\ 33rd STOC (2001), 712--721

    2004

  60. [60]

    Naihuan Jing, Yinlong Liu and Jian Zhang, Quantum algebra of multiparameter Manin matrices, J.\ Algebra 655 (2024), 586--618

    2024

  61. [61]

    Vaughan F. R. Jones, Hecke algebra representations of braid groups and link polynomials, Annals of Math. 126 (1987), 335--388

    1987

  62. [62]

    Kalorkoti, A lower bound for the formula size of rational functions, SIAM J.\ Comput

    Kyriakos A. Kalorkoti, A lower bound for the formula size of rational functions, SIAM J.\ Comput. 14 (1985), 678--687

    1985

  63. [63]

    22 (1993), 284--293

    Narendra Karmarkar, Richard Karp, Richard Lipton, L\'aszl\'o Lov\'asz and Michael Luby, A Monte Carlo algorithm for estimating the permanent, SIAM J.\ Comput. 22 (1993), 284--293

    1993

  64. [64]

    Christian Kassel, Quantum groups, Springer, New York, 1995, 531 pp

    1995

  65. [65]

    16 (2012), 289--304

    Matja z Konvalinka, On quantum immanants and the cycle basis of the quantum permutation space, Ann.\ Comb. 16 (2012), 289--304

    2012

  66. [66]

    216 (2007), 29--61

    Matja z Konvalinka and Igor Pak, Non-commutative extensions of the MacMahon Master Theorem, Adv.\ Math. 216 (2007), 29--61

    2007

  67. [67]

    169 (1995), 1--23

    Daniel Krob and Bernard Leclerc, Minor identities for quasi-determinants and quantum determinants, Comm.\ Math.\ Phys. 169 (1995), 1--23

    1995

  68. [68]

    George Lusztig, Quantum groups at roots of 1 , Geom.\ Dedicata 35 (1990), 89--113

    1990

  69. [69]

    Meena Mahajan, P. R. Subramanya and Vishwanathan Vinay, The combinatorial approach yields an NC algorithm for computing Pfaffians, Discrete Appl.\ Math. 143 (2004), 1--16; extended abstract in Proc.\ 5th COCOON (1999), 134--143

    2004

  70. [70]

    (1997), Art

    Meena Mahajan and Vishwanathan Vinay, Determinant: combinatorics, algorithms, and complexity, Chicago J.\ Theoret.\ Comput.\ Sci. (1997), Art. 5, 26 pp.; extended abstract in Proc.\ 8th SODA (1997), 730--738

    1997

  71. [71]

    12 (1999), 474--490; extended abstract in Proc.\ 6th SWAT (1998), 276--287

    Meena Mahajan and Vishwanathan Vinay, Determinant: old algorithms, new insights, SIAM J.\ Discrete Math. 12 (1999), 474--490; extended abstract in Proc.\ 6th SWAT (1998), 276--287

    1999

  72. [72]

    Manin, Quantum groups and noncommutative geometry, CRM, Universit\' e de Montr\' e al, QC, 1988, 91 pp

    Yuri I. Manin, Quantum groups and noncommutative geometry, CRM, Universit\' e de Montr\' e al, QC, 1988, 91 pp

    1988

  73. [73]

    Manin, Multiparameter quantum deformations of the linear supergroup, Comm.\ Math.\ Phys

    Yuri I. Manin, Multiparameter quantum deformations of the linear supergroup, Comm.\ Math.\ Phys. 123 (1989), 163--175

    1989

  74. [74]

    1062 (2026), Paper No

    Istvan Miklos and Cordian Riener, -hardness proofs of matrix immanants evaluated on restricted matrices, Theoret.\ Comput.\ Sci. 1062 (2026), Paper No. 115660, 14 pp

    2026

  75. [75]

    41 (2012), 332--355

    Cristopher Moore and Alexander Russell, Approximating the permanent via nonabelian determinants, SIAM J.\ Comput. 41 (2012), 332--355

    2012

  76. [76]

    Moore, On the determinant of an hermitian matrix of quaternionic elemens, Bull.\ AMS 28 (1922), 161--162

    Eliakim H. Moore, On the determinant of an hermitian matrix of quaternionic elemens, Bull.\ AMS 28 (1922), 161--162

    1922

  77. [77]

    Thomas Muir, A treatise on the theory of determinants (re-issue of 1928 ed.), Dover, New York, 1960, 766 pp

    1928

  78. [78]

    Noam Nisan, Lower bounds for non-commutative computation, in Proc.\ 23rd STOC (1991), 410--418

    1991

  79. [79]

    Andrei Okounkov, Quantum immanants and higher Capelli identities, Transform.\ Groups 1 (1996), 99--126

    1996

  80. [80]

    G\"unter Rote, Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches, in Computational Discrete Mathematics, Springer, Berlin, 2001, 119--135

    2001

Showing first 80 references.