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

Abstract

Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\mathcal{F}$ and $\mathcal{G}$ of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then $\mathcal{F}$ and $\mathcal{G}$ are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from $\mathcal{F}$, resp. from $\mathcal{G}$, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{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 $\mathcal{F}$ and $\mathcal{G}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their ${\text{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 \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism.

32 pages, 10 figures