Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets F and G of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then F and G are Holant-indistinguishable, i.e., every tensor network using tensors from F, resp. from G, 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 F and G always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GLq-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, and hence hard for graph isomorphism.