We introduce an approach to separating isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (so-called separating modules, which are, in particular, representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: degree, symmetric algebraic circuit size, and when considering only the representation-theoretic multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves).
Based on joint work with Joshua Grochow.
