{"id":"arxiv/2606.26244","url":"https://arxiv.org/abs/2606.26244","tags":["cs.CC","cs.DS","math.CO","math.RT"],"score":0,"title":"Geometric Complexity Theory and Graph Isomorphism","domain":"cs.CC","source":"arxiv","authors":["Joshua A. Grochow","Jacob Urisman"],"reviews":0,"subject":"cs.CC","summary":"We investigate ideas from the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001) in the setting of graph isomorphism. This provides us a playground of finite combinatorial objects on which to explore these techniques. We seek to separate non-isomorphic pairs of graphs using vector spaces of polynomials that are set-wise invariant under permutations (so-called separating modules). We characterize the power of this method for distinguishing graphs under several different complexity measures: - We show that separating modules of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-24","reactions":{}}