{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiap37za6ily3enhnsyrazpweh4qou76szi3hygpt6olsg4n3jbaiq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mp6447z5xbj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.26653v1",
  "publishedAt": "2026-06-26T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Agrim Dewan"
  ],
  "textContent": "**Authors:** Agrim Dewan\n\nThe 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.",
  "title": "Testing Equivalence to the Hamiltonian Cycle Polynomial"
}