{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:24Z","timestamp":1770921384786,"version":"3.50.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-17801-5_3","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:57Z","timestamp":1770918777000},"page":"31-45","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear Time Algorithms for\u00a0Abelian Group Isomorphism and\u00a0Basis Construction"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7356-7824","authenticated-orcid":false,"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 684\u2013697 (2016). https:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"3_CR2","doi-asserted-by":"publisher","unstructured":"Babai, L., Codenotti, P., Grochow, J.A., Qiao, Y.: Code equivalence and group isomorphism. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, 23\u201325 January 2011, pp. 1395\u20131408 (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.107","DOI":"10.1137\/1.9781611973082.107"},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Babai, L., Qiao, Y.: Polynomial-time isomorphism test for groups with abelian sylow towers. In: 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, 29th February\u20133rd March 2012, pp. 453\u2013464 (2012). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2012.453","DOI":"10.4230\/LIPICS.STACS.2012.453"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Babai, L., Szemer\u00e9di, E.: On the complexity of matrix group problems I. In: 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24\u201326 October 1984, pp. 229\u2013240 (1984). https:\/\/doi.org\/10.1109\/SFCS.1984.715919","DOI":"10.1109\/SFCS.1984.715919"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/11555964_5","volume-title":"Computer Algebra in Scientific Computing","author":"M Borges-Quintana","year":"2005","unstructured":"Borges-Quintana, M., Borges-Trenard, M.A., Mart\u00ednez-Moro, E.: On the use of Gr\u00f6bner bases for computing the structure of finite abelian groups. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 52\u201364. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11555964_5"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Bshouty, N.H.: Sublinear time algorithms for abelian group isomorphism and basis construction. CoRR abs\/2504.02387 (2025). https:\/\/doi.org\/10.48550\/ARXIV.2504.02387","DOI":"10.48550\/ARXIV.2504.02387"},{"issue":"252","key":"3_CR7","doi-asserted-by":"publisher","first-page":"2017","DOI":"10.1090\/S0025-5718-05-01740-0","volume":"74","author":"J Buchmann","year":"2005","unstructured":"Buchmann, J., Schmidt, A.: Computing the structure of a finite abelian group. Math. Comput. 74(252), 2017\u20132026 (2005). https:\/\/doi.org\/10.1090\/S0025-5718-05-01740-0","journal-title":"Math. Comput."},{"issue":"32","key":"3_CR8","doi-asserted-by":"publisher","first-page":"4110","DOI":"10.1016\/J.TCS.2010.06.011","volume":"412","author":"L Chen","year":"2011","unstructured":"Chen, L., Fu, B.: Linear and sublinear time algorithms for the basis of abelian groups. Theor. Comput. Sci. 412(32), 4110\u20134122 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2010.06.011","journal-title":"Theor. Comput. Sci."},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"Chen, Z., Grochow, J.A., Qiao, Y., Tang, G., Zhang, C.: On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups. In: 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, 30 January\u20132 February 2024, pp. 31:1\u201331:23 (2024). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2024.31","DOI":"10.4230\/LIPICS.ITCS.2024.31"},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Dietrich, H., Wilson, J.B.: Group isomorphism is nearly-linear time for most orders. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, 7\u201310 February 2022, pp. 457\u2013467 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00053","DOI":"10.1109\/FOCS52979.2021.00053"},{"issue":"4","key":"3_CR11","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/S10878-011-9445-8","volume":"26","author":"FL Gall","year":"2013","unstructured":"Gall, F.L., Yoshida, Y.: Property testing for cyclic groups and beyond. J. Comb. Optim. 26(4), 636\u2013654 (2013). https:\/\/doi.org\/10.1007\/S10878-011-9445-8","journal-title":"J. Comb. Optim."},{"issue":"2","key":"3_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0022-0000(91)90012-T","volume":"42","author":"MH Garzon","year":"1991","unstructured":"Garzon, M.H., Zalcstein, Y.: On isomorphism testing of a class of 2-nilpotent groups. J. Comput. Syst. Sci. 42(2), 237\u2013248 (1991). https:\/\/doi.org\/10.1016\/0022-0000(91)90012-T","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"3_CR13","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":"3_CR14","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","DOI":"10.1145\/3625308"},{"issue":"4","key":"3_CR15","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(85)90052-3","volume":"20","author":"CS Iliopoulos","year":"1985","unstructured":"Iliopoulos, C.S.: Analysis of algorithms on problems in general abelian groups. Inf. Process. Lett. 20(4), 215\u2013220 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90052-3","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"3_CR16","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/0218045","volume":"18","author":"CS Iliopoulos","year":"1989","unstructured":"Iliopoulos, C.S.: Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the hermite and smith normal forms of an integer matrix. SIAM J. Comput. 18(4), 658\u2013669 (1989). https:\/\/doi.org\/10.1137\/0218045","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR17","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0208040","volume":"8","author":"R Kannan","year":"1979","unstructured":"Kannan, R., Bachem, A.: Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM J. Comput. 8(4), 499\u2013507 (1979). https:\/\/doi.org\/10.1137\/0208040","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1142\/S1793830911001401","volume":"3","author":"G Karagiorgos","year":"2011","unstructured":"Karagiorgos, G., Poulakis, D.: Efficient algorithms for the basis of finite abelian groups. Discret. Math. Algorithms Appl. 3(4), 537\u2013552 (2011). https:\/\/doi.org\/10.1142\/S1793830911001401","journal-title":"Discret. Math. Algorithms Appl."},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-642-22685-4_40","volume-title":"Computing and Combinatorics","author":"G Karagiorgos","year":"2011","unstructured":"Karagiorgos, G., Poulakis, D.: Linear time algorithms for the basis of abelian groups. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol. 6842, pp. 456\u2013466. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22685-4_40"},{"issue":"6","key":"3_CR20","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1016\/j.jcss.2007.03.013","volume":"73","author":"T Kavitha","year":"2007","unstructured":"Kavitha, T.: Linear time algorithms for abelian group isomorphism and related problems. J. Comput. Syst. Sci. 73(6), 986\u2013996 (2007). https:\/\/doi.org\/10.1016\/j.jcss.2007.03.013","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"3_CR21","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1137\/S0036144503439190","volume":"46","author":"N Koblitz","year":"2004","unstructured":"Koblitz, N., Menezes, A.: A survey of public-key cryptosystems. SIAM Rev. 46(4), 599\u2013634 (2004). https:\/\/doi.org\/10.1137\/S0036144503439190","journal-title":"SIAM Rev."},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Miller, G.L.: On the n log n isomorphism technique: a preliminary report. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 1\u20133 May 1978, pp. 51\u201358 (1978). https:\/\/doi.org\/10.1145\/800133.804331","DOI":"10.1145\/800133.804331"},{"key":"3_CR23","unstructured":"Lipton, R.J., Snyder, L., Zalcstein, Y.: The Complexity of Word and Isomorphism Problems for Finite Groups. John Hopkins (1976)"},{"key":"3_CR24","unstructured":"Rosenbaum, D.J.: Bidirectional collision detection and faster deterministic isomorphism testing. CoRR abs\/1304.3935 (2013). http:\/\/arxiv.org\/abs\/1304.3935"},{"key":"3_CR25","unstructured":"Savage, C.: An $$o(n^2)$$ algorithm for abelian group isomorphism. Technical report, North Carolina State University (1980)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Teske, E.: The Pohlig-Hellman method generalized for group structure computation. J. Symb. Comput. 27(6), 521\u2013534 (1999)","DOI":"10.1006\/jsco.1999.0279"},{"key":"3_CR27","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001), see Section\u00a02.4, \u201cYao\u2019s Minimax Principle\u201d, pp.\u00a024\u201326"},{"issue":"1","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/JCSS.1996.0045","volume":"53","author":"N Vikas","year":"1996","unstructured":"Vikas, N.: An $$o(n)$$ algorithm for abelian $$p$$-group isomorphism and an $$o(n \\log n)$$ algorithm for abelian group isomorphism. J. Comput. Syst. Sci. 53(1), 1\u20139 (1996). https:\/\/doi.org\/10.1006\/JCSS.1996.0045","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR29","first-page":"281","volume":"10","author":"AC Yao","year":"1981","unstructured":"Yao, A.C.: Probabilistic computations: toward a unified measure of complexity. SIAM J. Comput. 10(2), 281\u2013290 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:59Z","timestamp":1770918779000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}