{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:24:38Z","timestamp":1743035078265,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_37","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"445-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parallel Identity Testing for Skew Circuits with Big Powers and Applications"],"prefix":"10.1007","author":[{"given":"Daniel","family":"K\u00f6nig","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"issue":"4","key":"37_CR1","doi-asserted-by":"publisher","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":"1","key":"37_CR2","doi-asserted-by":"publisher","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":"2","key":"37_CR3","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65(2), 332\u2013350 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"37_CR4","doi-asserted-by":"publisher","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."},{"issue":"3","key":"37_CR5","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1145\/44483.44496","volume":"35","author":"FE Fich","year":"1988","unstructured":"Fich, F.E., Tompa, M.: The parallel complexity of exponentiating polynomials over finite fields. J. Assoc. Comput. Mach. 35(3), 651\u2013667 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"37_CR6","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: $${P}$$-Completeness Theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: $${P}$$-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"37_CR7","doi-asserted-by":"publisher","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&2","key":"37_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci. 158(1&2), 143\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"37_CR9","doi-asserted-by":"publisher","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":"37_CR10","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the STOC 1997, pp. 220\u2013229. ACM Press (1997)","DOI":"10.1145\/258533.258590"},{"issue":"1\u20132","key":"37_CR11","doi-asserted-by":"publisher","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":"37_CR12","series-title":"Lecturer Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-319-21398-9_19","volume-title":"Computing and Combinatorics","author":"D K\u00f6nig","year":"2015","unstructured":"K\u00f6nig, D., Lohrey, M.: Evaluating matrix circuits. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 235\u2013248. Springer, Heidelberg (2015)"},{"key":"37_CR13","unstructured":"K\u00f6nig, D., Lohrey, M.: Parallel identity testing for algebraic branching programs with big powers and applications. arXiv.org (2015). http:\/\/arxiv.org\/abs\/1502.04545"},{"issue":"5","key":"37_CR14","doi-asserted-by":"publisher","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":"37_CR15","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: asurvey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"37_CR16","series-title":"SpringerBriefs in Mathematics","doi-asserted-by":"publisher","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. SpringerBriefs in Mathematics. Springer, New York (2014)"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.ic.2014.12.014","volume":"243","author":"M Lohrey","year":"2015","unstructured":"Lohrey, M., Steinberg, B., Zetzsche, G.: Rational subsets and submonoids of wreath products. Inf. Comput. 243, 191\u2013204 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"37_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"issue":"9","key":"37_CR19","first-page":"1","volume":"2","author":"PS Novikov","year":"1958","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Amer. Math. Soc. Transl. Ser. 2(9), 1\u2013122 (1958)","journal-title":"Amer. Math. Soc. Transl. Ser."},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"37_CR21","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, New York (1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T11:28:37Z","timestamp":1676028517000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}