5 papers
Topological and Geometric Perspectives on Homomorphism Indistinguishability
Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson +3
Two graphs and are homomorphism indistinguishable over a graph class if, for every graph , the number of homomorphisms from to is e…
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
Snir Hordan, Nadav Dym, Tim Seppelt
Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number , the -Weisfeiler-Leman (-WL) test cannot distinguish all no…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
Daniel Neuen, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., and admit the same number of…