pith. sign in

arxiv: 2606.26653 · v1 · pith:TWUVTN3Inew · submitted 2026-06-25 · 💻 cs.CC

Testing Equivalence to the Hamiltonian Cycle Polynomial

Agrim Dewan (Indian Insitute of Science , Bengaluru) This is my paper

Pith reviewed 2026-06-26 02:32 UTC · model grok-4.3

classification 💻 cs.CC
keywords Hamiltonian Cycle polynomialequivalence testingVNP-completedownward self-reducibilitycircuit identitiesrandomised algorithmsymmetries
0
0 comments X

The pith

A randomised polynomial time algorithm tests equivalence to the Hamiltonian Cycle polynomial under linear transformations over fields with mild constraints.

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

The paper presents a randomised polynomial time algorithm for testing equivalence of a black-box polynomial to the Hamiltonian Cycle polynomial HC_n via an invertible linear change of variables. It establishes that the symmetries of HC_n are generated by permutation and scaling matrices over large enough fields, yet HC_n is not characterised by those symmetries. The key step is invoking the downward self-reducibility of HC_n to conclude that it is characterised by circuit identities, which directly yields the equivalence test and an algorithm to check whether a given circuit computes HC_n. The result also produces a Flip theorem for HC_n. A sympathetic reader would care because this supplies an efficient verification method for a VNP-complete family that is defined combinatorially rather than algebraically.

Core claim

We give a randomised polynomial time ET algorithm for HC with mild constraints on the field. We show that the symmetries of HC_n are generated by permutation and scaling matrices over large enough fields. We also show that HC_n is not characterised by its symmetries, unlike the Permanent polynomial. Nevertheless, HC_n is downward self-reducible, implying HC_n is characterised by circuit identities and therefore admits an efficient algorithm to test if a given circuit C computes HC_n. We also get a Flip theorem for HC_n as a result of its circuit identities.

What carries the argument

Downward self-reducibility of HC_n, which produces a characterisation by circuit identities that enables the equivalence test.

If this is right

  • The symmetries of HC_n are generated by permutation and scaling matrices over large enough fields.
  • HC_n is not characterised by its symmetries.
  • HC_n is characterised by circuit identities due to downward self-reducibility.
  • There is an efficient algorithm to test whether a given circuit computes HC_n.
  • A Flip theorem holds for HC_n.

Where Pith is reading between the lines

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

  • The separation between symmetry characterisation and circuit-identity characterisation may classify other VNP-complete families.
  • The black-box nature of the test allows verification of HC_n computations without expanding the polynomial explicitly.

Load-bearing premise

HC_n is downward self-reducible.

What would settle it

A concrete polynomial g that passes the randomised test yet is not equal to HC_n composed with any invertible linear matrix, or a circuit that computes HC_n but fails the circuit-identity test.

read the original abstract

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. Valiant (STOC 1979) studied the Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, and showed both families are VNP-complete, the former over any field of characteristic other than $2$, and the latter over any field. Since its introduction, $HC$ has been studied from the perspective of lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its relation to the Permanent by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). Its VNP-completeness over any field has been used in Malod (CCC 2007), Grochow-Mulmuley-Qiao (ICALP 2016) and Hrubes (ToCT, 2016). The Equivalence Testing problem for a polynomial $f(\mathbf{x})$ (ET for $f$) is as follows: Given $g(\mathbf{x}) \in \mathbb{F}[\mathbf{x}]$ as a black box, decide if there exists $A \in \mathrm{GL}_{|\mathbf{x}|}(\mathbb{F})$ such that $g = f(A\mathbf{x})$. Kayal (STOC 2012) gave a randomised polynomial time ET algorithm for the Permanent. In this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the field. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. We also show that $HC_n$ is not characterised by its symmetries, unlike the Permanent polynomial, Mulmuley-Sohoni (SIAM J. Computing, 2001). Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, Zhang-Bai (TCS 2011), implying $HC_n$ is characterised by circuit identities and an efficient algorithm to test if a given circuit $\mathrm{C}$ computes $HC_n$. We also get a Flip theorem for $HC_n$ as a result of its circuit identities.

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

Summary. The paper claims a randomized polynomial-time equivalence testing (ET) algorithm for the Hamiltonian Cycle polynomial HC_n over fields with mild constraints. It proves that the symmetries of HC_n are generated by permutation and scaling matrices (over large enough fields), shows that HC_n is not characterized by its symmetries (unlike the Permanent), but invokes downward self-reducibility (Zhang-Bai, TCS 2011) to conclude that HC_n is characterized by circuit identities, yielding an efficient algorithm to test whether a given circuit computes HC_n. A Flip theorem for HC_n is also derived as a consequence.

Significance. If the central implication holds, the result extends Kayal's ET algorithm for the Permanent to another VNP-complete family, providing a second example where ET is tractable. The explicit determination of the symmetry group (permutations plus scalings) is a concrete contribution independent of the ET claim, and the Flip theorem adds a structural result. The work helps map the boundary between symmetry-characterized and circuit-identity-characterized polynomials in algebraic complexity.

major comments (2)
  1. [paragraph following symmetry analysis and Zhang-Bai citation] The paragraph invoking downward self-reducibility (immediately after the symmetry results and the citation to Zhang-Bai TCS 2011): the manuscript asserts that this property 'implying HC_n is characterised by circuit identities and an efficient algorithm to test if a given circuit C computes HC_n' without supplying the explicit construction of the identities, the reduction from black-box ET to identity testing, or the derivation showing how self-reducibility produces distinguishing identities for linear images of HC_n. This step is load-bearing for the main algorithmic claim.
  2. [abstract and introduction] The statement of the main result (abstract and introduction): the algorithm is claimed to hold 'with mild constraints on the field,' yet no explicit field-size lower bound, characteristic restriction, or handling of characteristic-2 issues is derived or stated in the visible argument, even though the symmetry group proof is noted to require 'large enough fields.'
minor comments (1)
  1. [abstract vs. technical definitions] Notation for the variable set and the matrix A in the ET definition could be made uniform between the abstract and the technical sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to improve clarity and completeness.

read point-by-point responses

  1. Referee: [paragraph following symmetry analysis and Zhang-Bai citation] The paragraph invoking downward self-reducibility (immediately after the symmetry results and the citation to Zhang-Bai TCS 2011): the manuscript asserts that this property 'implying HC_n is characterised by circuit identities and an efficient algorithm to test if a given circuit C computes HC_n' without supplying the explicit construction of the identities, the reduction from black-box ET to identity testing, or the derivation showing how self-reducibility produces distinguishing identities for linear images of HC_n. This step is load-bearing for the main algorithmic claim.

    Authors: We agree that the current presentation is too terse on this load-bearing step. While the downward self-reducibility of HC_n is cited from Zhang-Bai (TCS 2011) and the implication for circuit identities follows the same high-level logic as Kayal's treatment of the Permanent, we did not spell out the explicit identities or the reduction from black-box equivalence testing to identity testing for linear images. In the revised version we will add a dedicated subsection that (i) recalls the relevant identities obtained from self-reducibility, (ii) shows how they distinguish HC_n from its linear images, and (iii) sketches the reduction to PIT, adapting the Permanent argument to the Hamiltonian-cycle setting. revision: yes

  2. Referee: [abstract and introduction] The statement of the main result (abstract and introduction): the algorithm is claimed to hold 'with mild constraints on the field,' yet no explicit field-size lower bound, characteristic restriction, or handling of characteristic-2 issues is derived or stated in the visible argument, even though the symmetry group proof is noted to require 'large enough fields.'

    Authors: The symmetry-group theorem is proved only for fields that are sufficiently large (size at least a fixed polynomial in n) and of characteristic not equal to 2. The ET algorithm inherits these hypotheses because it relies on the explicit description of the symmetry group. We will revise the abstract and introduction to state the precise conditions (char(F) ≠ 2 and |F| ≥ n^c for an explicit constant c derived from the symmetry proof) and will add a short remark on the characteristic-2 case, noting that while HC_n remains well-defined, the current symmetry analysis does not apply and a separate argument would be needed. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation rests on external citation

full rationale

The paper invokes downward self-reducibility of HC_n via the external citation Zhang-Bai (TCS 2011) to conclude characterization by circuit identities, then derives the ET algorithm from that. This is not a self-citation (authors are distinct), not load-bearing in the sense of pattern 3, and does not reduce any claimed prediction or identity to a fitted parameter or self-definition by construction. Internal results on symmetries and non-characterization by symmetries are proved separately without circular reduction. No equations or steps exhibit the forbidden patterns; the chain is self-contained once the cited external fact is granted.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard background results in algebraic complexity (VNP-completeness of HC, downward self-reducibility from Zhang-Bai) and on field-size assumptions stated as 'mild constraints'; no free parameters are fitted inside the algorithm and no new entities are postulated.

axioms (2)
  • domain assumption HC_n is downward self-reducible (Zhang-Bai, TCS 2011)
    Invoked to obtain circuit identities that characterize HC_n and thereby yield the equivalence test.
  • standard math Standard facts about polynomial identity testing and randomized algorithms over finite fields of sufficient size
    Required for the randomized polynomial-time procedure to succeed with high probability.

pith-pipeline@v0.9.1-grok · 5995 in / 1524 out tokens · 50815 ms · 2026-06-26T02:32:30.126490+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

22 extracted references · 1 linked inside Pith

  1. [1]

    Mono- tone Circuit Complexity of Matching.CoRR, abs/2507.16105, 2025

    22 [CGR+25] Bruno Cavalar, Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Mono- tone Circuit Complexity of Matching.CoRR, abs/2507.16105, 2025. To appear in the proceedings of 58th Annual ACM Symposium on Theory of Computing (STOC 2026). 21 [CGS23] Suryajith Chillara, Coral Grichener, and Amir Shpilka. On Hardness of Testing Equivalen...

    arXiv 2025

  2. [2]

    19 [DRS24] Pranjal Dutta, Mahesh Sreekumar Rajasree, and Santanu Sarkar

    Springer, 2014. 19 [DRS24] Pranjal Dutta, Mahesh Sreekumar Rajasree, and Santanu Sarkar. Complexity of Monomial Pre- diction in Cryptography and Machine Learning. In2024 26th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pages 118–125, 2024. 2, 22 [FGT21] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf....

    2014

  3. [3]

    Determinant Equivalence Test over Finite Fields and over Q

    2 [GGKS19] Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, July 9-12, 2019 , volume 132 of LIPIc...

    2019

  4. [4]

    Grochow and Youming Qiao

    2, 22 [GQ23] Joshua A. Grochow and Youming Qiao. On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. SIAM J. Comput. , 52(2):568–617, 2023. Conference version appeared in the proceedings of ITCS 2021. 19 [Gre11] Bruno Grenet. An Upper Bound for the Permanent versus Determinant Problem. Manuscript,

    2023

  5. [5]

    Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines

    21 [Gri97] Dima Grigoriev. Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines. Theor. Comput. Sci., 180(1-2):217–228, 1997. 19 [Gro12] Joshua A. Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, University of Chicago, Chicago, IL, 2012. 1, 2, 6, 18, 20, 45 [Gro1...

    1997

  6. [6]

    1, 19, 20 [Kay12] Neeraj Kayal

    SIAM, 2011. 1, 19, 20 [Kay12] Neeraj Kayal. Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 643–662, 2012. 2, 1, 3, 4, 5, 6, 18, 19, 20 [KI04] Valentine Kabanets and Russell Impagliazzo. Derandomizing Polynomial Identity Tes...

    2011

  7. [7]

    Reconstruction of Full Rank Algebraic Branching Programs

    19 [KNST19] Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. ACM Trans. Comput. Theory , 11(1):2:1–2:56, 2019. Conference version appeared in the proceedings of CCC 2017. 3, 6, 19, 20 15 [KPTT15] Pascal Koiran, Natacha Portier, Sébastien Tavenas, and Stéphan Thomassé. A τ -conjecture...

    2019

  8. [8]

    A quadratic bound for the determinant and permanent problem

    20 [MR04] Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. International Mathematics Research Notices, 2004(79):4241–4253, 01 2004. 21 [MS01] Ketan Mulmuley and Milind A. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput., 31(2):496–526, 2001. 2 [MS18] M...

    Pith/arXiv arXiv 2004

  9. [9]

    i2 ∈ S and i4 ∈ S: In this case, we have that xi1,j1 ∂mσ1 ∂xi2,j2 = xi1,j1 ∏i∈S xi,σ1(i) xi2,j2 ˙∏i/∈Sxi,σ1(i) and xi3,j3 ∂mσ2 ∂xi4,j4 = xi3,j3 ∏i∈S xi,σ2(i) xi4,j4 ˙∏i/∈Sxi,σ2(i)

  10. [10]

    i2 ∈ S and i4 /∈ S: In this case we have, xi1,j1 ∂mσ1 ∂xi2,j2 = xi1,j1 ∏i∈S xi,σ1(i) xi2,j2 ∏ i/∈S xi,σ1(i) and xi3,j3 ∂mσ2 ∂xi4,j4 = xi3,j3 ∏ i∈S xi,σ2(i) ∏i/∈S xi,σ2(i) xi4,j4 Note that the case i2 /∈ S and i4 ∈ S is the same as this case with the appropriate changes in the resulting monomials

  11. [11]

    i2 /∈ S and i4 /∈ S xi1,j1 ∂mσ1 ∂xi2,j2 = xi1,j1 ∏ i∈S xi,σ1(i) ∏i/∈S xi,σ1(i) xi2,j2 and xi3,j3 ∂mσ2 ∂xi4,j4 = xi3,j3 ∏ i∈S xi,σ2(i) ∏i/∈S xi,σ2(i) xi4,j4 By the unique factorization theorem for multivariate polynomials, if the resulting monomials were equal, then their factors must be the same. However, as |S| = 3, it is not hard to observe in all of th...

  12. [12]

    As σ1 and σ2 are permutations, there exists a j1 ∈ [i + 1, n − 1]\{k1} such that σ1(mj1 ) = m′ i+1 and σ2(mj1 ) ̸= m′ i+1

    m′ i+1 ̸= mk1+1: This implies σ1(mk1 ) ̸= m′ i+1. As σ1 and σ2 are permutations, there exists a j1 ∈ [i + 1, n − 1]\{k1} such that σ1(mj1 ) = m′ i+1 and σ2(mj1 ) ̸= m′ i+1

  13. [13]

    Suppose to the contrary that there did not exist such aj1, then σ1(mj) = σ2(mj) for all j ∈ [i + 1, k1 − 1]

    m′ i+1 = mk1+1: In this case, we show that there exists a j1 ∈ [i + 1, k1 − 1] such that σ1(mj1 ) ̸= σ2(mj1 ). Suppose to the contrary that there did not exist such aj1, then σ1(mj) = σ2(mj) for all j ∈ [i + 1, k1 − 1]. Since m′ k2+1 = σ2(m′ k2 ) = mi+1, we also get from the previous assumption that mi+j = m′ k2+j for j ∈ [1, k1 − i]. Based on this, we ha...

  14. [14]

    For n ≥ 4, it is easy to see that there exists π ∈ Cn, such that π(i) = j, π(k) = ℓ

    i ̸= ℓ and k ̸= j: For n = 3, this case is not possible as i, j, k, ℓ are all distinct. For n ≥ 4, it is easy to see that there exists π ∈ Cn, such that π(i) = j, π(k) = ℓ. Hence, ∂2HCn ∂xi,j∂xk,ℓ = ∑ π∈Cn, π(i)=j, π(k)=ℓ ∏ i1∈[n]\{i,k} xi1,π(i1) ̸= 0, a contradiction

  15. [15]

    Hence, ∂2HCn ∂xi,j∂xk,ℓ = ∑ π∈Cn, π(i)=j, π(k)=i ∏ i1∈[n]\{i,k} xi1,π(i1) ̸= 0, a contradiction

    i = ℓ and k ̸= j: There exists π ∈ Cn, such that π(i) = j, π(k) = i = ℓ. Hence, ∂2HCn ∂xi,j∂xk,ℓ = ∑ π∈Cn, π(i)=j, π(k)=i ∏ i1∈[n]\{i,k} xi1,π(i1) ̸= 0, a contradiction. Note that the case i ̸= ℓ and k = j gives a contradiction in the same way

  16. [16]

    Hence, only the last case is possible, proving the forward direction

    i = ℓ and k = j: This is the assumption in the reverse direction. Hence, only the last case is possible, proving the forward direction. The partition of Ri,j as described in the Observation statement follows easily by using the conditions proved for the vanishing of the second- order derivatives of HCn. C.13 Proof of Proposition 3.7 Let π ∈ Sn\Cn such tha...

  17. [17]

    Then π(i − 1) = k and π(ℓ) = 1, where k, ℓ ∈ [n − 1]\{1, i − 1} and k ̸= ℓ as n ≥ 5

    π(1) = i − 1. Then π(i − 1) = k and π(ℓ) = 1, where k, ℓ ∈ [n − 1]\{1, i − 1} and k ̸= ℓ as n ≥ 5. In this case n−1 ∏ j=1 Z(i) j,π(j) = Z(i) 1,i−1Z(i) i−1,kZ(i) ℓ,1 ∏ j̸=1,i−1,ℓ Z(i) j,π(j) = xi,2x2,k+1xℓ+1,1 ∏ j̸=1,i−1,ℓ xj+1,π(j)+1

  18. [18]

    Then π(1) = k and π(ℓ) = i − 1, where k, ℓ ∈ [n − 1]\{1, i − 1} and k ̸= ℓ as n ≥ 5

    π(1) ̸= i − 1 and π(i − 1) = 1. Then π(1) = k and π(ℓ) = i − 1, where k, ℓ ∈ [n − 1]\{1, i − 1} and k ̸= ℓ as n ≥ 5. In this case n−1 ∏ j=1 Z(i) j,π(j) = Z(i) 1,kZ(i) i−1,1Z(i) ℓ,i−1 ∏ j̸=1,i−1,ℓ Z(i) j,π(j) = xi,k+1x2,1xℓ+1,2 ∏ j̸=1,i−1,ℓ xj+1,π(j)+1

  19. [19]

    Let π(1) = j1, π(i − 1) = j2, π(ℓ) = i − 1 and π(k) = 1, with j1, j2, ℓ, k ∈ [n − 1]

    π(1) ̸= i − 1 and π(i − 1) ̸= 1. Let π(1) = j1, π(i − 1) = j2, π(ℓ) = i − 1 and π(k) = 1, with j1, j2, ℓ, k ∈ [n − 1]. In this case n−1 ∏ j=1 Z(i) j,π(j) = Z(i) 1,j1 Z(i) i−1,j2 Z(i) ℓ,i−1Z(i) k,1 ∏ j̸=1,i−1,ℓ,k Z(i) j,π(j) = xi,j1+1x2,j2+1xℓ+1,2xk+1,1 ∏ j̸=1,i−1,ℓ,k xj+1,π(j)+1 In all of the above cases, π maps to a unique σ ∈ Cn such that σ(1) = i and ∏...

  20. [20]

    The diagonal matrix D with D1,2 = D2,3 = D3,1 = −1 and the rest of the entries as 1 is a discrete scaling symmetry of HC4

  21. [21]

    When char(F) = 2, then D is the identity matrix

    The diagonal matrix S, with entries satisfying S1,2 = S4,2 S2,4S3,2S4,1S4,3 , S1,3 = 1 S2,4S3,2S4,1 , S1,4 = S3,4S4,2 S2,4S2 3,2S4,1S4,3 , S2,1 = S2,4S3,2S4,1 S3,4S4,2 , S2,3 = S2,4S3,2S4,3 S3,4S4,2 , S3,1 = S3,2S4,1 S4,2 , (26) is a continuous scaling symmetry of HC4. When char(F) = 2, then D is the identity matrix. Lemma C.5. Over Fq such that 2 ∤ q − 1...

  22. [22]

    The correctness of Steps 2 and 3 follows from Claim 4.1 and Observation 3.2

    Repeating the algorithm will boost the success probability. The correctness of Steps 2 and 3 follows from Claim 4.1 and Observation 3.2. By Observation 3.2 we have that P′(x2,1) must be xi,j, proving the correctness of Step 4. Now, the set T′ 1,2 is either the image of T1,2 or that of Q1,2 under P. In the first case, the elements of T′ 1,2 are of form P(x...