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

CREATORAgrim Dewan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE158 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26653

Browse the full library · About the Tower of Babel