Testing Equivalence to the Hamiltonian Cycle Polynomial
Agrim Dewan · 2026
Read Testing Equivalence to the Hamiltonian Cycle Polynomial by Agrim Dewan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26653.txt.
Introduction
Agrim Dewan studies how to test whether a given polynomial secretly equals the Hamiltonian cycle polynomial. That polynomial sums over all cycles visiting every vertex of a complete directed graph once. It is a central hard object in algebraic complexity theory. Valiant showed it is complete for a large class of polynomials over every field, a distinction few rivals share.
The test problem takes a polynomial given in some compact form. It asks whether the polynomial is exactly the Hamiltonian cycle polynomial. Dewan's work, following Kayal's randomised algorithm for this problem, examines the test's power and limits. The polynomial's role as a universal hard case makes such identity tests important. They anchor attempts to generalise circuit lower bound results to all fields at once.
Catalog record
| CREATOR | Agrim Dewan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 158 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26653