{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T02:58:38Z","timestamp":1718938718871},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T00:00:00Z","timestamp":1499212800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00453-017-0343-z","type":"journal-article","created":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T13:36:52Z","timestamp":1499261812000},"page":"1459-1492","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Evaluation of Circuits Over Nilpotent and Polycyclic Groups"],"prefix":"10.1007","volume":"80","author":[{"given":"Daniel","family":"K\u00f6nig","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"issue":"4","key":"343_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","volume":"50","author":"M Agrawal","year":"2003","unstructured":"Agrawal, M., Biswas, S.: Primality and identity testing via chinese remaindering. J. Assoc. Comput. Mach. 50(4), 429\u2013443 (2003)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"343_CR2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E Allender","year":"1999","unstructured":"Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Comput. Complex. 8(2), 99\u2013126 (1999)","journal-title":"Comput. Complex."},{"issue":"5","key":"343_CR3","doi-asserted-by":"crossref","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"343_CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"E Allender","year":"1998","unstructured":"Allender, E., Jiao, J., Mahajan, M., Vinay, V.: Non-commutative arithmetic circuits: depth reduction and size lower bounds. Theor. Comput. Sci. 209(1\u20132), 47\u201386 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"343_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C \u00c0lvarez","year":"1993","unstructured":"\u00c0lvarez, C., Jenner, B.: A very hard log-space counting class. Theor. Comput. Sci. 107(1), 3\u201330 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"343_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity\u2014A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"343_CR7","first-page":"26","volume":"16","author":"V Arvind","year":"2009","unstructured":"Arvind, V., Joglekar, P.S.: Arithmetic circuit size, identity testing, and finite automata. Electron. Colloq. Comput. Complex. (ECCC) 16, 26 (2009)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"issue":"2","key":"343_CR8","doi-asserted-by":"crossref","first-page":"112","DOI":"10.2307\/1970362","volume":"86","author":"L Auslander","year":"1967","unstructured":"Auslander, L.: On a problem of Philip Hall. Ann. Math. 86(2), 112\u2013116 (1967)","journal-title":"Ann. Math."},{"key":"343_CR9","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DAM Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in $$\\text{ NC }^1$$ NC 1 . J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"343_CR10","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"DAM Barrington","year":"1988","unstructured":"Barrington, D.A.M., Th\u00e9rien, D.: Finite monoids and the fine structure of $$\\text{ NC }^{1}$$ NC 1 . J. Assoc. Comput. Mach. 35(4), 941\u2013952 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"343_CR11","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1137\/S0097539793249530","volume":"26","author":"M Beaudry","year":"1997","unstructured":"Beaudry, M., McKenzie, P., P\u00e9ladeau, P., Th\u00e9rien, D.: Finite monoids: from word to circuit evaluation. SIAM J. Comput. 26(1), 138\u2013152 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"343_CR12","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M Ben-Or","year":"1992","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput. 21(1), 54\u201358 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"343_CR13","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1006\/jabr.2000.8604","volume":"237","author":"DK Biss","year":"2001","unstructured":"Biss, D.K., Dasgupta, S.: A presentation for the unipotent group over rings with identity. J. Algebra 237(2), 691\u2013707 (2001)","journal-title":"J. Algebra"},{"key":"343_CR14","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"SA Cook","year":"1985","unstructured":"Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Inf. Control 64, 2\u201322 (1985)","journal-title":"Inf. Control"},{"key":"343_CR15","doi-asserted-by":"publisher","unstructured":"Cook, S.A., Fontes, L.: Formal theories for linear algebra. Log. Methods Comput. Sci. 8(1), (2012). doi: 10.2168\/LMCS-8(1:25)2012","DOI":"10.2168\/LMCS-8(1:25)2012"},{"key":"343_CR16","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: Proceedings of the 11th Symposium on Latin American Theoretical Informatics, LATIN 2014. Volume 8392 of Lecture Notes in Computer Science, pp. 1\u201312. Springer (2014)","DOI":"10.1007\/978-3-642-54423-1_1"},{"issue":"5","key":"343_CR17","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1137\/0218066","volume":"18","author":"W Eberly","year":"1989","unstructured":"Eberly, W.: Very fast parallel polynomial arithmetic. SIAM J. Comput. 18(5), 955\u2013976 (1989)","journal-title":"SIAM J. Comput."},{"key":"343_CR18","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","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. J. Comput. Syst. Sci. 65, 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"343_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"OH Ibarra","year":"1983","unstructured":"Ibarra, O.H., Moran, S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J. Assoc. Comput. Mach. 30(1), 217\u2013228 (1983)","journal-title":"J. Assoc. Comput. Mach."},{"key":"343_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, STOC 1997, pp. 220\u2013229. ACM Press (1997)","DOI":"10.1145\/258533.258590"},{"issue":"1\u20132","key":"343_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complex."},{"key":"343_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9964-6","volume-title":"Fundamentals of the Theory of Groups, Volume 62 of Graduate Texts in Mathematics","author":"MI Kargapolov","year":"1979","unstructured":"Kargapolov, M.I., Merzljakov, J.I.: Fundamentals of the Theory of Groups, Volume 62 of Graduate Texts in Mathematics. Springer-Verlag, New York (1979)"},{"issue":"4","key":"343_CR23","first-page":"852","volume":"45","author":"OG Kharlampovi\u010d","year":"1981","unstructured":"Kharlampovi\u010d, O.G.: A finitely presented solvable group with unsolvable word problem (Russian). Izv. Akad. Nauk SSSR Ser. Mat. 45(4), 852\u2013873 (1981)","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat."},{"key":"343_CR24","volume-title":"The Art of Computer Programming, Volume 2: Seminumerical Algorithmus","author":"D\u00a0E Knuth","year":"1998","unstructured":"Knuth, D\u00a0.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithmus, 3rd edn. Addison-Wesley, Boston (1998)","edition":"3"},{"key":"343_CR25","doi-asserted-by":"crossref","unstructured":"K\u00f6nig, D., Lohrey, M.: Parallel identity testing for algebraic branching programs with big powers and applications. In: Proceedings of Mathematical Foundations of Computer Science, MFCS 2015. Lecture Notes in Computer Science 9235, pp. 445\u2013458. Springer (2015)","DOI":"10.1007\/978-3-662-48054-0_37"},{"issue":"3","key":"343_CR26","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"RJ Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. Assoc. Comput. Mach. 24(3), 522\u2013526 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"5","key":"343_CR27","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"343_CR28","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"343_CR29","series-title":"Springer Briefs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, Berlin (2014)"},{"issue":"1\u20132","key":"343_CR30","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1142\/S0218196715400068","volume":"25","author":"M Lohrey","year":"2015","unstructured":"Lohrey, M.: Rational subsets of unitriangluar groups. Int. J. Algebra Comput. 25(1\u20132), 113\u2013121 (2015)","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"343_CR31","first-page":"1","volume":"2","author":"AI Mal\u2019cev","year":"1956","unstructured":"Mal\u2019cev, A.I.: On certain classes of infinite soluble groups. Am. Math. Soc. Transl. Ser. 2(2), 1\u201321 (1956)","journal-title":"Am. Math. Soc. Transl. Ser."},{"key":"343_CR32","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1073\/pnas.18.11.665","volume":"18","author":"G Miller","year":"1932","unstructured":"Miller, G.: The commutator subgroup of a group generated by two operators. Proc. Natl. Acad. Sci. USA 18, 665\u2013668 (1932)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"343_CR33","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0167-2789(97)80003-6","volume":"111","author":"C Moore","year":"1998","unstructured":"Moore, C.: Predicting nonlinear cellular automata quickly by decomposing them into linear ones. Phys. D Nonlinear Phenom. 111, 27\u201341 (1998)","journal-title":"Phys. D Nonlinear Phenom."},{"key":"343_CR34","unstructured":"Myasnikov, A.G., Wei\u00df, A.: TC $$\\hat{\\,\\,}$$ ^ 0 circuits for algorithmic problems in nilpotent groups. CoRR, abs\/1702.06616 (2017)"},{"key":"343_CR35","unstructured":"Nikolaev, A., Ushakov, A.: Subset sum problem in polycyclic groups. CoRR, abs\/1703.07406 (2017)"},{"key":"343_CR36","unstructured":"Robinson, D.: Parallel algorithms for group word problems. Ph.D. thesis, University of California, San Diego (1993)"},{"key":"343_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4176-8","volume-title":"An Introduction to the Theory of Groups","author":"J\u00a0J Rotman","year":"1995","unstructured":"Rotman, J\u00a0.J.: An Introduction to the Theory of Groups, 4th edn. Springer, Berlin (1995)","edition":"4"},{"key":"343_CR38","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22, 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"343_CR39","unstructured":"Simon, H.U.: Word problems for groups and contextfree recognition. In: Proceedings of Fundamentals of Computation Theory, FCT 1979, pp. 417\u2013422. Akademie-Verlag (1979)"},{"key":"343_CR40","first-page":"573","volume":"18","author":"R Swan","year":"1967","unstructured":"Swan, R.: Representations of polycyclic groups. Proc. Am. Math. Soc. 18, 573\u2013574 (1967)","journal-title":"Proc. Am. Math. Soc."},{"key":"343_CR41","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0021-8693(72)90058-0","volume":"20","author":"J Tits","year":"1972","unstructured":"Tits, J.: Free subgroups in linear groups. J. Algebra 20, 250\u2013270 (1972)","journal-title":"J. Algebra"},{"key":"343_CR42","unstructured":"Toda, S.: Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, University of Electro-Communications, Tokyo (1991)"},{"issue":"1\u20133","key":"343_CR43","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.tcs.2006.08.017","volume":"369","author":"SD Travers","year":"2006","unstructured":"Travers, S.D.: The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1\u20133), 211\u2013229 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"343_CR44","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pp. 270\u2013284. IEEE Computer Society (1991)","DOI":"10.1109\/SCT.1991.160269"},{"key":"343_CR45","doi-asserted-by":"crossref","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)"},{"issue":"4","key":"343_CR46","first-page":"265","volume":"25","author":"S Waack","year":"1991","unstructured":"Waack, S.: On the parallel complexity of linear groups. R.A.I.R.O. Inf. Th\u00e9or. Appl. 25(4), 265\u2013281 (1991)","journal-title":"R.A.I.R.O. Inf. Th\u00e9or. Appl."},{"key":"343_CR47","volume-title":"Infinite Linear Groups","author":"B\u00a0A\u00a0F Wehrfritz","year":"1977","unstructured":"Wehrfritz, B\u00a0.A\u00a0.F.: Infinite Linear Groups. Springer, Berlin (1977)"},{"key":"343_CR48","unstructured":"Wei\u00df, A.: On the complexity of conjugacy in amalgamated products and HNN extensions. Ph.D. thesis, Universit\u00e4t Stuttgart (2015)"},{"key":"343_CR49","volume-title":"Commutative Algebra, Volume I, Volume\u00a028 of Graduate Texts in Mathematics","author":"O Zariski","year":"1958","unstructured":"Zariski, O., Samuel, P.: Commutative Algebra, Volume I, Volume\u00a028 of Graduate Texts in Mathematics. Springer, Berlin (1958)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0343-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0343-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0343-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T13:33:16Z","timestamp":1659187996000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0343-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,5]]},"references-count":49,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["343"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0343-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,5]]}}}