{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:58Z","timestamp":1759063498810},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,10,20]],"date-time":"2011-10-20T00:00:00Z","timestamp":1319068800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00037-011-0024-2","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T05:56:46Z","timestamp":1319003806000},"page":"1-38","source":"Crossref","is-referenced-by-count":6,"title":["Small Space Analogues of Valiant\u2019s Classes and the Limitations of Skew Formulas"],"prefix":"10.1007","volume":"22","author":[{"given":"Meena","family":"Mahajan","sequence":"first","affiliation":[]},{"given":"B. V.","family":"Raghavendra Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,20]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Sanjeev Arora","year":"2009","unstructured":"Sanjeev Arora , Boaz Barak (2009) Computational Complexity: A Modern Approach. Cambridge University Press, New York, USA ISBN 0521424267, 9780521424264"},{"key":"24_CR2","unstructured":"Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan (2010).On Lower Bounds for Constant Width Arithmetic Circuits. In: ISAAC, Yingfei Dong, Ding-Zhu Du, Oscar Ibarra editors, Lecture Notes in Computer Science, 637\u2013646. Springer Berlin\/Heidelberg"},{"issue":"1","key":"24_CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"David A. Mix Barrington","year":"1989","unstructured":"David A. Mix Barrington (1989) Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. Journal of Computer and System Sciences 38(1): 150\u2013164","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR4","unstructured":"Lenore Blum, Felipe Cucker, Mike Shub & Steve Smale (1997). Complexity and Real Computation. Springer."},{"issue":"4","key":"24_CR5","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"Allan Borodin","year":"1977","unstructured":"Allan Borodin (1977) On Relating Time and Space to Size and Depth. SIAM J. Comput. 6(4): 733\u2013744","journal-title":"SIAM J. Comput."},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen & M. A. Shokrollahi (1997). Algebraic Complexity Theory. Springer-Verlag.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser (2000). Completeness and Reduction in Algebraic Complexity Theory. Algorithms and Computation in Mathematics. Springer-Verlag.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"24_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"Herv\u00e9 Caussinus","year":"1998","unstructured":"Herv\u00e9 Caussinus, Pierre McKenzie, Denis Th\u00e9rien, Heribert Vollmer (1998) Nondeterministic NC1 Computation. Journal of Computer and System Sciences 57: 200\u2013212","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR9","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"A. Chiu","year":"2001","unstructured":"Chiu A., G. Davida, B. Litow (2001) Division in Logspace-Uniform NC1. RAIRO Theoretical Informatics and Applications 35: 259\u2013276","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"24_CR10","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"Cook S. (1971) Characterizations of pushdown machines in terms of time-bounded computers. Journal of Association for Computing Machinery 18: 4\u201318","journal-title":"Journal of Association for Computing Machinery"},{"key":"24_CR11","unstructured":"Stephen A. Cook (1979). Deterministic CFL\u2019s Are Accepted Simultaneously in Polynomial Time and Log Squared Space. In Proceedings of the ACM Symposium on Theory of Computing STOC, 338\u2013345."},{"issue":"4","key":"24_CR12","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1007\/s00224-009-9241-3","volume":"46","author":"Uffe Flarup","year":"2010","unstructured":"Uffe Flarup, Laurent Lyaudet (2010) On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth\/Cliquewidth. Theory Comput. Syst. 46(4): 761\u2013791","journal-title":"Theory Comput. Syst."},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Raymond Greenlaw, James Hoover & Walter Ruzzo (1995). Limits To Parallel computation: P-Completeness Theory. Oxford University Press.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Maurice Jansen & Jayalal M. N. Sarma (2010). Balancing Bounded Treewidth Circuits. In CSR, volume 6072 of Lecture Notes in Computer Science, 228\u2013239.","DOI":"10.1007\/978-3-642-13182-0_21"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Maurice J. Jansen (2008). Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. In MFCS, 407\u2013418.","DOI":"10.1007\/978-3-540-85238-4_33"},{"key":"24_CR16","unstructured":"Maurice J. Jansen & B. V. Raghavendra Rao (2009). Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity. In CSR, 179\u2013190."},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"David S. Johnson (1990). A Catalog of Complexity Classes. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), Jan van Leeuwen, editor, 67\u2013161. Elsevier and MIT Press.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen & Pascal Koiran (2008). Expressing a fraction of two determinants as a determinant. In ISSAC, 141\u2013146.","DOI":"10.1145\/1390768.1390790"},{"issue":"50","key":"24_CR19","doi-asserted-by":"crossref","first-page":"5244","DOI":"10.1016\/j.tcs.2009.08.026","volume":"410","author":"Pascal Koiran","year":"2009","unstructured":"Pascal Koiran, Sylvain Perifel (2009) VPSPACE and a transfer theorem over the complex field. Theor. Comput. Sci. 410(50): 5244\u20135251","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"24_CR20","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s00037-009-0269-1","volume":"18","author":"Pascal Koiran","year":"2009","unstructured":"Pascal Koiran, Sylvain Perifel (2009) VPSPACE and a Transfer Theorem over the Reals. Computational Complexity 18(4): 551\u2013575","journal-title":"Computational Complexity"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Nutan Limaye, Meena Mahajan & B. V. Raghavendra Rao (2010). Arithmetizing Classes Around NC1 and L. Theory of Computing Systems 46(3), 499\u2013522. Preliminary version in STACS 2007, LNCS vol. 4393\u00a0pp. 477\u2013488.","DOI":"10.1007\/s00224-009-9233-3"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Meena Mahajan & B. V. Raghavendra Rao (2009). Small-Space Analogues of Valiant\u2019s Classes. In 17th International Symposium on Fundamentals of Computation Theory, FCT, 250\u2013261.","DOI":"10.1007\/978-3-642-03409-1_23"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Guillaume Malod (2007). The Complexity of Polynomials and Their Coefficient Functions. In IEEE Conference on Computational Complexity, 193\u2013204.","DOI":"10.1109\/CCC.2007.33"},{"issue":"1","key":"24_CR24","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"Guillaume Malod","year":"2008","unstructured":"Guillaume Malod, Natacha Portier (2008) Characterizing Valiant\u2019s algebraic complexity classes. J. Complexity 24(1): 16\u201338","journal-title":"J. Complexity"},{"issue":"7","key":"24_CR25","first-page":"435","volume":"309","author":"Christian Michaux","year":"1989","unstructured":"Christian Michaux (1989) Une remarque \u00e0 propos des machines sur $${\\mathbb{R}}$$ introduites par Blum, Shub et Smale. Comptes Rendus de l\u2019Acad\u00e9mie des Sciences de Paris 309(7): 435\u2013437","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences de Paris"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Paulin Jacob\u00e9 de Naurois (2006). A Measure of Space for Computing over the Reals. In CiE, 231\u2013240.","DOI":"10.1007\/11780342_25"},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1995). On the complexity of bilinear forms. In STOC \u201995: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 723\u2013732. ACM, New York, NY, USA.","DOI":"10.1145\/225058.225290"},{"key":"24_CR28","doi-asserted-by":"crossref","unstructured":"Nicholas Pippenger (1979). On Simultaneous Resource Bounds. In 20th Annual Symposium on Foundations of Computer Science FOCS, 307\u2013311.","DOI":"10.1109\/SFCS.1979.29"},{"key":"24_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"Amir Shpilka","year":"2002","unstructured":"Amir Shpilka, Avi Wigderson (2002) Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10: 1\u201327 ISSN 1016-3328","journal-title":"Computational Complexity"},{"key":"24_CR30","unstructured":"Seinosuke Toda (1991). Counting problems computationally equivalent to the determinant. Technical Report CSIM 91-07, Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo."},{"key":"24_CR31","first-page":"116","volume":"E75-D","author":"Seinosuke Toda","year":"1992","unstructured":"Seinosuke Toda (1992) Classes of arithmetic circuits capturing the complexity of computing the determinant. IEICE Transactions on Informations and Systems E75-D: 116\u2013124","journal-title":"IEICE Transactions on Informations and Systems"},{"key":"24_CR32","unstructured":"Iddo Tzamaret (2008). Studies in Algebraic and Propositional Proof Complexity. Ph.D. thesis, Tel Aviv University."},{"key":"24_CR33","doi-asserted-by":"crossref","unstructured":"L. G. Valiant (1979). Completeness classes in algebra. In STOC \u201979: Proceedings of the eleventh annual ACM symposium on Theory of computing, 249\u2013261. ACM, New York, NY, USA.","DOI":"10.1145\/800135.804419"},{"key":"24_CR34","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","volume":"13","author":"Leslie G. Valiant","year":"1976","unstructured":"Leslie G. Valiant (1976) Graph-theoretic properties in Computational Complexity. Journal of Computer and System Sciences 13: 278\u2013285","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR35","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"Leslie G. Valiant","year":"1979","unstructured":"Leslie G. Valiant (1979) The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189\u2013201","journal-title":"Theor. Comput. Sci."},{"key":"24_CR36","first-page":"365","volume":"30","author":"Leslie G. Valiant","year":"1982","unstructured":"Leslie G. Valiant (1982) Reducibility by algebraic projections. Logic and Algorithmic: an International Symposium held in honour of Ernst Specker 30: 30, 365\u2013380","journal-title":"Logic and Algorithmic: an International Symposium held in honour of Ernst Specker"},{"key":"24_CR37","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"Venkateswaran H. (1992) Circuit Definitions of Nondeterministic Complexity Classes. SIAM Journal on Computing 21: 655\u2013670","journal-title":"SIAM Journal on Computing"},{"key":"24_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":"24_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"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0024-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0024-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0024-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,10]],"date-time":"2023-06-10T15:38:53Z","timestamp":1686411533000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0024-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,20]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["24"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0024-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,20]]}}}