{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:30:08Z","timestamp":1775097008945,"version":"3.50.1"},"reference-count":98,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"name":"J. A. Grochow\u2019s NSF","award":["CISE-2047756"],"award-info":[{"award-number":["CISE-2047756"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p> We investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler\u2013Leman Version I algorithm for groups [J.\u00a0Brachter and P.\u00a0Schweitzer, On the Weisfeiler\u2013Leman dimension of finite groups, in 35th Annual ACM\/IEEE Symp. Logic in Computer Science, eds. H.\u00a0Hermanns, L.\u00a0Zhang, N.\u00a0Kobayashi and D.\u00a0Miller, Saarbrucken, Germany, July 8\u201311, 2020 (ACM, 2020), pp.\u00a0287\u2013300, doi:10.1145\/3373718.3394786] in tandem with bounded non-determinism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. These families include: <\/jats:p><jats:p> \u2022 Direct products of non-Abelian simple groups. \u2022 Coprime extensions, where the normal Hall subgroup is Abelian and the complement is an [Formula: see text]-generated solvable group with solvability class [Formula: see text]. This notably includes instances where the complement is an [Formula: see text]-generated nilpotent group. This problem was previously known to be in [Formula: see text] [Y.\u00a0Qiao, J.\u00a0M.\u00a0N.\u00a0Sarma and B.\u00a0Tang, On isomorphism testing of groups with normal Hall subgroups, in Proc. 28th Symp. Theoretical Aspects of Computer Science, Dagstuhl Castle, Leibniz Center for Informatics, 2011), pp.\u00a0567\u2013578, doi:10.4230\/LIPIcs. STACS.2011.567], and the complexity was recently improved to [Formula: see text] [J.\u00a0A. Grochow and M.\u00a0Levet, On the parallel complexity of group isomorphism via Weisfeiler\u2013Leman, in 24th Int. Symp. Fundamentals of Computation Theory, eds. H.\u00a0Fernau and K.\u00a0Jansen, Lecture Notes in Computer Science, Vol.\u00a014292, September 18\u201321, 2023, Trier, Germany (Springer, 2023), pp.\u00a0234\u2013247]. \u2022 Graphical groups of class 2 and exponent [Formula: see text] [A.\u00a0H.\u00a0Mekler, Stability of nilpotent groups of class 2 and prime exponent, J.\u00a0Symb. Logic 46(4) (1981) 781\u2013788] arising from the CFI and twisted CFI graphs [J.-Y.\u00a0Cai, M.\u00a0F\u00fcrer and N.\u00a0 Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389\u2013410], respectively. In particular, our work improves upon previous results of Brachter and Schweitzer [On the Weisfeiler\u2013Leman dimension of finite groups, in 35th Annual ACM\/IEEE Symp. Logic in Computer Science, eds. H.\u00a0Hermanns, L.\u00a0Zhang, N.\u00a0Kobayashi and D.\u00a0Miller, Saarbrucken, Germany, July 8\u201311, 2020 (ACM, 2020), pp.\u00a0287\u2013300, doi:10.1145\/3373718.3394786]. <\/jats:p><jats:p> Notably, each of these families was previously known to be identified by the counting variant of the more powerful Weisfeiler\u2013Leman Version II algorithm. We finally show that the q-ary count-free pebble game is unable to even distinguish Abelian groups. This extends the result of Grochow and Levet (ibid), who established the result in the case of [Formula: see text]. The general theme is that some counting appears necessary to place [Formula: see text] into [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218196724500103","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T08:10:00Z","timestamp":1708675800000},"page":"283-330","source":"Crossref","is-referenced-by-count":5,"title":["Count-free Weisfeiler\u2013Leman and group isomorphism"],"prefix":"10.1142","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2694-4080","authenticated-orcid":false,"given":"Nathaniel A.","family":"Collins","sequence":"first","affiliation":[{"name":"Department of Mathematics, Colorado State University, Fort Collins, Colorado, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1992-3175","authenticated-orcid":false,"given":"Michael","family":"Levet","sequence":"additional","affiliation":[{"name":"Department of Computer Science, College of Charleston, Charleston, SC, USA"}]}],"member":"219","published-online":{"date-parts":[[2024,4,3]]},"reference":[{"key":"S0218196724500103BIB001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"S0218196724500103BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103461"},{"key":"S0218196724500103BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.04.002"},{"key":"S0218196724500103BIB004","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"S0218196724500103BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00015-1"},{"key":"S0218196724500103BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.02.002"},{"key":"S0218196724500103BIB008","first-page":"684","volume-title":"Proc. 48th Annual ACM SIGACT Symp. Theory of Computing","author":"Babai L.","year":"2016"},{"key":"S0218196724500103BIB009","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.107"},{"key":"S0218196724500103BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_5"},{"key":"S0218196724500103BIB011","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1998.0258"},{"key":"S0218196724500103BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/164081.164105"},{"key":"S0218196724500103BIB013","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196702001115"},{"key":"S0218196724500103BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56287-7_99"},{"key":"S0218196724500103BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(89)80067-8"},{"key":"S0218196724500103BIB017","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1764"},{"key":"S0218196724500103BIB018","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28439"},{"key":"S0218196724500103BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90017-V"},{"key":"S0218196724500103BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2016.12.007"},{"key":"S0218196724500103BIB021","unstructured":"L. Babai and  Y. Qiao ,  Polynomial-time isomorphism test for groups with Abelian Sylow towers, in  29th Int. Symp. Theoretical Aspects of Computer Science,  Springer Lecture Notes in Computer Science, Vol.  6651  (Springer,  2012), pp. 453\u2013464.  https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2012.453"},{"key":"S0218196724500103BIB022","first-page":"287","volume-title":"35th Annual ACM\/IEEE Symp. Logic in Computer Science","author":"Brachter J.","year":"2020"},{"key":"S0218196724500103BIB023","first-page":"1","volume-title":"Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing","volume":"244","author":"Brachter J.","year":"2022"},{"key":"S0218196724500103BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488642"},{"key":"S0218196724500103BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"S0218196724500103BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(02)00133-5"},{"key":"S0218196724500103BIB028","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488643"},{"key":"S0218196724500103BIB029","doi-asserted-by":"publisher","DOI":"10.1145\/2540088"},{"key":"S0218196724500103BIB030","first-page":"4891","volume":"258","author":"Dedecker P.","year":"1964","journal-title":"C. R. Acad. Sci. Paris"},{"key":"S0218196724500103BIB031","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.16"},{"key":"S0218196724500103BIB032","series-title":"Leibniz International Proceedings in Informatics","first-page":"145","volume-title":"Annual Conf. Foundations of Software Technology and Theoretical Computer Science","volume":"4","author":"Datta S.","year":"2009"},{"key":"S0218196724500103BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19955-5_8"},{"key":"S0218196724500103BIB034","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00053"},{"key":"S0218196724500103BIB035","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"S0218196724500103BIB036","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"S0218196724500103BIB037","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"S0218196724500103BIB038","doi-asserted-by":"publisher","DOI":"10.1081\/AGB-120003468"},{"key":"S0218196724500103BIB039","doi-asserted-by":"publisher","DOI":"10.1145\/3132720"},{"key":"S0218196724500103BIB040","doi-asserted-by":"publisher","DOI":"10.2307\/2272945"},{"key":"S0218196724500103BIB041","first-page":"35","volume":"1","author":"Fra\u00efss\u00e9 R.","year":"1955","journal-title":"Publ. Sci. Univ. Alger. S\u00e9r. A"},{"key":"S0218196724500103BIB042","series-title":"Leibniz International Proceedings in Informatics","first-page":"1","volume-title":"46th Int. Colloquium Automata, Languages, and Programming","volume":"132","author":"Grohe M.","year":"2019"},{"key":"S0218196724500103BIB043","series-title":"Leibniz International Proceedings in Informatics","first-page":"1","volume-title":"48th Int. Colloquium Automata, Languages, and Programming","volume":"198","author":"Grohe M.","year":"2021"},{"key":"S0218196724500103BIB044","series-title":"Udine, Electronic Proceedings in Theoretical Computer Science","first-page":"185","volume-title":"Proc. 14th Int. Symp. Games, Automata, Logics, and Formal Verification","volume":"390","author":"Grochow J. A."},{"key":"S0218196724500103BIB045","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-43587-4_17"},{"key":"S0218196724500103BIB046","doi-asserted-by":"publisher","DOI":"10.1145\/3453943"},{"key":"S0218196724500103BIB047","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196710006047"},{"key":"S0218196724500103BIB048","first-page":"578","volume-title":"26th Int. Symp. Algorithms and Computation","author":"Grochow J. A."},{"key":"S0218196724500103BIB049","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009767"},{"key":"S0218196724500103BIB051","doi-asserted-by":"crossref","unstructured":"M. Grohe , Descriptive Complexity, Canonisation, and Definable Graph Structure Theory,  Lecture Notes in Logic, Vol.  47 ( Cambridge University Press,  Cambridge,  2017).  https:\/\/doi.org\/10.1017\/9781139028868","DOI":"10.1017\/9781139028868"},{"key":"S0218196724500103BIB052","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_2"},{"key":"S0218196724500103BIB053","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90070-5"},{"key":"S0218196724500103BIB054","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"S0218196724500103BIB055","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035216"},{"key":"S0218196724500103BIB056","doi-asserted-by":"publisher","DOI":"10.1007\/BF01238631"},{"key":"S0218196724500103BIB057","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103404"},{"key":"S0218196724500103BIB058","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"S0218196724500103BIB059","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"S0218196724500103BIB060","doi-asserted-by":"publisher","DOI":"10.1515\/GMJ.1997.313"},{"key":"S0218196724500103BIB061","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"S0218196724500103BIB062","doi-asserted-by":"publisher","DOI":"10.1137\/18M1165682"},{"key":"S0218196724500103BIB063","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/092"},{"key":"S0218196724500103BIB064","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00042-4"},{"key":"S0218196724500103BIB065","first-page":"776","volume-title":"Proc. 34th Annual ACM Symp. Theory of Computing","author":"Jackson J. C.","year":"2002"},{"key":"S0218196724500103BIB066","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.013"},{"key":"S0218196724500103BIB068","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_49"},{"key":"S0218196724500103BIB069","doi-asserted-by":"publisher","DOI":"10.1145\/3333003"},{"key":"S0218196724500103BIB070","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200427"},{"key":"S0218196724500103BIB071","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79709-8_23"},{"key":"S0218196724500103BIB072","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"S0218196724500103BIB073","series-title":"Leibniz International Proceedings in Informatics","first-page":"625","volume-title":"26th Proc. Symp. Theoretical Aspects of Computer Science","volume":"3","author":"Le Gall F.","year":"2009"},{"key":"S0218196724500103BIB075","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"S0218196724500103BIB076","doi-asserted-by":"publisher","DOI":"10.1145\/3572918"},{"key":"S0218196724500103BIB077","first-page":"400","volume-title":"Proc. 24th Annual ACM Symp. Theory of Computing","author":"Lindell S.","year":"1992"},{"key":"S0218196724500103BIB078","first-page":"463","volume-title":"2017 IEEE 58th Annual Symp. Foundations of Computer Science","author":"Li Y.","year":"2017"},{"key":"S0218196724500103BIB080","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"S0218196724500103BIB082","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"S0218196724500103BIB083","doi-asserted-by":"publisher","DOI":"10.2307\/2273227"},{"key":"S0218196724500103BIB084","first-page":"51","volume-title":"Proc. 10th Annual ACM Symp. Theory of Computing","author":"Miller G. L.","year":"1978"},{"key":"S0218196724500103BIB085","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"S0218196724500103BIB086","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188900"},{"key":"S0218196724500103BIB087","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1563-2"},{"key":"S0218196724500103BIB088","first-page":"1","volume-title":"48th Int. Symp. Mathematical Foundations of Computer Science","volume":"272","author":"Pago B."},{"key":"S0218196724500103BIB089","series-title":"Dagstuhl Castle","first-page":"567","volume-title":"Proc. 28th Symp. Theoretical Aspects of Computer Science","author":"Qiao Y.","year":"2011"},{"key":"S0218196724500103BIB090","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-0128-8"},{"key":"S0218196724500103BIB091","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02261-6_28"},{"key":"S0218196724500103BIB094","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90010-4"},{"key":"S0218196724500103BIB096","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"S0218196724500103BIB098","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002987X"},{"key":"S0218196724500103BIB100","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(81)90305-7"},{"key":"S0218196724500103BIB101","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970241096X"},{"key":"S0218196724500103BIB102","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_58"},{"key":"S0218196724500103BIB103","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-009-9074-9"},{"key":"S0218196724500103BIB104","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0045"},{"key":"S0218196724500103BIB105","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"S0218196724500103BIB106","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20712-9_16"},{"key":"S0218196724500103BIB107","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0089374"},{"key":"S0218196724500103BIB108","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0007"},{"key":"S0218196724500103BIB109","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a019"},{"key":"S0218196724500103BIB111","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00014-I"},{"key":"S0218196724500103BIB112","doi-asserted-by":"publisher","DOI":"10.1007\/BF02104746"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196724500103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T01:49:09Z","timestamp":1716860949000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196724500103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,3]]},"references-count":98,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["10.1142\/S0218196724500103"],"URL":"https:\/\/doi.org\/10.1142\/s0218196724500103","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,3]]}}}