{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:52:46Z","timestamp":1775281966003,"version":"3.50.1"},"reference-count":55,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3881,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2002,12]]},"DOI":"10.1016\/s0022-0000(02)00025-9","type":"journal-article","created":{"date-parts":[[2002,12,27]],"date-time":"2002-12-27T18:04:53Z","timestamp":1041012293000},"page":"695-716","source":"Crossref","is-referenced-by-count":115,"title":["Uniform constant-depth threshold circuits for division and iterated multiplication"],"prefix":"10.1016","volume":"65","author":[{"given":"William","family":"Hesse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Allender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David A.","family":"Mix Barrington","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(02)00025-9_BIB1","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jcss.1999.1675","article-title":"On TC0, AC0, and Arithmetic Circuits","volume":"60","author":"Agrawal","year":"2000","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00037-001-8191-1","article-title":"Reducing the complexity of reductions","volume":"10","author":"Agrawal","year":"2001","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB3","unstructured":"E. Allender, The division breakthroughs, L. Fortnow (Ed.), The Computational Complexity Column, EATCS Bull. 74, (2001), 61\u201377."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB4","unstructured":"E. Allender, A. Ambainis, D.A. Mix Barrington, S. Datta, H. L\u00eaThanh, Bounded depth arithmetic circuits: counting and closure, in: Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, Vol. 1644, 1999, pp. 149\u2013158."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB5","first-page":"65","article-title":"Uniform circuits for division","volume":"7","author":"Allender","year":"2000","journal-title":"Electron. Colloq. Comput. Complexity"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB6","unstructured":"E. Allender, D.A. Mix Barrington, W. Hesse, Uniform circuits for division: consequences and problems, Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC-2001), IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 150\u2013159."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB7","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0020-0190(91)90015-A","article-title":"Rudimentary reductions revisited","volume":"40","author":"Allender","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB8","series-title":"Advances in Computational Complexity Theory","first-page":"21","article-title":"On strong separations from AC0","volume":"Vol. 13","author":"Allender","year":"1993"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB9","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/jcss.1999.1646","article-title":"Isolation, matching, and counting","volume":"59","author":"Allender","year":"1999","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB10","unstructured":"A. Ambainis, D.A. Mix Barrington, H. L\u00eaThanh, On counting AC0 circuits with negative constants, in: MFCS \u201998: Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1450, Springer, Berlin, 1998, pp. 409\u2013417."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB11","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","article-title":"Bounded-width polynomial-size branching programs recognize exactly those languages in NC1","volume":"38","author":"Mix Barrington","year":"1989","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB12","doi-asserted-by":"crossref","unstructured":"D.A. Mix Barrington, N. Immerman, Time, hardware, and uniformity, in: L.A. Hemaspaandra, A.L. Selman (Eds.), Complexity Theory Retrospective II, Springer, Berlin, 1997, pp. 1\u201322.","DOI":"10.1007\/978-1-4612-1872-2_1"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB13","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","article-title":"On uniformity within NC1","volume":"41","author":"Mix Barrington","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB14","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1006\/jcss.2001.1764","article-title":"On the complexity of some problems on groups given as multiplication tables","volume":"63","author":"Mix Barrington","year":"2001","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB15","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0215070","article-title":"Log depth circuits for division and related problems","volume":"15","author":"Beame","year":"1986","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0022-0000(02)00025-9_BIB16","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","article-title":"Nondeterministic NC1 computation","volume":"57","author":"Caussinus","year":"1998","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB17","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","article-title":"Constant depth reducibility","volume":"13","author":"Chandra","year":"1984","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB18","unstructured":"A. Chiu, Complexity of parallel arithmetic using the Chinese Remainder representation, Master's Thesis, University of Wisconsin-Milwaukee, 1995."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB19","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1051\/ita:2001119","article-title":"Division in logspace-uniform NC1","volume":"35","author":"Chiu","year":"2001","journal-title":"RAIRO Theoret. Inform. Appl."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB20","doi-asserted-by":"crossref","unstructured":"P. Clote, Sequential machine independent characterizations of the parallel complexity classes AlogTIME, ACk, NCk, and NC, in: Feasible Mathematics: A Mathematical Sciences Institute Workshop held in Ithaca, New York, June 1989, Birkhauser, Basel, 1990, pp. 49\u201369.","DOI":"10.1007\/978-1-4612-3466-1_4"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB21","doi-asserted-by":"crossref","unstructured":"R. Constable, Type 2 computational complexity, in: Proceedings of the Fifth ACM Symposium on Theory of Computing (STOC), 1973, pp. 108\u2013121.","DOI":"10.1145\/800125.804041"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB22","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1006\/inco.1996.0084","article-title":"Inductive counting for width-restricted branching programs","volume":"130","author":"Damm","year":"1996","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB23","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1137\/0220048","article-title":"Fast parallel arithmetic via modular representation","volume":"20","author":"Davida","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB24","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/S0019-9958(86)80006-7","article-title":"Definability by constant-depth, polynomial-size circuits","volume":"70","author":"Denenberg","year":"1986","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB25","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(94)00021-2","article-title":"Bits and relative order from residues, space efficiently","volume":"50","author":"Dietz","year":"1994","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10.1016\/S0022-0000(02)00025-9_BIB26","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1137\/0218066","article-title":"Very fast polynomial arithmetic","volume":"18","author":"Eberly","year":"1989","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0022-0000(02)00025-9_BIB27","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1994.1016","article-title":"Logarithmic depth circuits for Hermite interpolation","volume":"16","author":"Eberly","year":"1994","journal-title":"J. Algorithms"},{"issue":"2\u20133","key":"10.1016\/S0022-0000(02)00025-9_BIB28","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(85)90045-3","article-title":"Bounded-depth, polynomial-size circuits for symmetric functions","volume":"36","author":"Fagin","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB29","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1006\/jcss.1999.1671","article-title":"Time\u2013space tradeoffs for satisfiability","volume":"60","author":"Fortnow","year":"2000","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB30","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0304-3975(76)90024-4","article-title":"On tape bounds for single letter alphabet language processing","volume":"3","author":"Hartmanis","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB31","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, D. Ranjan, Space bounded computations: review and new speculation, in: MFCS \u201989: Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 379, Springer, Berlin, 1989, pp. 49\u201366.","DOI":"10.1007\/3-540-51486-4_56"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB32","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, in: S. Micali (Ed.), Randomness and Computation, Advances in Computing Research, Vol. 5, JAI Press, Greenwich, CT, 1989, pp. 143\u2013170."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB33","unstructured":"J. H\u00e5stad, T. Leighton, Division in O(logn) depth using n1+\u03b5 processors, manuscript, available online at http:\/\/www.nada.kth.se\/~johanh\/papers.html."},{"issue":"2","key":"10.1016\/S0022-0000(02)00025-9_BIB34","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/inco.1994.1008","article-title":"Optimal depth, very small size circuits for symmetric functions in AC0","volume":"108","author":"H\u00e5stad","year":"1994","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB35","doi-asserted-by":"crossref","unstructured":"W. Hesse, Division is in Uniform TC0, in: ICALP 2001: 28th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 104\u2013114.","DOI":"10.1007\/3-540-48224-5_9"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB36","series-title":"Descriptive Complexity","author":"Immerman","year":"1999"},{"issue":"1","key":"10.1016\/S0022-0000(02)00025-9_BIB37","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1995.1007","article-title":"The complexity of iterated multiplication","volume":"116","author":"Immerman","year":"1995","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB38","doi-asserted-by":"crossref","unstructured":"J. Johannsen, Weak bounded arithmetic, the Diffie\u2013Hellman problem, and Constable's class K, in: Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS), 1999, pp. 268\u2013274.","DOI":"10.1109\/LICS.1999.782621"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB39","series-title":"Complexity Theory Retrospective II","first-page":"197","article-title":"Computing with sublogarithmic space","author":"Li\u015bkiewicz","year":"1997"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB40","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/S0097539793253851","article-title":"Space-efficient deterministic simulation of probabilistic automata","volume":"27","author":"Macarie","year":"1998","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0022-0000(02)00025-9_BIB41","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1006\/inco.1998.2732","article-title":"Threshold circuits of small majority-depth","volume":"146","author":"Maciel","year":"1998","journal-title":"Inform. Comput."},{"issue":"1","key":"10.1016\/S0022-0000(02)00025-9_BIB42","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1006\/inco.1998.2783","article-title":"Efficient threshold circuits for power series","volume":"152","author":"Maciel","year":"1999","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB43","first-page":"1462","article-title":"Rudimentary predicates and Turing calculations","volume":"11","author":"Nepomnja\u0161\u010di\u0131\u0306","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB44","doi-asserted-by":"crossref","unstructured":"I. Newman, P. Ragde, A. Wigderson, Perfect hashing, graph entropy, and circuit complexity (preliminary version), in: Proceedings of the Fifth Annual Structure in Complexity Theory Conference, IEEE Computer Society Press, Silver Spring, MD, 1990, pp. 91\u201399.","DOI":"10.1109\/SCT.1990.113958"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB45","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/0215017","article-title":"Logarithmic depth circuits for algebraic functions","volume":"15","author":"Reif","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB46","doi-asserted-by":"crossref","unstructured":"J. Reif, On threshold circuits and polynomial computation, in: Proceedings of the Second Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, Silver Spring, MD, 1987, pp. 118\u2013123.","DOI":"10.1109\/PSCT.1987.10319260"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB47","doi-asserted-by":"crossref","first-page":"896","DOI":"10.1137\/0221053","article-title":"On threshold circuits and polynomial computation","volume":"21","author":"Reif","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB48","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1137\/0219064","article-title":"Optimal size integer division circuits","volume":"19","author":"Reif","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB49","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","article-title":"On uniform circuit complexity","volume":"21","author":"Ruzzo","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB50","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0020-0190(88)90230-X","article-title":"Efficient parallel circuits and algorithms for division","volume":"29","author":"Shankar","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB51","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1137\/S0895480192228619","article-title":"On optimal depth threshold circuits for multiplication and related problems","volume":"7","author":"Siu","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB52","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0304-3975(90)90008-6","article-title":"If deterministic and nondeterministic space complexities are equal for loglogn, then they are also equal for logn","volume":"74","author":"Szepietowski","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00025-9_BIB53","article-title":"Turing Machines with Sublogarithmic Space","volume":"Vol. 843","author":"Szepietowski","year":"1994"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB54","series-title":"Introduction to Circuit Complexity","author":"Vollmer","year":"1999"},{"key":"10.1016\/S0022-0000(02)00025-9_BIB55","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1137\/0219024","article-title":"Decomposing NC and AC","volume":"19","author":"Wilson","year":"1990","journal-title":"SIAM J. Comput."}],"updated-by":[{"DOI":"10.1016\/j.jcss.2013.09.002","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000}}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000259?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000259?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T14:33:55Z","timestamp":1704724435000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000002000259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["S0022000002000259"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(02)00025-9","relation":{"erratum":[{"id-type":"doi","id":"10.1016\/j.jcss.2013.09.002","asserted-by":"object"}]},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}