7 papers
Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
Isolde Adler, Eva Fluck, Tim Seppelt +1
We study the expressive power of first-order logic with counting quantifiers, especially the -variable and quantifier-rank- fragment, using homomorphism indistinguishability.…
Homomorphism Indistinguishability Relations induced by Quantum Groups
Tim Seppelt, Gian Luca Spitzer
Homomorphism indistinguishability is a way of characterising many natural equivalence relations on graphs. Two graphs and are called homomorphism indistinguishable over a g…
Symmetric Algebraic Circuits and Homomorphism Polynomials
Anuj Dawar, Benedikt Pago, Tim Seppelt
The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic…
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Prem Nigam Kar, David E. Roberson, Tim Seppelt +1
ManÄinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. Atserias et al. [J…
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, Tim Seppelt
Valiant's conjecture asserts that the circuit complexity classes VP and VNP are distinct, meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the…
Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
Marek Äerný, Tim Seppelt
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph . Many…