Speaker
Description
David E. Roberson and Tim Seppelt
Abstract: 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 L_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 L_t. By analysing the treewidth of graphs in L_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 L_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.