{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T23:29:21Z","timestamp":1677713361533},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T00:00:00Z","timestamp":1474588800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00037-016-0146-7","type":"journal-article","created":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T09:13:40Z","timestamp":1474622020000},"page":"583-625","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dual VP Classes"],"prefix":"10.1007","volume":"26","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"G\u00e1l","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"Mertz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,23]]},"reference":[{"key":"146_CR1","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jcss.1999.1675","volume":"60","author":"M. Agrawal","year":"2000","unstructured":"Agrawal M., Allender E., Datta S. (2000) On TC0, AC0, and Arithmetic Circuits. Journal of Computer and System Sciences 60: 395\u2013421","journal-title":"Journal of Computer and System Sciences"},{"key":"146_CR2","unstructured":"E. Allender & V. Gore (1994). A uniform circuit lower bound for the permanent. SIAM Journal on Computing 23, 1026\u201349."},{"key":"146_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"E. Allender","year":"1998","unstructured":"Allender E., Jiao J., Mahajan M., Vinay V. (1998) Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theoretical Computer Science 209: 47\u201386","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"146_CR4","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E. Allender","year":"1999","unstructured":"Allender E., Reinhardt K., Zhou S. (1999) Isolation, matching, and counting: Uniform and nonuniform upper bounds. Journal of Computer and System Sciences 59(2): 164\u2013181","journal-title":"Journal of Computer and System Sciences"},{"key":"146_CR5","doi-asserted-by":"crossref","unstructured":"Eric Allender, Anna G\u00e1l & Ian Mertz (2015). Dual VP Classes. In Proc. 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), number 9235 in Lecture Notes in Computer Science, 14\u201325. Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-662-48054-0_2"},{"key":"146_CR6","unstructured":"Eric Allender & Asa Goodwillie (2015). Arithmetic circuit classes over $${\\mathbb{Z}_m}$$ Z m . Technical Report 15-145, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"146_CR7","unstructured":"Eric Allender & Michal Kouck\u00fd (2010). Amplifying Lower Bounds by Means of Self-Reducibility. Journal of the ACM 57: 14:1 \u2013 14:36"},{"key":"146_CR8","unstructured":"R. Beigel & J. Tarui (1994). On ACC. Computational Complexity 4, 350\u2013366. Special issue on circuit complexity."},{"key":"146_CR9","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub & S. Smale (1998). Complexity and Real Computation. Springer.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"146_CR10","doi-asserted-by":"crossref","unstructured":"A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo & M. Tompa (1989). Two applications of inductive counting for complementation problems. SIAM Journal on Computing 18, 559\u2013578. See Erratum in SIAM J. Comput. 18, 1283.","DOI":"10.1137\/0218084"},{"key":"146_CR11","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Richard Cleve, Michal Kouck\u00fd, Bruno Loff & Florian Speelman (2014). Computing with a full memory: catalytic space. In ACM Symposium on Theory of Computing (STOC), 857\u2013866.","DOI":"10.1145\/2591796.2591874"},{"issue":"3","key":"146_CR12","first-page":"73","volume":"3","author":"B\u00fcrgisser Peter","year":"1999","unstructured":"Peter B\u00fcrgisser (1999) On the Structure of Valiant\u2019s Complexity Classes. Discrete Mathematics & Theoretical Computer Science 3(3): 73\u201394","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"issue":"1","key":"146_CR13","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0304-3975(99)00183-8","volume":"235","author":"B\u00fcrgisser Peter","year":"2000","unstructured":"Peter B\u00fcrgisser (2000) Cook\u2019s versus Valiant\u2019s hypothesis. Theoretical Computer Science 235(1): 71\u201388","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"146_CR14","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"Caussinus Herv\u00e9","year":"1998","unstructured":"Herv\u00e9 Caussinus, Pierre McKenzie, Denis Th\u00e9rien, Heribert Vollmer (1998) Nondeterministic NC1 Computation. Journal of Computer and System Sciences 57(2): 200\u2013212","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"146_CR15","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/S0097539793250330","volume":"24","author":"Chari Suresh","year":"1995","unstructured":"Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan (1995) Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems. SIAM Journal on Computing 24(5): 1036\u20131050","journal-title":"SIAM Journal on Computing"},{"key":"146_CR16","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu A., Davida G.I., Litow B. (2001) Division in logspace-uniform NC 1. RAIRO Theoretical Informatics and Applications 35: 259\u2013276","journal-title":"RAIRO Theoretical Informatics and Applications"},{"issue":"2","key":"146_CR17","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1006\/jnth.1997.2114","volume":"64","author":"Capi Corrales-Rodrig\u00e1\u00f1ez","year":"1997","unstructured":"Corrales-Rodrig\u00e1\u00f1ez Capi, Schoof Ren\u00e9 (1997) The support problem and its elliptic analogue. Journal of Number Theory 64(2): 276\u2013290","journal-title":"Journal of Number Theory"},{"issue":"3","key":"146_CR18","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"Ofer Gabber","year":"1981","unstructured":"Gabber Ofer, Galil Zvi (1981) Explicit Constructions of Linear-Sized Superconcentrators. Journal of Computer and System Sciences 22(3): 407\u2013420","journal-title":"Journal of Computer and System Sciences"},{"key":"146_CR19","unstructured":"Anna G\u00e1l (1995). Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic. Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995 82\u201387."},{"issue":"1-2","key":"146_CR20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<99::AID-RSA7>3.0.CO;2-6","volume":"9","author":"Anna G\u00e1l","year":"1996","unstructured":"G\u00e1l Anna, Wigderson Avi (1996) Boolean complexity classes vs. their arithmetic analogs. Random Struct. Algorithms 9(1-2): 99\u2013111","journal-title":"Random Struct. Algorithms"},{"key":"146_CR21","unstructured":"Michael Hahn, Andreas Krebs, Klaus-J\u00f6rn Lange & Michael Ludwig (2015). Visibly Counter Languages and the Structure of NC1. In Symposium on Mathematical Foundations of Computer Science (MFCS), number 9235 in Lecture Notes in Computer Science, 384\u2013394. Springer."},{"key":"146_CR22","doi-asserted-by":"crossref","unstructured":"Kristoffer Arnsfelt Hansen & Michal Kouck\u00fd (2010). A New Characterization of ACC0 and Probabilistic CC0. Computational Complexity 19(2), 211\u2013234.","DOI":"10.1007\/s00037-010-0287-z"},{"key":"146_CR23","doi-asserted-by":"crossref","unstructured":"William Hesse, Eric Allender & David A. Mix Barrington (2002). Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication. Journal of Computer and System Sciences 65, 695\u2013716.","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"146_CR24","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"Immerman N., Landau S. (1995) The Complexity of Iterated Multiplication. Information and Computation 116: 103\u2013116","journal-title":"Information and Computation"},{"key":"146_CR25","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & David Zuckerman (1989). How to Recycle Random Bits. In IEEE Symposium on Foundations of Computer Science (FOCS), 248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"issue":"1","key":"146_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-011-0002-8","volume":"20","author":"Koiran Pascal","year":"2011","unstructured":"Pascal Koiran, Sylvain Perifel (2011) Interpolation in Valiant\u2019s Theory. Computational Complexity 20(1): 1\u201320","journal-title":"Computational Complexity"},{"issue":"1","key":"146_CR27","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"Malod Guillaume","year":"2008","unstructured":"Guillaume Malod, Natacha Portier (2008) Characterizing Valiant\u2019s algebraic complexity classes. J. Complexity 24(1): 16\u201338","journal-title":"J. Complexity"},{"key":"146_CR28","doi-asserted-by":"crossref","unstructured":"Cristopher Moore, Denis Th\u00e9rien, Fran\u00e7ois Lemieux, Joshua Berman & Arthur Drisko (2000). Circuits and Expressions with Nonassociative Gates. Journal of Computer and System Sciences 60(2), 368\u2013394.","DOI":"10.1006\/jcss.1999.1673"},{"key":"146_CR29","doi-asserted-by":"crossref","first-page":"896","DOI":"10.1137\/0221053","volume":"21","author":"J. Reif","year":"1992","unstructured":"Reif J., Tate S. (1992) On threshold circuits and polynomial computation. SIAM Journal on Computing 21: 896\u2013908","journal-title":"SIAM Journal on Computing"},{"key":"146_CR30","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K. Reinhardt","year":"2000","unstructured":"Reinhardt K., Allender E. (2000) Making Nondeterminism Unambiguous. SIAM Journal on Computing 29: 1118\u20131131","journal-title":"SIAM Journal on Computing"},{"key":"146_CR31","doi-asserted-by":"crossref","unstructured":"R. Smolensky (1987). Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In ACM Symposium on Theory of Computing (STOC), 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"146_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing H. (1994) Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston"},{"issue":"4","key":"146_CR33","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF01263425","volume":"4","author":"Denis Th\u00e9rien","year":"1994","unstructured":"Th\u00e9rien Denis (1994) Circuits constructed with MOD q gates cannot compute \u201cAND\u201d in sublinear size. Computational Complexity 4(4): 383\u2013388","journal-title":"Computational Complexity"},{"key":"146_CR34","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda S. (1991) PP Is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing 20: 865\u2013877","journal-title":"SIAM Journal on Computing"},{"key":"146_CR35","doi-asserted-by":"crossref","unstructured":"L.G. Valiant (1979). Completeness classes in algebra. In Proc. 11th ACM STOC, 249\u2013261.","DOI":"10.1145\/800135.804419"},{"issue":"4","key":"146_CR36","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L.G. Valiant","year":"1983","unstructured":"Valiant L.G., Skyum S., Berkowitz S., Rackoff C. (1983) Fast parallel computation of polynomials using few processors. SIAM Journal on Computing 12(4): 641\u2013644","journal-title":"SIAM Journal on Computing"},{"key":"146_CR37","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"Venkateswaran H. (1991) Properties That Characterize LOGCFL. Journal of Computer and System Sciences 43: 380\u2013404","journal-title":"Journal of Computer and System Sciences"},{"key":"146_CR38","doi-asserted-by":"crossref","unstructured":"V Vinay (1991). Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of 6th Structure in Complexity Theory Conference, 270\u2013284.","DOI":"10.1109\/SCT.1991.160269"},{"key":"146_CR39","doi-asserted-by":"crossref","unstructured":"H. Vollmer (1999). Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"146_CR40","unstructured":"J. von zur Gathen (1993). Parallel linear algebra. In Synthesis of Parallel Algorithms, J. Reif, editor, 574\u2013615. Morgan Kaufmann."},{"key":"146_CR41","doi-asserted-by":"crossref","unstructured":"William P Wardlaw (1994). Matrix representation of finite fields. Mathematics Magazine 289\u2013293.","DOI":"10.2307\/2690850"},{"issue":"1","key":"146_CR42","first-page":"2","volume":"61","author":"Ryan Williams","year":"2014","unstructured":"Williams Ryan (2014) Nonuniform ACC circuit lower bounds. Journal of the ACM 61(1): 2","journal-title":"Journal of the ACM"},{"key":"146_CR43","doi-asserted-by":"crossref","first-page":"65","DOI":"10.4064\/aa150-1-4","volume":"150","author":"T. Xylouris","year":"2011","unstructured":"Xylouris T. (2011) On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions. Acta Arithmetica 150: 65\u201391","journal-title":"Acta Arithmetica"},{"key":"146_CR44","unstructured":"Andrew Chi-Chih Yao (1990). On ACC and Threshold Circuits. In IEEE Symposium on Foundations of Computer Science (FOCS), 619\u2013627."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0146-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0146-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0146-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T23:04:13Z","timestamp":1568415853000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0146-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,23]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["146"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0146-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9,23]]}}}