Smoothed analysis for graph isomorphism
Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.
Download
Conference Paper
| Published
| English
Scopus indexed
Corresponding author has ISTA affiliation
Department
Grant
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.
Publishing Year
Date Published
2025-06-15
Proceedings Title
Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Publisher
Association for Computing Machinery
Acknowledgement
All authors were supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Michael Anastos was also supported in part by the Austrian Science Fund (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. For Open Access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.
Page
2098-2106
Conference
STOC: Symposium on Theory of Computing
Conference Location
Prague, Czechia
Conference Date
2025-06-23 – 2025-06-27
ISBN
ISSN
IST-REx-ID
Cite this
Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173
Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173
Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2098–2106. Association for Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718173.
M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025, pp. 2098–2106.
Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.
Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2025_STOC_Anastos.pdf
706.45 KB
Access Level
Open Access
Date Uploaded
2025-07-14
MD5 Checksum
cf0ab9cb9c6abda188de13dc3f9a4c9b
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2410.06095
Google Scholar
ISBN Search