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 case in many branches of complexity theory, the unconditional separation of these complexity classes seems elusive. In stark contrast, the symmetric analogue of Valiant’s conjecture has been proven by Dawar and Wilsenach (2020): the permanent does not admit symmetric algebraic circuits of polynomial size, while the determinant does. Symmetric algebraic circuits are both a powerful computational model and amenable to proving unconditional lower bounds.

In this paper, we develop a symmetric algebraic complexity theory by introducing symmetric analogues of the complexity classes VP, VBP, and VF called symVP, symVBP, and symVF. They comprise polynomials that admit symmetric algebraic circuits, skew circuits, and formulas, respectively, of polynomial orbit size. Having defined these classes, we show unconditionally that symVF ⊊ symVBP ⊊ symVP. To that end, we characterise the polynomials in symVF and symVBP as those that can be written as linear combinations of homomorphism polynomials for patterns of bounded treedepth and pathwidth, respectively. This extends a previous characterisation by Dawar, Pago, and Seppelt (2026) of symVP.

Finally, we show that symVBP and symVP contain homomorphism polynomials which are VBP- and VP-complete, respectively. We give general graph-theoretic criteria for homomorphism polynomials and their linear combinations to be VBP-, VP-, or VNP-complete. These conditional lower bounds drastically enlarge the realm of natural polynomials known to be complete for VNP, VP, or VBP. Under the assumption VFPT VW[1], we precisely identify the homomorphism polynomials that lie in VP as those whose patterns have bounded treewidth.

Two graphs G and H are homomorphism indistinguishable over a class of graphs 𝓕 if, for all graphs F ∊ 𝓕, the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In 1967, Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over the class of all graphs. Subsequently, many graph isomorphism relaxations such as quantum isomorphism, spectral, and logical equivalences have been characterised as homomorphism indistinguishability relations over certain graph classes. Thereby, homomorphism indistinguishability connects seemingly disparate fields such as quantum information, finite model theory, and machine learning.

This thesis explores three themes: We first review the plenitude of characterisations of graph isomorphism relaxations as a homomorphism indistinguishability relation. Focusing on integer programming relaxations for graph isomorphism, we prove that the feasibility of each level of the Sherali–Adams and Lasserre hierarchies is characterised as homomorphism indistinguishability relations. These results, which are derived using (bi)labelled graphs and homomorphism tensors, shed light on the distinguishing power of these hierarchies. In particular, we determine the precise number of Sherali–Adams levels necessary such that their feasibility guarantees the feasibility of a given Lasserre level.

Abstracting from the wealth of homomorphism indistinguishability characterisations, we embark on a more principled study of homomorphism indistinguishability investigating the distinguishing power and the complexity of homomorphism indistinguishability relations over minor-closed graph class.

The homomorphism distinguishing closure cl(𝓕) of a graph class 𝓕 is the central notion for studying the distinguishing power of homomorphism indistinguishability relations. It is defined as the maximal graph class whose homomorphism indistinguishability relation coincides with the one of 𝓕. Roberson conjectured that every minor-closed union-closed graph class 𝓕 is homomorphism distinguishing closed, i.e. cl(𝓕) = 𝓕. We confirm Roberson’s conjecture, which is generally wide open, for further graphs classes and prove unconditionally that if 𝓕 is minor-closed then so is cl(𝓕).

Lastly, we investigate the complexity of deciding whether two graphs are homomorphism indistinguishable over a fixed graph class. For infinite graph classes, this problem is a priori not even decidable. In stark contrast to this, we show that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomised polynomial time.

We show that feasibility of the t^th level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class ℒ_t of graphs such that graphs G and H are not distinguished by the t^th level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in ℒ_t. By analysing the treewidth of graphs in ℒ_t we prove that the 3t^th level of Sherali-Adams linear programming hierarchy is as strong as the t^th level of Lasserre. Moreover, we show that this is best possible in the sense that 3t cannot be lowered to 3t-1 for any t. The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family ℒ_t^+ of graphs. Additionally, we give characterisations of level-t Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler-Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the t^th level of the Lasserre hierarchy with non-negativity constraints.

Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker than isomorphism. In this paper, we study cospectrality in relation to another well-studied relaxation of isomorphism, namely k-dimensional Weisfeiler-Leman (k-WL) indistinguishability. Cospectrality with respect to standard graph matrices such as the adjacency or the Laplacian matrix yields a strictly finer equivalence relation than 2-WL indistinguishability. We show that individualising one vertex plus running 1-WL already subsumes cospectrality with respect to all such graph matrices. Building on this result, we resolve an open problem of Fürer (2010) about spectral invariants.
Looking beyond 2-WL, we devise a hierarchy of graph matrices generalising the adjacency matrix such that k-WL indistinguishability after a fixed number of iterations can be captured as a spectral condition on these matrices. Precisely, we provide a spectral characterisation of k-WL indistinguishability after d iterations, for k,d ∈ ℕ. Our results can be viewed as characterisations of homomorphism indistinguishability over certain graph classes in terms of matrix equations. The study of homomorphism indistinguishability is an emerging field, to which we contribute by extending the algebraic framework of Mančinska and Roberson (2020) and Grohe et al. (2022).