{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:32Z","timestamp":1740109412311,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,2,12]],"date-time":"2018-02-12T00:00:00Z","timestamp":1518393600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00224-018-9849-2","type":"journal-article","created":{"date-parts":[[2018,2,11]],"date-time":"2018-02-11T22:19:41Z","timestamp":1518387581000},"page":"809-832","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC0"],"prefix":"10.1007","volume":"63","author":[{"given":"Alexei","family":"Miasnikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svetla","family":"Vassileva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,12]]},"reference":[{"issue":"3","key":"9849_CR1","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"DAM Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC1. J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990). \n                    https:\/\/doi.org\/10.1016\/0022-0000(90)90022-D","journal-title":"J. Comput. Syst. Sci."},{"key":"9849_CR2","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1515\/gcc-2016-0012","volume":"4","author":"MJ Craven","year":"2012","unstructured":"Craven, M.J., Jimbo, H.C.: Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography. Groups Complex. Cryptol. 4, 135\u2013165 (2012). \n                    https:\/\/doi.org\/10.1515\/gcc-2016-0012","journal-title":"Groups Complex. Cryptol."},{"issue":"1","key":"9849_CR3","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M Dehn","year":"1911","unstructured":"Dehn, M.: \u00dcber unendliche diskontinuierliche Gruppen. Math. Ann. 71(1), 116\u2013144 (1911). \n                    https:\/\/doi.org\/10.1007\/BF01456932","journal-title":"Math. Ann."},{"key":"9849_CR4","doi-asserted-by":"crossref","unstructured":"Diekert, V., Myasnikov, A. G., Wei\u00df, A.: Conjugacy in baumslag\u2019s group, generic case complexity, and division in power circuits. In: Latin American Theoretical Informatics Symposium, pp 1\u201312 (2014)","DOI":"10.1007\/978-3-642-54423-1_1"},{"key":"9849_CR5","first-page":"199","volume":"1","author":"D Grigoriev","year":"2009","unstructured":"Grigoriev, D., Shpilrain, V.: Authentication from matrix conjugation. Groups Complex. Cryptol. 1, 199\u2013205 (2009)","journal-title":"Groups Complex. Cryptol."},{"issue":"9","key":"9849_CR6","doi-asserted-by":"publisher","first-page":"6189","DOI":"10.1090\/tran\/6880","volume":"369","author":"F Gul","year":"2017","unstructured":"Gul, F., Sohrabi, M., Ushakov, A.: Magnus embedding and algorithmic properties of groups F\/N\n                           (d). Trans. Amer. Math. Soc. 369(9), 6189\u20136206 (2017). \n                    https:\/\/doi.org\/10.1090\/tran\/6880","journal-title":"Trans. Amer. Math. Soc."},{"key":"9849_CR7","doi-asserted-by":"crossref","unstructured":"Hesse, W.: Division is in uniform TC0. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001, Proceedings, Lecture Notes in Computer Science, vol. 2076, pp 104\u2013114. Springer (2001)","DOI":"10.1007\/3-540-48224-5_9"},{"key":"9849_CR8","first-page":"695","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D. A. M.: Uniform constant-depth threshold circuits for division and iterated multiplication. JCSS 65, 695\u2013716 (2002)","journal-title":"JCSS"},{"issue":"6","key":"9849_CR9","first-page":"15","volume":"5","author":"MI Kargapolov","year":"1966","unstructured":"Kargapolov, M. I., Remeslennikov, V. N.: The conjugacy problem for free solvable groups. Algebra i Logika Sem. 5(6), 15\u201325 (1966)","journal-title":"Algebra i Logika Sem."},{"key":"9849_CR10","doi-asserted-by":"publisher","unstructured":"Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.S., Park, C.: New public-key cryptosystem using braid groups. In: Advances in cryptology\u2014CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Computer Science. \n                    https:\/\/doi.org\/10.1007\/3-540-44598-6_10\n                    \n                  , vol. 1880, pp 166\u2013183. Springer, Berlin (2000)","DOI":"10.1007\/3-540-44598-6_10"},{"key":"9849_CR11","doi-asserted-by":"publisher","unstructured":"K\u00f6nig, D., Lohrey, M.: Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica (2017). \n                    https:\/\/doi.org\/10.1007\/s00453-017-0343-z","DOI":"10.1007\/s00453-017-0343-z"},{"issue":"4","key":"9849_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00224-006-1310-2","volume":"40","author":"A Krebs","year":"2007","unstructured":"Krebs, A., Lange, K., Reifferscheid, S.: Characterizing TC0 in terms of infinite groups. Theory Comput. Syst. 40 (4), 303\u2013325 (2007). \n                    https:\/\/doi.org\/10.1007\/s00224-006-1310-2","journal-title":"Theory Comput. Syst."},{"key":"9849_CR13","doi-asserted-by":"publisher","unstructured":"Lange, K., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K., Ibarra, O.H. (eds.) ISAAC 1998, Proceedings, Lecture Notes in Computer Science. \n                    https:\/\/doi.org\/10.1007\/3-540-49381-6_27\n                    \n                  , vol. 1533, pp 247\u2013256. Springer (1998)","DOI":"10.1007\/3-540-49381-6_27"},{"issue":"1","key":"9849_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1006\/inco.1998.2732","volume":"146","author":"A Maciel","year":"1998","unstructured":"Maciel, A., Th\u00e9rien, D.: Threshold circuits of small majority-depth. Inf. Comput. 146(1), 55\u201383 (1998). \n                    https:\/\/doi.org\/10.1006\/inco.1998.2732","journal-title":"Inf. Comput."},{"key":"9849_CR15","doi-asserted-by":"publisher","first-page":"764","DOI":"10.2307\/1968892","volume":"40","author":"W Magnus","year":"1939","unstructured":"Magnus, W.: On a theorem of Marshall Hall. Ann. of Math. (2) 40, 764\u2013768 (1939)","journal-title":"Ann. of Math. (2)"},{"key":"9849_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1090\/S0002-9947-1966-0193130-8","volume":"121","author":"J Matthews","year":"1966","unstructured":"Matthews, J.: The conjugacy problem in wreath products and free metabelian groups. Trans. Amer. Math. Soc. 121, 329\u2013339 (1966)","journal-title":"Trans. Amer. Math. Soc."},{"key":"9849_CR17","volume-title":"On group-theoretic decision problems and their classification, Ann. of Math. Studies, vol. 68","author":"CFIII Miller","year":"1971","unstructured":"Miller, C.F. III: On group-theoretic decision problems and their classification, Ann. of Math. Studies, vol. 68. Princeton University Press, NJ (1971)"},{"issue":"9","key":"9849_CR18","doi-asserted-by":"publisher","first-page":"4655","DOI":"10.1090\/S0002-9947-10-04959-7","volume":"362","author":"A Myasnikov","year":"2010","unstructured":"Myasnikov, A., Roman\u2019kov, V., Ushakov, A., Vershik, A.: The word and geodesic problems in free solvable groups. Trans. Amer. Math. Soc. 362(9), 4655\u20134682 (2010). \n                    https:\/\/doi.org\/10.1090\/s0002-9947-10-04959-7","journal-title":"Trans. Amer. Math. Soc."},{"key":"9849_CR19","doi-asserted-by":"publisher","unstructured":"Myasnikov, A., Vassileva, S., Wei\u00df, A.: The conjugacy problem in free solvable groups and wreath products of abelian groups is in T\n                           C\n                           0. In: CSR 2017. \n                    https:\/\/doi.org\/10.1007\/978-3-319-58747-9_20\n                    \n                  , pp 217\u2013231. Proceedings (2017)","DOI":"10.1007\/978-3-319-58747-9_20"},{"key":"9849_CR20","doi-asserted-by":"publisher","unstructured":"Myasnikov, A., Vassileva, S., Weiss, A.: Log-Space Complexity of the Conjugacy Problem in Wreath Products, chap. 12, pp. 215\u2013236. World Scientific (2017). \n                    https:\/\/doi.org\/10.1142\/9789813204058_0012","DOI":"10.1142\/9789813204058_0012"},{"key":"9849_CR21","unstructured":"Myasnikov, A., Wei\u00df, A.: TC0 circuits for algorithmic problems in nilpotent groups. ArXiv e-prints (2017)"},{"issue":"5","key":"9849_CR22","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/BF02321898","volume":"9","author":"V Remeslennikov","year":"1970","unstructured":"Remeslennikov, V., Sokolov, V. G.: Certain properties of the Magnus embedding. Algebra i logika 9(5), 566\u2013578 (1970)","journal-title":"Algebra i logika"},{"key":"9849_CR23","volume-title":"Parallel algorithms for group word problems","author":"D Robinson","year":"1993","unstructured":"Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993)"},{"key":"9849_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00200-006-0006-9","volume":"17","author":"V Shpilrain","year":"2006","unstructured":"Shpilrain, V., Zapata, G.: Combinatorial group theory and public key cryptography. Appl. Algebra Engrg. Comm. Comput. 17, 291\u2013302 (2006)","journal-title":"Appl. Algebra Engrg. Comm. Comput."},{"issue":"1","key":"9849_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1515\/GCC.2011.005","volume":"3","author":"S Vassileva","year":"2011","unstructured":"Vassileva, S.: Polynomial time conjugacy in wreath products and free solvable groups. Groups Complex. Cryptol. 3(1), 105\u2013120 (2011). \n                    https:\/\/doi.org\/10.1515\/GCC.2011.005","journal-title":"Groups Complex. Cryptol."},{"key":"9849_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer, Berlin (1999)"},{"key":"9849_CR27","doi-asserted-by":"crossref","unstructured":"Waack, S.: The parallel complexity of some constructions in combinatorial group theory, pp 492\u2013498. Springer-Verlag New York, Inc., New York (1990)","DOI":"10.1007\/BFb0029647"},{"key":"9849_CR28","doi-asserted-by":"publisher","unstructured":"Wang, L., Wang, L., Cao, Z., Okamoto, E., Shao, J.: New constructions of public-key encryption schemes from conjugacy search problems. In: Information security and cryptology, Lecture Notes in Comput. Sci. \n                    https:\/\/doi.org\/10.1007\/978-3-642-21518-6_1\n                    \n                  , vol. 6584, pp 1\u201317. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-21518-6_1"},{"key":"9849_CR29","doi-asserted-by":"crossref","unstructured":"Wei\u00df, A.: A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. In: Algebra and computer science, Contemporary Mathematics, vol. 677, pp 185\u2013212. American Mathematics Society, Providence (2016)","DOI":"10.1090\/conm\/677\/13628"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9849-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9849-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9849-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T21:09:57Z","timestamp":1556053797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9849-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,12]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["9849"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9849-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,2,12]]},"assertion":[{"value":"12 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}