{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:44:35Z","timestamp":1740120275167,"version":"3.37.3"},"reference-count":29,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"crossref","award":["17-11-0117"],"award-info":[{"award-number":["17-11-0117"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DFG-project","award":["DI 435\/7-1"],"award-info":[{"award-number":["DI 435\/7-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:p> Recently, Macdonald et al. showed that many algorithmic problems for finitely generated nilpotent groups including computation of normal forms, the subgroup membership problem, the conjugacy problem, and computation of subgroup presentations can be done in [Formula: see text]. Here, we follow their approach and show that all these problems are complete for the uniform circuit class [Formula: see text] \u2014 even if an [Formula: see text]-generated nilpotent group of class at most [Formula: see text] is part of the input but [Formula: see text] and [Formula: see text] are fixed constants. In particular, unary encoded systems of a bounded number of linear equations over the integers can be solved in [Formula: see text]. In order to solve these problems in [Formula: see text], we show that the unary version of the extended gcd problem (compute greatest common divisors and express them as linear combinations) is in [Formula: see text]. Moreover, if we allow a certain binary representation of the inputs, then the word problem and computation of normal forms is still in uniform [Formula: see text], while all the other problems we examine are shown to be [Formula: see text]-Turing-reducible to the binary extended gcd problem. <\/jats:p>","DOI":"10.1142\/s0218196722500382","type":"journal-article","created":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T09:32:55Z","timestamp":1650274375000},"page":"895-928","source":"Crossref","is-referenced-by-count":2,"title":["Parallel complexity for nilpotent groups"],"prefix":"10.1142","volume":"32","author":[{"given":"Alexei","family":"Myasnikov","sequence":"first","affiliation":[{"name":"Stevens Institute of Technology, 1 Castle Point Terrace, Hoboken, NJ 07030, USA"}]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Stuttgart, FMI, Universit\u00e4tsstra\u00dfe 38, 70569 Stuttgart, Germany"}]}],"member":"219","published-online":{"date-parts":[[2022,4,18]]},"reference":[{"key":"S0218196722500382BIB001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0172925-5"},{"key":"S0218196722500382BIB002","doi-asserted-by":"publisher","DOI":"10.2307\/1970103"},{"key":"S0218196722500382BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456932"},{"key":"S0218196722500382BIB005","first-page":"128","volume":"18","author":"Elberfeld M.","year":"2011","journal-title":"Electron. Colloq. Comput. Complex."},{"issue":"2","key":"S0218196722500382BIB006","first-page":"99","volume":"9","author":"Garreta A.","year":"2017","journal-title":"Groups Complex. Cryptol."},{"key":"S0218196722500382BIB007","series-title":"Queen Mary College Mathematics Notes","volume-title":"The Edmonton Notes on Nilpotent Groups","author":"Hall P.","year":"1969"},{"key":"S0218196722500382BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_9"},{"key":"S0218196722500382BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"S0218196722500382BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9964-6"},{"key":"S0218196722500382BIB011","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1007\/BF02219648","volume":"8","author":"Kargapolov M. I.","year":"1969","journal-title":"Algebra Log."},{"key":"S0218196722500382BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21398-9_19"},{"key":"S0218196722500382BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49381-6_27"},{"key":"S0218196722500382BIB014","first-page":"105","volume-title":"Computational Group Theory","author":"Laue R.","year":"1984"},{"key":"S0218196722500382BIB015","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157000000127"},{"key":"S0218196722500382BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/322017.322031"},{"key":"S0218196722500382BIB017","series-title":"LIPIcs","first-page":"43:1","volume-title":"Proc. 44th Int. Symp. on Mathematical Foundations of Computer Science","volume":"138","author":"Lohrey M.","year":"2019"},{"key":"S0218196722500382BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S021819671950019X"},{"key":"S0218196722500382BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58691-1_56"},{"key":"S0218196722500382BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9849-2"},{"key":"S0218196722500382BIB023","doi-asserted-by":"publisher","DOI":"10.4064\/fm-59-2-137-152"},{"key":"S0218196722500382BIB024","doi-asserted-by":"publisher","DOI":"10.1515\/jgth-2014-0022"},{"key":"S0218196722500382BIB025","doi-asserted-by":"publisher","DOI":"10.1515\/jgth-2016-0506"},{"key":"S0218196722500382BIB026","first-page":"23:1","volume-title":"Proc. 42nd Int. Symp. Mathematical Foundations of Computer Science","author":"Myasnikov A. G.","year":"2017"},{"key":"S0218196722500382BIB027","first-page":"1","volume":"44","author":"Novikov P. S.","year":"1955","journal-title":"Trudy Mat. Inst. Steklov"},{"key":"S0218196722500382BIB030","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087610"},{"key":"S0218196722500382BIB031","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565953"},{"key":"S0218196722500382BIB032","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574702"},{"key":"S0218196722500382BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"S0218196722500382BIB034","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0080152"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196722500382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T08:35:23Z","timestamp":1655886923000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196722500382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,18]]},"references-count":29,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["10.1142\/S0218196722500382"],"URL":"https:\/\/doi.org\/10.1142\/s0218196722500382","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2022,4,18]]}}}