{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:14Z","timestamp":1758586214393,"version":"3.44.0"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_16","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:39Z","timestamp":1758498339000},"page":"208-220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of\u00a0Identifying Fitting-Free Groups"],"prefix":"10.1007","author":[{"given":"Joshua A.","family":"Grochow","sequence":"first","affiliation":[]},{"given":"Dan","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Levet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"issue":"5","key":"16_CR1","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ic.2006.02.002","volume":"204","author":"V Arvind","year":"2006","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. Inf. Comput. 204(5), 835\u2013852 (2006). https:\/\/doi.org\/10.1016\/j.ic.2006.02.002","journal-title":"Inf. Comput."},{"issue":"6","key":"16_CR2","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/S0195-6698(89)80067-8","volume":"10","author":"L Babai","year":"1989","unstructured":"Babai, L., Kantor, W., Lubotsky, A.: Small-diameter Cayley graphs for finite simple groups. Eur. J. Combin. 10(6), 507\u2013522 (1989). https:\/\/doi.org\/10.1016\/S0195-6698(89)80067-8","journal-title":"Eur. J. Combin."},{"key":"16_CR3","doi-asserted-by":"publisher","unstructured":"Babai, L., Luks, E., Seress, A.: Permutation groups in NC. In: STOC 1987, pp. 409\u2013420. Association for Computing Machinery (1987). https:\/\/doi.org\/10.1145\/28395.28439","DOI":"10.1145\/28395.28439"},{"key":"16_CR4","doi-asserted-by":"publisher","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: STOC 2016, pp. 684\u2013697. ACM (2016). https:\/\/doi.org\/10.1145\/2897518.2897542, preprint of full version at arXiv:1512.03547v2 [cs.DS]","DOI":"10.1145\/2897518.2897542"},{"key":"16_CR5","doi-asserted-by":"publisher","unstructured":"Babai, L., Codenotti, P., Grochow, J.A., Qiao, Y.: Code equivalence and group isomorphism. In: SODA 2011, pp. 1395\u20131408. SIAM (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.107","DOI":"10.1137\/1.9781611973082.107"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-31594-7_5","volume-title":"Automata, Languages, and Programming","author":"L Babai","year":"2012","unstructured":"Babai, L., Codenotti, P., Qiao, Y.: Polynomial-time isomorphism test for groups with no abelian normal subgroups. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 51\u201362. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_5"},{"key":"16_CR7","doi-asserted-by":"publisher","unstructured":"Babai, L., Szemer\u00e9di, E.: On the complexity of matrix group problems I. In: FOCS 1984, pp. 229\u2013240. IEEE Computer Society (1984). https:\/\/doi.org\/10.1109\/SFCS.1984.715919","DOI":"10.1109\/SFCS.1984.715919"},{"key":"16_CR8","unstructured":"Bennett, H., et al.: Asymptotic improvements to provable algorithms for the code equivalence problem. Cryptology ePrint Archive, Paper 2025\/187 (2025). https:\/\/eprint.iacr.org\/2025\/187, to appear, ISIT 2025"},{"issue":"4","key":"16_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1006\/jsco.1998.0258","volume":"27","author":"HU Besche","year":"1999","unstructured":"Besche, H.U., Eick, B.: Construction of finite groups. J. Symb. Comput. 27(4), 387\u2013404 (1999). https:\/\/doi.org\/10.1006\/jsco.1998.0258","journal-title":"J. Symb. Comput."},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1142\/S0218196702001115","volume":"12","author":"HU Besche","year":"2002","unstructured":"Besche, H.U., Eick, B., O\u2019Brien, E.: A millennium project: constructing small groups. Intern. J. Alg. and Comput 12, 623\u2013644 (2002). https:\/\/doi.org\/10.1142\/S0218196702001115","journal-title":"Intern. J. Alg. and Comput"},{"key":"16_CR11","unstructured":"Brachter, J.: Combinatorial approaches to the group isomorphism problem. Ph.D. thesis, TU Darmstadt (2023). https:\/\/tuprints.ulb.tu-darmstadt.de\/26387\/1\/thesis_brachter.pdf"},{"key":"16_CR12","doi-asserted-by":"publisher","unstructured":"Brachter, J., Schweitzer, P.: On the Weisfeiler\u2013Leman dimension of finite groups. In: Hermanns, H., Zhang, L., Kobayashi, N., Miller, D. (eds.) LICS 2020, pp. 287\u2013300. ACM (2020). https:\/\/doi.org\/10.1145\/3373718.3394786","DOI":"10.1145\/3373718.3394786"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-56287-7_99","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"H Buhrman","year":"1992","unstructured":"Buhrman, H., Homer, S.: Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In: Shyamasundar, R. (ed.) FSTTCS 1992. LNCS, vol. 652, pp. 116\u2013127. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-56287-7_99"},{"key":"16_CR14","doi-asserted-by":"publisher","unstructured":"Cai, J.Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389\u2013410 (1992). https:\/\/doi.org\/10.1007\/BF01305232, originally appeared in SFCS 1989","DOI":"10.1007\/BF01305232"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0747-7171(02)00133-5","volume":"35","author":"JJ Cannon","year":"2003","unstructured":"Cannon, J.J., Holt, D.F.: Automorphism group computation and isomorphism testing in finite groups. J. Symb. Comput. 35, 241\u2013267 (2003). https:\/\/doi.org\/10.1016\/S0747-7171(02)00133-5","journal-title":"J. Symb. Comput."},{"key":"16_CR16","doi-asserted-by":"publisher","unstructured":"Chattopadhyay, A., Tor\u00e1n, J., Wagner, F.: Graph isomorphism is not $$\\text{AC}^0$$-reducible to group isomorphism. ACM Trans. Comput. Theory 5(4), Article no. 13 (2013). https:\/\/doi.org\/10.1145\/2540088, preliminary version appeared in FSTTCS 2010; ECCC Tech. Report TR10-117","DOI":"10.1145\/2540088"},{"key":"16_CR17","unstructured":"Codenotti, P.: Testing isomorphism of combinatorial and algebraic structures. Ph.D. thesis, University of Chicago (2011). https:\/\/people.cs.uchicago.edu\/~laci\/students\/codenotti.pdf"},{"key":"16_CR18","doi-asserted-by":"publisher","unstructured":"Collins, N.A., Grochow, J.A., Levet, M., Wei\u00df, A.: Constant depth circuit complexity for generating quasigroups. In: Hauenstein, J.D., Lee, W., Chen, S. (eds.) Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, ISSAC 2024, Raleigh, NC, USA, 16\u201319 July 2024, pp. 198\u2013207. ACM (2024). https:\/\/doi.org\/10.1145\/3666000.3669691","DOI":"10.1145\/3666000.3669691"},{"issue":"03","key":"16_CR19","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1142\/S0218196724500103","volume":"34","author":"NA Collins","year":"2024","unstructured":"Collins, N.A., Levet, M.: Count-free Weisfeiler-Leman and group isomorphism. Int. J. Algebra Comput. 34(03), 283\u2013330 (2024). https:\/\/doi.org\/10.1142\/S0218196724500103","journal-title":"Int. J. Algebra Comput."},{"key":"16_CR20","doi-asserted-by":"publisher","unstructured":"Dietrich, H., Wilson, J.B.: Group isomorphism is nearly-linear time for most orders. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 457\u2013467 (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00053","DOI":"10.1109\/FOCS52979.2021.00053"},{"issue":"5","key":"16_CR21","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1081\/AGB-120003468","volume":"30","author":"B Eick","year":"2002","unstructured":"Eick, B., Leedham-Green, C.R., O\u2019Brien, E.A.: Constructing automorphism groups of $$p$$-groups. Comm. Algebra 30(5), 2271\u20132295 (2002). https:\/\/doi.org\/10.1081\/AGB-120003468","journal-title":"Comm. Algebra"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Felsch, V., Neub\u00fcser, J.: On a programme for the determination of the automorphism group of a finite group. In: Computational Problems in Abstract Algebra (Proceedings of the Conference, Oxford, 1967), pp. 59\u201360 (1970)","DOI":"10.1016\/B978-0-08-012975-4.50011-4"},{"key":"16_CR23","unstructured":"Grochow, J.A., Johnson, D., Levet, M.: On the complexity of identifying groups without abelian normal subgroups: parallel, first order, and GI-hardness. arXiv:2504.19777 [cs.CC] (2025)"},{"key":"16_CR24","doi-asserted-by":"publisher","unstructured":"Grochow, J.A., Levet, M.: On the descriptive complexity of groups without abelian normal subgroups (extended abstract). In: Achilleos, A., Monica, D.D. (eds.) Proceedings of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2023, Udine, Italy, 18-20th September 2023. EPTCS, vol.\u00a0390, pp. 185\u2013202 (2023). https:\/\/doi.org\/10.4204\/EPTCS.390.12","DOI":"10.4204\/EPTCS.390.12"},{"key":"16_CR25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-031-43587-4_17","volume-title":"FCT 2023","author":"JA Grochow","year":"2023","unstructured":"Grochow, J.A., Levet, M.: On the parallel complexity of group isomorphism via Weisfeiler-Leman. In: Fernau, H., Jansen, K. (eds.) FCT 2023. LNCS, vol. 14292, pp. 234\u2013247. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43587-4_17"},{"issue":"4","key":"16_CR26","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1137\/15M1009767","volume":"46","author":"JA Grochow","year":"2017","unstructured":"Grochow, J.A., Qiao, Y.: Algorithms for group isomorphism via group extensions and cohomology. SIAM J. Comput. 46(4), 1153\u20131216 (2017). https:\/\/doi.org\/10.1137\/15M1009767","journal-title":"SIAM J. Comput."},{"key":"16_CR27","doi-asserted-by":"publisher","unstructured":"Grochow, J.A., Qiao, Y.: On $$p$$-group isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors. ACM Trans. Comput. Theory 16(1), 2:1\u20132:39 (2024). https:\/\/doi.org\/10.1145\/3625308, extended abstract at CCC 2021; preliminary version was part of arXiv:1907.00309","DOI":"10.1145\/3625308"},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective","author":"N Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.: Describing graphs: a first-order approach to graph canonization. In: Selman, A.L. (ed.) Complexity Theory Retrospective, pp. 59\u201381. Springer, New York (1990)"},{"issue":"4","key":"16_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR30","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01200427","volume":"2","author":"J K\u00f6bler","year":"1992","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: Graph isomorphism is low for pp. Comput. Complex. 2, 301\u2013330 (1992). https:\/\/doi.org\/10.1007\/BF01200427","journal-title":"Comput. Complex."},{"key":"16_CR31","unstructured":"Le\u00a0Gall, F., Rosenbaum, D.J.: On the group and color isomorphism problems. arXiv:1609.08253 [cs.CC] (2016)"},{"key":"16_CR32","doi-asserted-by":"publisher","unstructured":"Levet, M., Rombach, P., Sieger, N.: Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman. In: Bodlaender, H.L. (ed.) 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0294, pp. 32:1\u201332:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2024.32","DOI":"10.4230\/LIPIcs.SWAT.2024.32"},{"key":"16_CR33","doi-asserted-by":"publisher","unstructured":"Luks, E.: Permutation groups and polynomial-time computation. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 11 (1993). https:\/\/doi.org\/10.1090\/dimacs\/011\/11","DOI":"10.1090\/dimacs\/011\/11"},{"key":"16_CR34","doi-asserted-by":"publisher","unstructured":"Luks, E.M.: Parallel algorithms for permutation groups and graph isomorphism. In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27\u201329 October 1986, pp. 292\u2013302. IEEE Computer Society (1986). https:\/\/doi.org\/10.1109\/SFCS.1986.39","DOI":"10.1109\/SFCS.1986.39"},{"key":"16_CR35","doi-asserted-by":"publisher","unstructured":"Miller, G.L.: On the $$n^{\\log n}$$ isomorphism technique (a preliminary report). In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 51\u201358. Association for Computing Machinery, New York (1978). https:\/\/doi.org\/10.1145\/800133.804331","DOI":"10.1145\/800133.804331"},{"issue":"5","key":"16_CR36","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1109\/18.623157","volume":"43","author":"E Petrank","year":"1997","unstructured":"Petrank, E., Roth, R.: Is code equivalence easy to decide? IEEE Trans. Info. Theory 43(5), 1602\u20131604 (1997). https:\/\/doi.org\/10.1109\/18.623157","journal-title":"IEEE Trans. Info. Theory"},{"issue":"3","key":"16_CR37","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312\u2013323 (1988). https:\/\/doi.org\/10.1016\/0022-0000(88)90010-4","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR38","unstructured":"Tang, B.: Towards understanding satisfiability, group isomorphism and their connections. Ph.D. thesis, Tsinghua University (2013)"},{"issue":"5","key":"16_CR39","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.1137\/S009753970241096X","volume":"33","author":"J Tor\u00e1n","year":"2004","unstructured":"Tor\u00e1n, J.: On the hardness of graph isomorphism. SIAM J. Comput. 33(5), 1093\u20131108 (2004). https:\/\/doi.org\/10.1137\/S009753970241096X","journal-title":"SIAM J. Comput."},{"issue":"19","key":"16_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2019.v015a019","volume":"15","author":"JB Wilson","year":"2019","unstructured":"Wilson, J.B.: The threshold for subgroup profiles to agree is logarithmic. Theory Comput. 15(19), 1\u201325 (2019). https:\/\/doi.org\/10.4086\/toc.2019.v015a019","journal-title":"Theory Comput."},{"key":"16_CR41","unstructured":"Wilson, J.B.: Isomorphism testing of permutation groups. Pers. Commun. (2024)"},{"issue":"4","key":"16_CR42","doi-asserted-by":"publisher","first-page":"1426","DOI":"10.1007\/BF02104746","volume":"29","author":"VN Zemlyachenko","year":"1985","unstructured":"Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Soviet Math. 29(4), 1426\u20131481 (1985). https:\/\/doi.org\/10.1007\/BF02104746","journal-title":"J. Soviet Math."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:42Z","timestamp":1758498342000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}