{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia6c5mdjr52grbyhfnfgtimsyepyzcyoudlqirkku4ng2f6kypkj4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mpdgghe4kb72"
  },
  "path": "/report/2026/107",
  "publishedAt": "2026-06-28T04:50:40.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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}$. The Permanent and $HC$, defined as the family $\\{HC_n | \\ n \\geq 1\\}$, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of characteristic other than $2$, and the latter to be VNP-complete over every field. Since its introduction, $HC$ has been studied from the perspective of circuit lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its connection with the Permanent and the Determinant polynomials by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). It has been the most prominent choice for generalising results to all fields, such as in Malod (CCC 2007) and Grochow-Mulmuley-Qiao (ICALP 2016), owing to its VNP-completeness over every field. Hrubes (ToCT, 2016) showed the VNP-completeness of many graph-based polynomial families over every field by using $HC$.\n    \nIn Kayal (STOC 2012), a randomised polynomial time algorithm was given for the following problem: Given an $n^2$-variate degree-$n$ polynomial $f(\\mathbf{x}) \\in \\mathbb{F}[\\mathbf{x}]$ as a black box, decide if there exists $A \\in \\mathrm{GL}_{n^2}(\\mathbb{F})$ such that $f(\\mathbf{x}) = Perm_n(A\\mathbf{x})$. Here, the Permanent polynomial $Perm_n$  computes the permanent of the $n \\times n$ symbolic matrix $(x_{i,j})$. This problem is known as testing equivalence to the Permanent, or alternatively, ET for Permanent. \n    \nIn this work, we study ET for $HC$. While both families are VNP-complete, the efficient ET algorithm for Permanent does not imply the same for $HC$.  Besides, there are crucial differences between the two polynomials that make studying the complexity of ET for $HC$ interesting: The underlying decision problem corresponding to the Permanent is in P (detecting perfect matchings in a bipartite graph), but that for $HC$ (detecting  Hamiltonian cycles in a digraph) is NP-complete. The Permanent polynomial is known to be characterised by its symmetries as shown by Mulmuley-Sohoni (SIAM J. Computing, 2001). This property yields an efficient algorithm for the circuit-testing problem for the Permanent, a special case of ET for the Permanent, in which we check whether a given circuit computes the Permanent. In contrast, we show $HC_n$ is not characterised by its symmetries. \n    \nIn this work, we give a randomised polynomial time ET algorithm for $HC$ with mild constraints on the underlying field. The algorithm is obtained by studying and completely characterising the Lie algebra and the symmetries of $HC_n$. We show that, like the Permanent polynomial, the symmetries of $HC_n$ are generated by permutation and scaling matrices over large enough fields. However, we also show that, unlike the Permanent polynomial, $HC_n$ is not characterised by its symmetries. Nevertheless, like the Permanent polynomial, $HC_n$ is downward self-reducible, as shown in Zhang-Bai (TCS 2011), which implies $HC_n$ is characterised by circuit identities and that we can efficiently test whether 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": "TR26-107 |  Testing Equivalence to the Hamiltonian Cycle Polynomial | \n\n\tAgrim Dewan"
}