{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:07:40Z","timestamp":1759147660555,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","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":[[2001]]},"DOI":"10.1007\/3-540-48224-5_9","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"104-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Division Is In Uniform TC0"],"prefix":"10.1007","author":[{"given":"William","family":"Hesse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or. A theorem on probabilistic constant depth computations. In ACM Symposium on Theory of Computing (STOC\u2019 84), pages 471\u2013474, 1984. ACM Press.","DOI":"10.1145\/800057.808715"},{"key":"9_CR2","unstructured":"E. Allender, D. A. Mix Barrington, and W. Hesse. Uniform circuits for division: Consequences and problems. To appear in Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC-2001), 2001. IEEE Computer Society."},{"key":"9_CR3","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 NC1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"9_CR4","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. W. Beame","year":"1986","unstructured":"P. W. Beame, S. A. Cook, and H. J. Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994\u20131003, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR5","unstructured":"A. Chiu, G. Davida, and B. Litow. NC1 division. online at http:\/\/www.cs.jcu.edu.au\/~bruce\/papers\/crr00_3.ps.gz ."},{"issue":"4","key":"9_CR6","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1137\/0220048","volume":"20","author":"G. I. Davida","year":"1991","unstructured":"G. I. Davida and B. Litow. Fast Parallel Arithmetic via Modular Representation. SIAM Journal of Computing, 20(4):756\u2013765, 1991.","journal-title":"SIAM Journal of Computing"},{"issue":"2-3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(85)90045-3","volume":"36","author":"R. Fagin","year":"1985","unstructured":"R. Fagin, M. M. Klawe, N. J. Pippenger, and L. Stockmeyer. Bounded-depth, polynomial-size circuits for symmetric functions. Theoretical Computer Science, 36(2-3):239\u2013250, 1985.","journal-title":"Theoretical Computer Science"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. In 22nd Annual Symposium on Foundations of Computer Science, 260\u2013270, 1981. IEEE.","DOI":"10.1109\/SFCS.1981.35"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"J. Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 6\u201320, 1986.","DOI":"10.1145\/12130.12132"},{"key":"9_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"N. Immerman. Descriptive Complexity. Springer-Verlag, New York, 1999."},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, 116(1):103\u2013116, 1995.","journal-title":"Information and Computation"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"J. H. Reif. On threshold circuits and polynomial computation. In Proceedings, Structure in Complexity Theory, Second Annual Conference, pages 118\u2013123, IEEE Computer Society Press.","DOI":"10.1109\/PSCT.1987.10319260"},{"issue":"5","key":"9_CR13","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1137\/0221053","volume":"21","author":"J. H. Reif","year":"1992","unstructured":"J. H. Reif and S. R. Tate. On threshold circuits and polynomial computation. SIAM Journal on Computing, 21(5):896\u2013908, 1992.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:24Z","timestamp":1737503424000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"4 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}