{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:25:53Z","timestamp":1742991953312,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319587462"},{"type":"electronic","value":"9783319587479"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-58747-9_20","type":"book-chapter","created":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T01:14:05Z","timestamp":1493946845000},"page":"217-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in $${{\\mathsf {T}}}{{\\mathsf {C}}}^0$$"],"prefix":"10.1007","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"}]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,6]]},"reference":[{"issue":"3","key":"20_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 NC$${^1}$$. J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"20_CR2","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)","journal-title":"Math. Ann."},{"key":"20_CR3","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 Symposium, pp. 1\u201312 (2014)","DOI":"10.1007\/978-3-642-54423-1_1"},{"key":"20_CR4","first-page":"199","volume":"1","author":"D Grigoriev","year":"2009","unstructured":"Grigoriev, D., Shpilrain, V.: Authentication from matrix conjugation. Groups Complex. Cryptology 1, 199\u2013205 (2009)","journal-title":"Groups Complex. Cryptology"},{"key":"20_CR5","unstructured":"Gul, F., Sohrabi, M., Ushakov, A.: Magnus embedding and algorithmic properties of groups $$F\/N^{(d)}$$. ArXiv e-prints, abs\/1501.01001, January 2015"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/3-540-48224-5_9","volume-title":"Automata, Languages and Programming","author":"W Hesse","year":"2001","unstructured":"Hesse, W.: Division is in uniform TC$${^0}$$. In: Orejas, F., Spirakis, P.G., Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 104\u2013114. Springer, Heidelberg (2001). doi:10.1007\/3-540-48224-5_9"},{"key":"20_CR7","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":"20_CR8","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":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/3-540-44598-6_10","volume-title":"Advances in Cryptology \u2014 CRYPTO 2000","author":"KH Ko","year":"2000","unstructured":"Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J., Park, C.: New public-key cryptosystem using braid groups. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 166\u2013183. Springer, Heidelberg (2000). doi:10.1007\/3-540-44598-6_10"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"K\u00f6nig, D., Lohrey, M.: Evaluating matrix circuits. CoRR, abs\/1502.03540 (2015)","DOI":"10.1007\/978-3-319-21398-9_19"},{"issue":"4","key":"20_CR11","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 TC$$^{0}$$ in terms of infinite groups. Theory Comput. Syst. 40(4), 303\u2013325 (2007)","journal-title":"Theory Comput. Syst."},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-49381-6_27","volume-title":"Algorithms and Computation","author":"K-J Lange","year":"1998","unstructured":"Lange, K.-J., McKenzie, P.: On the complexity of free monoid morphisms. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 247\u2013256. Springer, Heidelberg (1998). doi:10.1007\/3-540-49381-6_27"},{"issue":"1","key":"20_CR13","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)","journal-title":"Inf. Comput."},{"key":"20_CR14","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. Math. 40, 764\u2013768 (1939)","journal-title":"Ann. Math."},{"key":"20_CR15","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. Am. Math Soc. 121, 329\u2013339 (1966)","journal-title":"Trans. Am. Math Soc."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Miller III, C.F.: On group-theoretic decision problems and their classification, vol. 68. Annals of Mathematics Studies. Princeton University Press (1971)","DOI":"10.1515\/9781400881789"},{"issue":"9","key":"20_CR17","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, geodesic problems in free solvable groups. Trans. Amer. Math. Soc. 362(9), 4655\u20134682 (2010)","journal-title":"Trans. Amer. Math. Soc."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Myasnikov, A.G., Vassileva, S., Wei\u00df, A.: Log-space complexity of the conjugacy problem in wreath products. Groups Complex. Cryptol. (2017, to appear)","DOI":"10.1142\/9789813204058_0012"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Miasnikov, A., Vassileva, S., Wei\u00df, A.: The conjugacy problem in free solvable groups and wreath product of abelian groups is in TC$$^{0}$$. ArXiv e-prints, abs\/1612.05954 (2016)","DOI":"10.1007\/978-3-319-58747-9_20"},{"issue":"5","key":"20_CR20","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":"20_CR21","unstructured":"Robinson,D.: Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego (1993)"},{"key":"20_CR22","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":"20_CR23","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)","journal-title":"Groups Complex. Cryptol."},{"key":"20_CR24","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":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1007\/BFb0029647","volume-title":"Mathematical Foundations of Computer Science 1990","author":"S Waack","year":"1990","unstructured":"Waack, S.: The parallel complexity of some constructions in combinatorial group theory (abstract). In: Rovan, B. (ed.) MFCS 1990. LNCS, vol. 452, pp. 492\u2013498. Springer, Heidelberg (1990). doi:10.1007\/BFb0029647"},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-21518-6_1","volume-title":"Information Security and Cryptology","author":"L Wang","year":"2011","unstructured":"Wang, L., Wang, L., Cao, Z., Okamoto, E., Shao, J.: New constructions of public-key encryption schemes from conjugacy search problems. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010. LNCS, vol. 6584, pp. 1\u201317. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-21518-6_1"},{"key":"20_CR27","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, vol. 677. Contemporary Mathematics, pp. 185\u2013212. American Mathematical Society, Providence, RI (2016)","DOI":"10.1090\/conm\/677\/13628"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-58747-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:16:07Z","timestamp":1710263767000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-58747-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319587462","9783319587479"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-58747-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"6 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Kazan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/logic.pdmi.ras.ru\/csr2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}