{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T19:28:04Z","timestamp":1648668484331},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648277","type":"print"},{"value":"9783540685326","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055790","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"409-417","source":"Crossref","is-referenced-by-count":5,"title":["On counting ac 0 circuits with negative constants"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[]},{"given":"David Mix","family":"Barrington","sequence":"additional","affiliation":[]},{"given":"Huong","family":"L\u00eaThanh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"37_CR1","unstructured":"M. Agrawal, E. Allender, S. Datta, On TC 0, AC 0 and Arithmetic Circuits. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pp:134\u2013148, 1997."},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender, R. Beals, M. Ogihara, The complexity of matrix rank and feasible systems of linear equations. In Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pp:161\u2013167, 1996.","DOI":"10.1145\/237814.237856"},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. \u00e1lvarez","year":"1993","unstructured":"C. \u00e1lvarez, B. Jenner, A very hard logspace counting class. Theoretical Computer Science, 107:3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"D. A. M. Barrington, N. Immerman, Time, Hardware, and Uniformity. In L. A. Hemaspaandra and A. L. Selman, eds., Complexity Theory Retrospective II, Springer Verlag, pp:1\u201322, 1997.","DOI":"10.1007\/978-1-4612-1872-2_1"},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, N. Immerman, and H. Straubing, On Uniformity Within NC 1. Journal of Computer and System Science, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Science"},{"key":"37_CR6","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. Beame","year":"1986","unstructured":"P. Beame, S. Cook, H. J. Hoover, Log depth circuits for division and related problems. SIAM Journal on Computing, 15:994\u20131003, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR7","unstructured":"H. Caussinus, P. McKenzie, D. Th\u00e9rien, H. Vollmer, Nondeterministic NC 1. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pp:12\u201321, 1996."},{"issue":"1","key":"37_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"S. A. Fenner","year":"1995","unstructured":"S. A. Fenner, L. J. Fortnow, S. A. Kurtz, Gap-definable counting classes. Journal of Computer and System Science, 48(1):116\u2013148, 1995.","journal-title":"Journal of Computer and System Science"},{"key":"37_CR9","first-page":"363","volume":"26","author":"J. K\u00f6bler","year":"1989","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, J. Tor\u00e1n, On counting and approximation. Acta Informatica, 26:363\u2013379, 1989.","journal-title":"Acta Informatica"},{"issue":"5","key":"37_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(92)90035-T","volume":"42","author":"B. Litow","year":"1992","unstructured":"B. Litow, On iterated integer product. Information Processing Letters, 42(5):269\u2013272, 1992.","journal-title":"Information Processing Letters"},{"key":"37_CR11","unstructured":"M. Mahajan, V. Vinay, Determinant: Combinatorics, Algorithms and Complexity. In Proceedings of SODA'97. ftp:\/\/ftp.eccc.unitrier.de\/pub\/eccc\/reports\/1997\/TR97-036\/index.html"},{"key":"37_CR12","first-page":"598","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. A. Razborov, Lower bound on size of bounded depth networks over a complete basis with logical addition. Mathematicheskie Zametli, 41:598\u2013607, 1987. English translation in Mathematical Notes of the Academy of Sciences of the USSR, 41:333\u2013338, 1987.","journal-title":"Mathematicheskie Zametli"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (STOC), pp:77\u201382, 1987.","DOI":"10.1145\/28395.28404"},{"key":"37_CR14","first-page":"116","volume":"E75-D","author":"S. Toda","year":"1992","unstructured":"S. Toda, Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions, Informations and Systems, E75-D:116\u2013124, 1992.","journal-title":"IEICE Transactions, Informations and Systems"},{"key":"37_CR15","unstructured":"S. Toda, Counting problems computationally equivalent to the determinant. Manuscript."},{"key":"37_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant, The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"37_CR17","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":"37_CR18","doi-asserted-by":"crossref","unstructured":"V. Vinay, Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, pp:270\u2013284, 1991.","DOI":"10.1109\/SCT.1991.160269"}],"container-title":["Mathematical Foundations of Computer Science 1998","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:44:49Z","timestamp":1555785889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":18,"URL":"http:\/\/dx.doi.org\/10.1007\/bfb0055790","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1998]]}}}