{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:53:32Z","timestamp":1758272012166},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,11,5]],"date-time":"2015-11-05T00:00:00Z","timestamp":1446681600000},"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":["comput. complex."],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00037-015-0114-7","type":"journal-article","created":{"date-parts":[[2015,11,5]],"date-time":"2015-11-05T12:49:27Z","timestamp":1446727767000},"page":"217-253","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the power of algebraic branching programs of width two"],"prefix":"10.1007","volume":"25","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Fengming","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,5]]},"reference":[{"key":"114_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":"114_CR2","doi-asserted-by":"crossref","unstructured":"M. Agrawal, R. Gurjar, A. Korwar & N. Saxena (2015).Hitting- Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM Journal on Computing 44(3), 669\u2013697. doi: 10.1137\/140975103 .","DOI":"10.1137\/140975103"},{"key":"114_CR3","unstructured":"E. Allender (2004). Arithmetic Circuits and Counting Complexity Classes. In Complexity of Computations and Proofs, J. Kraj\u00ed\u010dek, editor, volume 13 of Quaderni di Matematica, 33\u201372. Seconda Universit\u00e0 di Napoli."},{"key":"114_CR4","unstructured":"A. Ambainis, E. Allender, D. A. M. Barrington, S. Datta & H. L\u00eaThanh (1999). Bounded Depth Arithmetic Circuits: Counting and Closure. In Proc. ICALP, number 1644 in Lecture Notes in Computer Science, 149\u2013158. Springer."},{"key":"114_CR5","unstructured":"D. A. Barrington (1985). Width-3 Permutation Branching Programs. Technical Report Technical Memorandum MIT\/LCS\/TM-293, MIT."},{"key":"114_CR6","unstructured":"M. Ben-Or & R. Cleve (1988). Computing Algebraic Formulas Using a Constant Number of Registers. In Proc. ACM Symp. on Theory of Computing (STOC), 254\u2013257."},{"issue":"1","key":"114_CR7","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M Ben-Or","year":"1992","unstructured":"Ben-Or M, Cleve R (1992) Computing Algebraic Formulas Using a Constant Number of Registers. SIAM Journal on Computing 21(1): 54\u201358","journal-title":"SIAM Journal on Computing"},{"key":"114_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H Caussinus","year":"1998","unstructured":"Caussinus H, McKenzie P, Th\u00e9rien D, Vollmer H (1998) Nondeterministic NC1 computation. Journal of Computer and System Sciences 57: 200\u2013212","journal-title":"Journal of Computer and System Sciences"},{"key":"114_CR10","doi-asserted-by":"crossref","unstructured":"M. J. Jansen, M. Mahajan & B. V. Raghavendra Rao (2013). Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits. Computational Complexity 22(3), 517\u2013564.","DOI":"10.1007\/s00037-013-0072-x"},{"key":"114_CR11","doi-asserted-by":"crossref","unstructured":"H. Jung (1985). Depth efficient transformations of arithmetic into Boolean circuits. In Proc. FCT, number 199 in Lecture Notes in Computer Science, 167\u2013173. Springer.","DOI":"10.1007\/BFb0028801"},{"key":"114_CR12","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R Lipton","year":"1977","unstructured":"Lipton R, Zalcstein Y (1977) Word problems solvable in logspace. Journal of the ACM 24: 522\u2013526","journal-title":"Journal of the ACM"},{"issue":"1","key":"114_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-011-0024-2","volume":"22","author":"M Mahajan","year":"2013","unstructured":"Mahajan M, Raghavendra Rao B.V (2013) Small Space Analogues of Valiant\u2019s Classes and the Limitations of Skew Formulas. Computational Complexity 22(1): 1\u201338","journal-title":"Computational Complexity"},{"key":"114_CR14","unstructured":"Meena Mahajan, Nitin Saurabh & Karteek Sreenivasaiah (2012). Counting paths in planar width 2 branching programs. In Proc. 18th Computing: The Australasian Theory Symposium, (CATS 2012), volume 128 of CRPIT, 59\u201368. Australian Computer Society."},{"key":"114_CR15","unstructured":"N. Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In Proc. ACM Symp. on Theory of Computing (STOC), 410\u2013418."},{"key":"114_CR16","unstructured":"D. Robinson (1993). Parallel algorithms for group word problems. Ph.D. thesis, Univ. of California, San Diego."},{"key":"114_CR17","unstructured":"C. Saha, R. Saptharishi & N. Saxena (2009). The Power of Depth 2 Circuits over Algebras. In Proc. Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 371\u2013382."},{"key":"114_CR18","unstructured":"Chandan Saha (2011). Private communication."},{"key":"114_CR19","doi-asserted-by":"crossref","unstructured":"L. Valiant (1979). Completeness classes in algebra. In Proc. ACM Symp. on Theory of Computing (STOC), 249\u2013261.","DOI":"10.1145\/800135.804419"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0114-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0114-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0114-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0114-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,5]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["114"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0114-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,5]]}}}