Sum-of-Squares, Counting Logics and Graph Isomorphism

Joanna Ochremiak

The isomorphisms between two graphs can be described by the integral solutions of a system of linear equations and inequalities. We show that the Lasserre hierarchy of increasingly tighter semidefinite relaxations of this integer linear program is closely related to the well-known colour-refinement heuristic for graph isomorphism called the Weisfeiler-Lehman algorithm, or equivalently, to indistinguishability in logics with counting quantifiers and a bounded number of variables. This is joint work with Albert Atserias.