{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T12:10:32Z","timestamp":1737375032767,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_13","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"164-175","source":"Crossref","is-referenced-by-count":2,"title":["Arithmetic Circuits and Polynomial Replacement Systems"],"prefix":"10.1007","author":[{"given":"Pierre","family":"McKenzie","sequence":"first","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"13_CR1","series-title":"Lect Notes Comput Sci","volume-title":"Bounded depth arithmetic circuits: Counting and closure","author":"E. Allender","year":"1999","unstructured":"E. Allender, A. Ambainis, D. Mix Barrington, S. Datta, and H. L\u00eaThanh. Bounded depth arithmetic circuits: Counting and closure. In Proceedings 26th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Berlin Heidelberg, 1999. Springer Verlag. To appear."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal, E. Allender, and S. Datta. On TC0, AC0, and arithmetic circuits. In Proceedings 12th Computational Complexity, pages 134\u2013148. IEEE Computer Society, 1997.","DOI":"10.1109\/CCC.1997.612309"},{"issue":"4","key":"13_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/270563.270564","volume":"28","author":"E. Allender","year":"1998","unstructured":"E. Allender. Making computation count: arithmetic circuits in the nineties. SIGACT News, 28(4):2\u201315, 1998.","journal-title":"SIGACT News"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01200057","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai and L. Fortnow. Arithmetization: a new method in structural complexity theory. Computational Complexity, 1:41\u201366, 1991.","journal-title":"Computational Complexity"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"H. Caussinus, P. McKenzie, D. Th\u00e9rien, and H. Vollmer. Nondeterministic NC1 computation. Journal of Computer and System Sciences, 57:200\u2013212, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O. Ibarra","year":"1983","unstructured":"O. Ibarra and S. Moran. Probabilistic algorithms for deciding equivalence of straight-line programs. Journal of the ACM, 30:217\u2013228, 1983.","journal-title":"Journal of the ACM"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/42267.45069","volume":"35","author":"E. Kaltofen","year":"1988","unstructured":"E. Kaltofen. Greatest common divisors of polynomials given by straightline programs. Journal of the ACM, 35:231\u2013264, 1988.","journal-title":"Journal of the ACM"},{"key":"13_CR8","volume-title":"Hilbert\u2019s Tenth Problem","author":"Y. V. Matiasjevi\u010d","year":"1993","unstructured":"Y. V. Matiasjevi\u010d. Hilbert\u2019s Tenth Problem. Foundations of Computing Series. MIT Press, Cambridge, MA, 1993."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. In Proceedings 5th ACM Symposium on the Theory of Computing, pages 1\u20139. ACM Press, 1973.","DOI":"10.1145\/800125.804029"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25:405\u2013414, 1978.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"13_CR11","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal of Computing, 8(3):411\u2013421, 1979.","journal-title":"SIAM Journal of Computing"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"H. Venkateswaran. Circuit definitions of non-deterministic complexity classes. SIAM Journal on Computing, 21:655\u2013670, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings 6th Structure in Complexity Theory, pages 270\u2013284. IEEE Computer Society Press, 1991.","DOI":"10.1109\/SCT.1991.160269"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12:641\u2013644, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1137\/0218036","volume":"18","author":"H. Venkateswaran","year":"1989","unstructured":"H. Venkateswaran and M. Tompa. A new pebble game that characterizes parallel complexity classes. SIAM J. on Computing, 18:533\u2013549, 1989.","journal-title":"SIAM J. on Computing"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"K. W. Wagner. The complexity of problems concerning graphs with regularities. Technical report, Friedrich-Schiller-Universit\u00e4t Jena, 1984. Extended abstract in Proceedings 11th Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 176, pages 544\u2013552, 1984.","DOI":"10.1007\/BFb0030338"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"K. W. Wagner. The complexity of combinatorial problems with succinct input representation. Acta Informatica, 23:325\u2013356, 1986.","journal-title":"Acta Informatica"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"K. Yang. Integer circuit evaluation is PSPACE-complete. In Proceedings 15th Computational Complexity Conference, pages 204\u2013211. IEEE Computer Society Press, 2000.","DOI":"10.1109\/CCC.2000.856751"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:29:56Z","timestamp":1737372596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}