@inproceedings{20007,
  abstract     = {There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.},
  author       = {Anastos, Michael and Kwan, Matthew Alan and Moore, Benjamin},
  booktitle    = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing},
  isbn         = {9798400715105},
  issn         = {0737-8017},
  location     = {Prague, Czechia},
  pages        = {2098--2106},
  publisher    = {Association for Computing Machinery},
  title        = {{Smoothed analysis for graph isomorphism}},
  doi          = {10.1145/3717823.3718173},
  year         = {2025},
}