Reproduce “Testing Equivalence to the Hamiltonian Cycle Polynomial” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Agrim Dewan
Agrim Dewan, from the Indian Institute of Science, developed the first randomized polynomial-time algorithm to test equivalence to the Hamiltonian Cycle polynomial ($ ext{HC}_n$), a VNP-complete polynomial over all fields. This algorithm not only determines if a given polynomial is equivalent to $ ext{HC}_n$ under an affine transformation but also outputs the transformation if it exists, along with characterizing $ ext{HC}_n$'s unique algebraic structure.
Key insights
- For $n ext{\ge} 5$, $ ext{HC}_n$ is surprisingly not characterized by its symmetries, contrasting with the Permanent polynomial and requiring new verification methods.
- Despite lacking symmetry characterization for larger $n$, $ ext{HC}_n$ is characterized by circuit identities over any field, a property derived from its downward self-reducibility, which is crucial for the algorithm's soundness check.
- The Lie algebra of $ ext{HC}_n$ is explicitly characterized, with a dimension of $2n-2$ for $n=3$ or $n ext{\ge} 5$, providing fundamental insight into its algebraic structure.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.