Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing

Marek Černý, Tim Seppelt

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph $F\in \mathcal{F}$. Many…