{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T05:12:06Z","timestamp":1741324326077,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_62","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"736-747","source":"Crossref","is-referenced-by-count":1,"title":["On the Power of Algebraic Branching Programs of Width Two"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Fengming","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"62_CR1","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jcss.1999.1675","volume":"60","author":"M. Agrawal","year":"2000","unstructured":"Agrawal, M., Allender, E., Datta, S.: On TC0, AC0, and arithmetic circuits. Journal of Computer and System Sciences\u00a060, 395\u2013421 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"62_CR2","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Kraj\u00ed\u010dek, J. (ed.) Complexity of Computations and Proofs. Quaderni di Matematica, vol.\u00a013, pp. 33\u201372. Seconda Universit\u00e0 di Napoli (2004)"},{"key":"62_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-48523-6_12","volume-title":"Automata, Languages and Programming","author":"A. Ambainis","year":"1999","unstructured":"Ambainis, A., Allender, E., Barrington, D.A.M., Datta, S., L\u00eaThanh, H.: Bounded depth arithmetic circuits: Counting and closure. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 149\u2013158. Springer, Heidelberg (1999)"},{"key":"62_CR4","unstructured":"Barrington, D.A.: Width-3 permutation branching programs. Technical Report Technical Memorandum MIT\/LCS\/TM-293, MIT (1985)"},{"key":"62_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 254\u2013257 (1988)","DOI":"10.1145\/62212.62236"},{"issue":"1","key":"62_CR6","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing\u00a021(1), 54\u201358 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"62_CR7","doi-asserted-by":"publisher","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.: Nondeterministic $\\mbox{\\rm NC$^1$}$ computation. Journal of Computer and System Sciences\u00a057, 200\u2013212 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"62_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-540-85238-4_33","volume-title":"Mathematical Foundations of Computer Science 2008","author":"M.J. Jansen","year":"2008","unstructured":"Jansen, M.J.: Lower bounds for syntactically multilinear algebraic branching programs. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 407\u2013418. Springer, Heidelberg (2008)"},{"key":"62_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-03351-3_18","volume-title":"Computer Science - Theory and Applications","author":"M.J. Jansen","year":"2009","unstructured":"Jansen, M.J., Raghavendra Rao, B.V.: Simulation of arithmetical circuits by branching programs with preservation of constant width and syntactic multilinearity. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol.\u00a05675, pp. 179\u2013190. Springer, Heidelberg (2009)"},{"key":"62_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BFb0028801","volume-title":"Fundamentals of Computation Theory","author":"H. Jung","year":"1985","unstructured":"Jung, H.: Depth efficient transformations of arithmetic into Boolean circuits. In: Budach, L. (ed.) FCT 1985. LNCS, vol.\u00a0199, pp. 167\u2013173. Springer, Heidelberg (1985)"},{"key":"62_CR11","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R. Lipton","year":"1977","unstructured":"Lipton, R., Zalcstein, Y.: Word problems solvable in logspace. Journal of the ACM\u00a024, 522\u2013526 (1977)","journal-title":"Journal of the ACM"},{"key":"62_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-03409-1_23","volume-title":"Fundamentals of Computation Theory","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raghavendra Rao, B.V.: Small-space analogues of valiant\u2019s classes. In: Kuty\u0142owski, M., Charatonik, W., G\u0119bala, M. (eds.) FCT 2009. LNCS, vol.\u00a05699, pp. 250\u2013261. Springer, Heidelberg (2009)"},{"key":"62_CR13","unstructured":"Mahajan, M., Saurabh, N., Sreenivasaiah, K.: Counting paths in planar width 2 branching programs (2011) (manuscript)"},{"key":"62_CR14","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"key":"62_CR15","unstructured":"Robinson, D.: Parallel algorithms for group word problems. PhD thesis, Univ. of California, San Diego (1993)"},{"key":"62_CR16","unstructured":"Saha, C., Saptharishi, R., Saxena, N.: The power of depth 2 circuits over algebras. In: Proc. Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), pp. 371\u2013382 (2009)"},{"key":"62_CR17","unstructured":"Saha, C.: Private communication (2011)"},{"key":"62_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.: Completeness classes in algebra. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T11:29:40Z","timestamp":1741260580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}