{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:48Z","timestamp":1725511788837},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_12","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"133-144","source":"Crossref","is-referenced-by-count":0,"title":["On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds"],"prefix":"10.1007","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1109\/CCC.2006.30","volume-title":"Proc. 21st Ann. IEEE Conference on Computational Complexity","author":"E. Allender","year":"2006","unstructured":"Allender, E., et al.: On the complexity of numerical analysis. In: Proc. 21st Ann. IEEE Conference on Computational Complexity, pp. 331\u2013339. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"12_CR2","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1142\/9789812794499_0035","volume-title":"Current trends in Theoretical Computer Science","author":"E. Allender","year":"1993","unstructured":"Allender, E., Wagner, K.W.: Counting hierarchies: polynomial time and constant depth circuits. In: Rozenberg, G., Salomaa, A. (eds.) Current trends in Theoretical Computer Science, pp. 469\u2013483. World Scientific, Singapore (1993)"},{"issue":"4","key":"12_CR3","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P.W. Beame","year":"1986","unstructured":"Beame, P.W., Cook, S.A., Hoover, H.J.: Log depth circuits for division and related problems. SIAM J. Comput.\u00a015(4), 994\u20131003 (1986)","journal-title":"SIAM J. Comput."},{"key":"12_CR4","series-title":"Lectures in Applied Mathematics","first-page":"125","volume-title":"The mathematics of numerical analysis","author":"L. Blum","year":"1996","unstructured":"Blum, L., et al.: Algebraic Settings for the Problem \u201cP\u00a0\u2260\u2009NP?\u201d. In: The mathematics of numerical analysis. Lectures in Applied Mathematics, vol.\u00a032, pp. 125\u2013144. Amer. Math. Soc, Providence (1996)"},{"key":"12_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., et al.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers. Bull.\u00a0Amer. Math. Soc.\u00a021, 1\u201346 (1989)","journal-title":"Bull.\u00a0Amer. Math. Soc."},{"key":"12_CR7","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics, vol.\u00a07. Springer, Heidelberg (2000)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(99)00183-8","volume":"235","author":"P. B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Cook\u2019s versus Valiant\u2019s hypothesis. Theoret. Comp. Sci.\u00a0235, 71\u201388 (2000)","journal-title":"Theoret. Comp. Sci."},{"key":"12_CR9","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, vol.\u00a0315. Springer, Heidelberg (1997)"},{"issue":"5","key":"12_CR10","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1090\/S0002-9939-96-03173-5","volume":"124","author":"W. Melo de","year":"1996","unstructured":"de Melo, W., Svaiter, B.F.: The cost of computing integers. Proc. Amer. Math. Soc.\u00a0124(5), 1377\u20131378 (1996)","journal-title":"Proc. Amer. Math. Soc."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(80)90020-1","volume":"11","author":"J. Gathen von zur","year":"1980","unstructured":"von zur Gathen, J., Strassen, V.: Some polynomials that are hard to compute. Theoret. Comp. Sci.\u00a011, 331\u2013336 (1980)","journal-title":"Theoret. Comp. Sci."},{"issue":"4","key":"12_CR12","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., Barrrington, D.A.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. System Sci.\u00a065(4), 695\u2013716 (2002)","journal-title":"J. Comput. System Sci."},{"issue":"3-4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00037-004-0186-2","volume":"13","author":"P. Koiran","year":"2004","unstructured":"Koiran, P.: Valiant\u2019s model and the cost of computing integers. Comput. Complexity\u00a013(3-4), 131\u2013146 (2004)","journal-title":"Comput. Complexity"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/3-540-58691-1_45","volume-title":"Algorithmic Number Theory","author":"R.J. Lipton","year":"1994","unstructured":"Lipton, R.J.: Straight-line complexity and integer factorization. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol.\u00a0877, pp. 71\u201379. Springer, Heidelberg (1994)"},{"key":"12_CR15","unstructured":"Malod, G.: Polyn\u00f4mes et coefficients. Phd thesis, Universit\u00e9 Claude Bernard-Lyon\u00a01 (2003), \n                    \n                      http:\/\/tel.ccsd.cnrs.fr\/tel-00087399"},{"issue":"5","key":"12_CR16","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1137\/0221053","volume":"21","author":"J.H. Reif","year":"1992","unstructured":"Reif, J.H., Tate, S.R.: On threshold circuits and polynomial computation. SIAM J. Comput.\u00a021(5), 896\u2013908 (1992)","journal-title":"SIAM J. Comput."},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M. Shub","year":"1995","unstructured":"Shub, M., Smale, S.: On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cNP\u2009\u2260\u2009P?\u201d. Duke Math. J.\u00a081, 47\u201354 (1995)","journal-title":"Duke Math. J."},{"key":"12_CR18","first-page":"271","volume-title":"Mathematics: frontiers and perspectives","author":"S. Smale","year":"2000","unstructured":"Smale, S.: Mathematical problems for the next century. In: Mathematics: frontiers and perspectives, pp. 271\u2013294. Amer. Math. Soc., Providence (2000)"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0203010","volume":"3","author":"V. Strassen","year":"1974","unstructured":"Strassen, V.: Polynomials with rational coefficients which are hard to compute. SIAM J.\u00a0Comp.\u00a03, 128\u2013149 (1974)","journal-title":"SIAM J.\u00a0Comp."},{"key":"12_CR20","first-page":"1","volume":"78","author":"V. Strassen","year":"1976","unstructured":"Strassen, V.: Einige Resultate \u00fcber Berechnungskomplexit\u00e4t. Jahr. Deutsch. Math. Ver.\u00a078, 1\u20138 (1976)","journal-title":"Jahr. Deutsch. Math. Ver."},{"key":"12_CR21","first-page":"634","volume-title":"Handbook of Theoretical Computer Science, vol. A","author":"V. Strassen","year":"1990","unstructured":"Strassen, V.: Algebraic complexity theory. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. A, pp. 634\u2013672. Elsevier, Amsterdam (1990)"},{"issue":"3","key":"12_CR22","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/116825.116858","volume":"38","author":"J. Tor\u00e1n","year":"1991","unstructured":"Tor\u00e1n, J.: Complexity classes defined by counting quantifiers. J. Assoc. Comput. Mach.\u00a038(3), 753\u2013774 (1991)","journal-title":"J. Assoc. Comput. Mach."},{"key":"12_CR23","first-page":"249","volume-title":"Proc.\u00a011th ACM STOC","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc.\u00a011th ACM STOC, pp. 249\u2013261. ACM Press, New York (1979)"},{"key":"12_CR24","unstructured":"Valiant, L.G.: Reducibility by algebraic projections. In: Logic and Algorithmic: an International Symposium held in honor of Ernst Specker, vol. 30, pp. 365\u2013380. Monogr. No.\u00a030 de l\u2019Enseign. Math. (1982)"},{"key":"12_CR25","series-title":"Texts in Theoretical Computer Science. EATCS","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity. A uniform approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. EATCS. Springer, Berlin (1999)"},{"issue":"3","key":"12_CR26","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K.W. Wagner","year":"1986","unstructured":"Wagner, K.W.: The complexity of combinatorial problems with succinct input representation. Acta Inform.\u00a023(3), 325\u2013356 (1986)","journal-title":"Acta Inform."}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:32:07Z","timestamp":1620001927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_12","relation":{},"subject":[]}}