{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:45:29Z","timestamp":1773996329049,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_55","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"672-683","source":"Crossref","is-referenced-by-count":19,"title":["Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Healy","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Comput. Complexity\u00a010(2), 117\u2013138 (2001)","DOI":"10.1007\/s00037-001-8191-1"},{"key":"55_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Bernasconi, A., Damm, C., von zur Gathen, J., Saks, M., Shparlinski, I.: Complexity of some arithmetic problems for binary polynomials. Comput. Complexity\u00a012(1-2), 23\u201347 (2003)","DOI":"10.1007\/s00037-003-0176-9"},{"key":"55_CR3","unstructured":"Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.: Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electronic Colloquium on Computational Complexity, TR05-126 (2005), http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"55_CR4","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC 1. J. Comput. System Sci.\u00a041(3), 274\u2013306 (1990)","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"55_CR5","doi-asserted-by":"crossref","unstructured":"Boyar, J., Frandsen, G., Sturtivant, C.: An arithmetic model of computation equivalent to threshold circuits. Theoret. Comput. Sci.\u00a093(2), 303\u2013319 (1992)","DOI":"10.1016\/0304-3975(92)90335-D"},{"key":"55_CR6","doi-asserted-by":"crossref","unstructured":"Eberly, W.: Very fast parallel polynomial arithmetic. SIAM Journal on Computing\u00a018(5), 955\u2013976 (1989)","DOI":"10.1137\/0218066"},{"key":"55_CR7","doi-asserted-by":"crossref","unstructured":"Fich, F.E., Tompa, M.: The parallel complexity of exponentiating polynomials over finite fields. J. Assoc. Comput. Mach.\u00a035(3), 651\u2013667 (1988)","DOI":"10.1145\/44483.44496"},{"key":"55_CR8","doi-asserted-by":"crossref","unstructured":"Frandsen, G.S., Valence, M., Barrington, D.A.M.: Some results on uniform arithmetic circuit complexity. Math. Systems Theory\u00a027(2), 105\u2013124 (1994)","DOI":"10.1007\/BF01195199"},{"key":"55_CR9","doi-asserted-by":"crossref","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory\u00a017(1), 13\u201327 (1984)","DOI":"10.1007\/BF01744431"},{"key":"55_CR10","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Modern cryptography, probabilistic proofs and pseudorandomness. Algorithms and Combinatorics, vol.\u00a017. Springer, Berlin (1999)","DOI":"10.1007\/978-3-662-12521-2"},{"key":"55_CR11","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Viola, E.: Fooling Parity Tests with Parity Gates. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 381\u2013392. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27821-4_34"},{"key":"55_CR12","unstructured":"H\u00e5stad, J.: Computational limitations of small-depth circuits. MIT Press, Cambridge (1987)"},{"key":"55_CR13","doi-asserted-by":"crossref","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. System Sci.\u00a065(4), 695\u2013716 (2002)","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"55_CR14","doi-asserted-by":"crossref","unstructured":"Kung, H.T.: On computing reciprocals of power series. Numerical Math.\u00a022, 341\u2013348 (1974)","DOI":"10.1007\/BF01436917"},{"key":"55_CR15","unstructured":"Morgensteren, M., Shamir, E.: Parallel Algorithms for Arithmetics, Irreducibility and Factoring of GFq-Polynomials. Stanford University Technical Report STAN-CS-83-991 (December 1983)"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Probabilistic Algorithms in Finite Fields. SIAM Journal on Computing\u00a09(2), 273\u2013280 (1980)","DOI":"10.1137\/0209024"},{"key":"55_CR17","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki\u00a041(4), 598\u2013607 (1987)","DOI":"10.1007\/BF01137685"},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"Reif, J.: Logarithmic depth circuits for algebraic functions. SIAM Journal on Computing\u00a015(1), 231\u2013242 (1986)","DOI":"10.1137\/0215017"},{"key":"55_CR19","doi-asserted-by":"crossref","unstructured":"Sieveking, M.: An algorithm for division of power series. Computing\u00a010, 153\u2013156 (1972)","DOI":"10.1007\/BF02242389"},{"key":"55_CR20","doi-asserted-by":"crossref","unstructured":"Sturtivant, C., Frandsen, G.S.: The computational efficacy of finite-field arithmetic. Theoret. Comput. Sci.\u00a0112(2), 291\u2013309 (1993)","DOI":"10.1016\/0304-3975(93)90022-L"},{"key":"55_CR21","doi-asserted-by":"crossref","unstructured":"van Lint, J.H.: Introduction to coding theory, 3rd edn. Springer, Heidelberg (1999)","DOI":"10.1007\/978-3-642-58575-3"},{"key":"55_CR22","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to circuit complexity. Springer, Berlin (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T23:31:41Z","timestamp":1555457501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11672142_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}