2025/06/30 by Qiuyue Liu, Zhanyuan Cai, Liu, Qiuyue +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #FOS: Mathematics #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.2506.23846
openalex publication_date 2025/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the unimodular isomorphism problem (UIP) of convex lattice polytopes: given two convex lattice polytopes P and P', decide whether there exists a unimodular affine transformation mapping P to P'. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( \mathrmSikiri\acutec, \mathrmSchurmann, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP.