Geometric Complexity Theory and Graph Isomorphism

Abstract

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 "support-degree" k are equivalent in power to the counts of O(k)-vertex subgraphs. - We show that separating modules of symmetric algebraic circuit size n^Θ(k) are equivalent to Θ(k)-dimensional Weisfeiler-Leman. This generalizes and strengthens the result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025). - When considering only the representation-theoretic multiplicities of separating modules, we show that two graphs are separated by multiplicities if and only if their automorphism groups have different multiplicity of cycle types (cycle index). The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect support size (from the study of WL) to complexity measures on S_n (Dafni, Filmus, Lifshitz, Lindzey, & Vinyals, ITCS '21); as well as connections between invariant polynomials, the Graph Reconstruction Conjectures, and Forman's "invariants of finite type" (Adv. Math., 2004).

Canonical Directed Laplacian on F_2^4, Symmetry-Induced Two-Scale Coupling, and the Structural Isomorphism of a 64-Copy Boolean Graph Assembly
Alejandro Diaz
28 Jun 2026PreprintLicence not statedFull text5 citedGeometry & topologyOpenAlex
Isomorphism classes and geometric classification of three-dimensional Jordan algebras and the length function
Isabel Hernandez, Maria Eugenia Martin, Rodrigo Lucas Rodrigues +1
arXiv1 Nov 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
A study on Type-2 isomorphic circulant graphs. Part 8: Isomorphism series, digraph and graph of C_n(R)
V. Vilfred Kamalappan
arXiv27 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings
Joshua A. Grochow, Youming Qiao, Katherine E. Stange +1
arXiv1 Nov 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
Dibyayan Chakraborty, Florent Foucaud
HAL27 Sep 2026PreprintLicence not statedCombinatorics & discrete mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{grochow2026geometric,
  title = {{Geometric Complexity Theory and Graph Isomorphism}},
  author = {Joshua A. Grochow and Jacob Urisman},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.26244},
  eprint = {2606.26244},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.26244},
}

RIS

TY  - UNPB
TI  - Geometric Complexity Theory and Graph Isomorphism
AU  - Joshua A. Grochow
AU  - Jacob Urisman
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2606.26244
UR  - https://arxiv.org/abs/2606.26244
AB  - 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 "support-degree" k are equivalent in power to the counts of O(k)-vertex subgraphs. - We show that separating modules of symmetric algebraic circuit size n^Θ(k) are equivalent to Θ(k)-dimensional Weisfeiler-Leman. This generalizes and strengthens the result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025). - When considering only the representation-theoretic multiplicities of separating modules, we show that two graphs are separated by multiplicities if and only if their automorphism groups have different multiplicity of cycle types (cycle index). The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect support size (from the study of WL) to complexity measures on S_n (Dafni, Filmus, Lifshitz, Lindzey, & Vinyals, ITCS '21); as well as connections between invariant polynomials, the Graph Reconstruction Conjectures, and Forman's "invariants of finite type" (Adv. Math., 2004).
ER  -

Abstract

Related

Cite