4 citations · 8 across the 9 of their papers we have counts for
5 papers · 1 filter
The Complexity of Homomorphism Reconstructibility
Jan Böker, Louis Härtel, Nina Runde +2
Representing graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising…
Limitations of Game Comonads via Homomorphism Indistinguishability
Moritz Lichter, Benedikt Pago, Tim Seppelt
Abramsky, Dawar, and Wang (2017) introduced the pebbling comonad for k-variable counting logic and thereby initiated a line of work that imports category theoretic machinery to fin…
Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth
Eva Fluck, Tim Seppelt, Gian Luca Spitzer
We study the expressive power of first-order logic with counting quantifiers, especially the -variable and quantifier-rank- fragment , using homomorphism indi…
Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
Tim Seppelt
Two graphs and are homomorphism indistinguishable over a class of graphs if for all graphs the number of homomorphisms from to is…
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
David E. Roberson, Tim Seppelt
We show that feasibility of the level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability…