{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T03:51:36Z","timestamp":1794369096784,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642106309","type":"print"},{"value":"9783642106316","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10631-6_65","type":"book-chapter","created":{"date-parts":[[2009,12,4]],"date-time":"2009-12-04T02:03:43Z","timestamp":1259892223000},"page":"637-646","source":"Crossref","is-referenced-by-count":3,"title":["On Lower Bounds for Constant Width Arithmetic Circuits"],"prefix":"10.1007","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pushkar S.","family":"Joglekar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"65_CR1","doi-asserted-by":"crossref","unstructured":"Arvind, V., Joglekar, P., Srinivasan, S.: On Lower Bounds for Constant Width Arithmetic Circuits. In: Electronic Colloquium of Computational Complexity, TR09-073, http:\/\/eccc.hpi-web.de\/report\/2009\/073\/","DOI":"10.1007\/978-3-642-10631-6_65"},{"key":"65_CR2","unstructured":"Ben-Or, M.: Unpublished notes"},{"issue":"1","key":"65_CR3","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 J. Comput.\u00a021(1), 54\u201358 (1992)","journal-title":"SIAM J. Comput."},{"key":"65_CR4","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Shpilka, A., Yehudayoff, A.: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. In: Proc. Symp. on Theory of Computing, pp. 741\u2013748 (2008)","DOI":"10.1145\/1374376.1374482"},{"key":"65_CR5","doi-asserted-by":"crossref","unstructured":"Jansen, M., Raghavendra Rao, B.V.: Simulation of arithmetical circuits by branching programs preserving constant width and syntactic multilinearity. In: CSR (2009)","DOI":"10.1007\/978-3-642-03351-3_18"},{"key":"65_CR6","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomization of polynomial identity tests means proving circuit lower bounds. In: Proc. of the thirty-fifth annual ACM Sym. on Theory of computing, pp. 355\u2013364 (2003)","DOI":"10.1145\/780591.780595"},{"key":"65_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-70918-3_41","volume-title":"STACS 2007","author":"N. Limaye","year":"2007","unstructured":"Limaye, N., Mahajan, M., Raghavendra Rao, B.V.: Arithmetizing classes around NC1 and L. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 477\u2013488. Springer, Heidelberg (2007); Preliminary version in STACS 2007"},{"key":"65_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-540-85238-4_37","volume-title":"Mathematical Foundations of Computer Science 2008","author":"M. Mahajan","year":"2008","unstructured":"Mahajan, M., Raghavendra Rao, B.V.: Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 455\u2013466. Springer, Heidelberg (2008)"},{"key":"65_CR9","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation. In: Proc. of the 23rd annual ACM Sym. on Theory of computing, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"issue":"1","key":"65_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non commutative models. Computational Complexity\u00a014(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"issue":"2","key":"65_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"R. Raz","year":"2009","unstructured":"Raz, R., Yehudayoff, A.: Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity\u00a018(2), 171\u2013207 (2009)","journal-title":"Computational Complexity"},{"key":"65_CR12","doi-asserted-by":"crossref","unstructured":"Snir, M.: On the Size Complexity of Monotone Formulas. In: Proc. 7th Intl. Colloquium on Algorithms Languages and Programming, pp. 621\u2013631 (1980)","DOI":"10.1007\/3-540-10003-2_103"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10631-6_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:32:20Z","timestamp":1606167140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10631-6_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642106309","9783642106316"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6_65","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-10631-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}