2026-10-11T04:21:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25319 2026-03-19T12:03:27Z ddc:004 open_access

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem Cai, Jin-Yi Young, Ben Holant Orbit Closure Intersection Homomorphism Indistinguishability Tensor Network Valiant’s Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets ℱ and 𝒢 of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then ℱ and 𝒢 are Holant-indistinguishable, i.e., every tensor network using tensors from ℱ, respectively from 𝒢, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable ℱ and 𝒢 always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GL_q-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class TOCI introduced by Lysikov and Walter [Vladimir Lysikov and Michael Walter, 2024], and hence hard for graph isomorphism. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jin-Yi Cai and Ben Young 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.32 urn:nbn:de:0030-drops-253198 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode