{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T08:39:54Z","timestamp":1765960794142},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00224-013-9519-3","type":"journal-article","created":{"date-parts":[[2013,11,30]],"date-time":"2013-11-30T02:14:57Z","timestamp":1385777697000},"page":"318-336","source":"Crossref","is-referenced-by-count":3,"title":["Balancing Bounded Treewidth Circuits"],"prefix":"10.1007","volume":"54","author":[{"given":"Maurice","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,12,1]]},"reference":[{"key":"9519_CR1","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-540-73001-9_3","volume-title":"Computation and Logic in the Real World","author":"E. Allender","year":"2007","unstructured":"Allender, E.: Reachability problems: an update. In: Computation and Logic in the Real World. Lect. Notes in Comp. Sci., vol. 4497, pp. 25\u201327. Springer, Berlin (2007)"},{"key":"9519_CR2","doi-asserted-by":"crossref","unstructured":"Arvind, V., Joglekar, P., Srinivasan, S.: On lower bounds for constant width arithmetic circuits. ISAAC 2009. Technical Report ECCC TR09-73, Electronic Colloquium in Computational Complexity (2009, to appear)","DOI":"10.1007\/978-3-642-10631-6_65"},{"key":"9519_CR3","first-page":"254","volume-title":"Proc. 20th Annual ACM Symposium on the Theory of Computing","author":"M. Ben-Or","year":"1988","unstructured":"Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. In: Proc. 20th Annual ACM Symposium on the Theory of Computing, pp. 254\u2013257 (1988)"},{"key":"9519_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-50728-0_32","volume-title":"Proc. 14th Workshop on Graph-Theoretic Concepts in Comp. Sc. (WG\u201988)","author":"H.L. Bodlaender","year":"1989","unstructured":"Bodlaender, H.L.: NC-algorithms for graphs with small treewidth. In: Proc. 14th Workshop on Graph-Theoretic Concepts in Comp. Sc. (WG\u201988). LNCS, vol. 344, pp. 1\u201310. Springer, Berlin (1989)"},{"key":"9519_CR5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. Brent","year":"1974","unstructured":"Brent, R.: The parallel evaluation of general arithmetic expressions. J. ACM 21, 201\u2013206 (1974)","journal-title":"J. ACM"},{"key":"9519_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Claussen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer, Berlin (1997)"},{"key":"9519_CR7","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"215","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010)","author":"B. Das","year":"2010","unstructured":"Das, B., Datta, S., Nimbhorkar, P.: Log-space algorithms for paths and matchings in k-trees. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010). Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 215\u2013226 (2010)"},{"issue":"2","key":"9519_CR8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are logspace comp lete for P. SIGACT News 9(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"key":"9519_CR9","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-642-03351-3_18","volume-title":"Proceedings of the 4th International Computer Science Symposium in Russia (CSR2009)","author":"M. Jansen","year":"2009","unstructured":"Jansen, M., Rao, B.V.R.: Simulation of arithmetical circuits by branching programs with preservation of constant width and syntactic multilinearity. In: Proceedings of the 4th International Computer Science Symposium in Russia (CSR2009). Lect. Notes in Comp. Sci., vol. 5675, pp. 179\u2013190. Springer, Berlin (2009)"},{"key":"9519_CR10","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"Jones, N.: Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11, 68\u201385 (1975). Corrigendum: J. Comput. Syst. Sci. 15, 241 (1977)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9519_CR11","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00037-009-0265-5","volume":"18","author":"N. Limaye","year":"2009","unstructured":"Limaye, N., Mahajan, M., Jayalal Sarma, M.N.: Upper bounds for monotone planar circuit value and variants. Comput. Complex. 18(3), 377\u2013412 (2009)","journal-title":"Comput. Complex."},{"key":"9519_CR12","unstructured":"Mahajan, M.: Polynomial size log depth circuits: between NC1 and AC1. Technical Report 91, BEATCS Computational Complexity Column (2007)"},{"key":"9519_CR13","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-3-540-85238-4_37","volume-title":"Proc. 33rd International Symposium on Mathematical Foundations of Computer Science","author":"M. Mahajan","year":"2008","unstructured":"Mahajan, M., Rao, B.V.R.: Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae. In: Proc. 33rd International Symposium on Mathematical Foundations of Computer Science. Lect. Notes in Comp. Sci., vol. 5162, pp. 455\u2013466 (2008)"},{"key":"9519_CR14","series-title":"Lect. Notes in Comp. Sci.","first-page":"455","volume-title":"Proc. 17th International Conference on Fundamentals of Computation Theory","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Rao, B.V.R.: Small-space analogues of Valiant\u2019s classes. In: Proc. 17th International Conference on Fundamentals of Computation Theory. Lect. Notes in Comp. Sci., vol. 5699, pp. 455\u2013466 (2009)"},{"issue":"1","key":"9519_CR15","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"G. Malod","year":"2008","unstructured":"Malod, G., Portier, N.: Characterizing Valiant\u2019s algebraic complexity classes. J. Complex. 24(1), 16\u201338 (2008)","journal-title":"J. Complex."},{"key":"9519_CR16","first-page":"1","volume-title":"Proc. 18th Annual ACM Symposium on the Theory of Computing","author":"D. Mix Barrington","year":"1986","unstructured":"Mix Barrington, D.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. In: Proc. 18th Annual ACM Symposium on the Theory of Computing, pp. 1\u20135 (1986)"},{"key":"9519_CR17","first-page":"24","volume-title":"IEEE Conference on Computational Complexity","author":"D.A. Mix Barrington","year":"1999","unstructured":"Mix Barrington, D.A., Lu, C.-J., Bro Miltersen, P., Skyum, S.: On monotone planar circuits. In: IEEE Conference on Computational Complexity, pp. 24\u201331 (1999)"},{"key":"9519_CR18","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/FOCS.2004.42","volume-title":"Proc. 45th Annual IEEE Symposium on Foundations of Computer Science","author":"R. Raz","year":"2004","unstructured":"Raz, R.: Separation of multilinear circuit and formula size. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 344\u2013351 (2004)"},{"key":"9519_CR19","first-page":"376","volume-title":"Proc. 37th Annual ACM Symposium on the Theory of Computing","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proc. 37th Annual ACM Symposium on the Theory of Computing, pp. 376\u2013385 (2005)"},{"issue":"4","key":"9519_CR20","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/S0022-0000(73)80031-5","volume":"7","author":"W.J. Savitch","year":"1973","unstructured":"Savitch, W.J.: Maze recognizing automata and nondeterministic tape complexity. J. Comput. Syst. Sci. 7(4), 389\u2013403 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"9519_CR21","doi-asserted-by":"crossref","unstructured":"Till Tantau, Elberfeld, M., Jakoby, A.: Logspace versions of the theorems of bodlaender and courcelle. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). Technical report ECCC-TR10-062 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"key":"9519_CR22","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12, 641\u2013644 (1983)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9519-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9519-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9519-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T07:56:44Z","timestamp":1564905404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9519-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9519"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9519-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,1]]}}}