{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:30:02Z","timestamp":1725795002814},"publisher-location":"Cham","reference-count":11,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_6","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"65-76","source":"Crossref","is-referenced-by-count":0,"title":["On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains"],"prefix":"10.1007","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[]},{"given":"S.","family":"Raja","sequence":"additional","affiliation":[]},{"given":"A. V.","family":"Sreejith","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-40164-0_17","volume-title":"Fundamentals of Computation Theory","author":"J. Boyar","year":"2013","unstructured":"Boyar, J., Find, M.G.: Cancellation-free circuits in unbounded and bounded depth. In: G\u0105sieniec, L., Wolter, F. (eds.) FCT 2013. LNCS, vol.\u00a08070, pp. 159\u2013170. Springer, Heidelberg (2013)"},{"issue":"7","key":"6_CR2","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Transactions on Information Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000063","volume":"9","author":"S. Jukna","year":"2013","unstructured":"Jukna, S., Sergeev, I.: Complexity of linear boolean operators. Foundations and Trends in Theoretical Computer Science\u00a09(1), 1\u2013123 (2013)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R.J. Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. Journal of the ACM (JACM)\u00a024(3), 522\u2013526 (1977)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"6_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M. Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on slp-compressed strings: A survey. Groups Complexity Cryptology\u00a04(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"issue":"1-2","key":"6_CR6","first-page":"1","volume":"4","author":"S.V. Lokam","year":"2009","unstructured":"Lokam, S.V.: Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science\u00a04(1-2), 1\u2013155 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1145\/321752.321761","volume":"20","author":"J. Morgenstern","year":"1973","unstructured":"Morgenstern, J.: Note on a lower bound on the linear complexity of the fast fourier transform. Journal of the ACM (JACM)\u00a020(2), 305\u2013306 (1973)","journal-title":"Journal of the ACM (JACM)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: STOC, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01215351","volume":"14","author":"P. Pudlak","year":"1994","unstructured":"Pudlak, P.: Large communication in constant depth circuits. Combinatorica\u00a014(2), 203\u2013216 (1994)","journal-title":"Combinatorica"},{"issue":"4","key":"6_CR10","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01270384","volume":"6","author":"V. Shoup","year":"1996","unstructured":"Shoup, V., Smolensky, R.: Lower bounds for polynomial evaluation and interpolation problems. Computational Complexity\u00a06(4), 301\u2013311 (1996)","journal-title":"Computational Complexity"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Mathematical Foundations of Computer Science 1977","author":"L.G. Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol.\u00a053, pp. 162\u2013176. Springer, Heidelberg (1977)"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T19:57:20Z","timestamp":1558900640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}