{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:26Z","timestamp":1725664466222},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_113","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:42:45Z","timestamp":1330274565000},"page":"48-59","source":"Crossref","is-referenced-by-count":3,"title":["Non-commutative computation, depth reduction, and skew circuits (extended abstract)"],"prefix":"10.1007","author":[{"given":"Meena","family":"Mahajan","sequence":"first","affiliation":[]},{"given":"V","family":"Vinay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"volume-title":"A note on log space optimization. Technical report","year":"1992","author":"C. \u00c1lvarez","key":"5_CR1","unstructured":"C. \u00c1lvarez and B. Jenner. A note on log space optimization. Technical report, Universitat Polit\u00e8cnica Catalunya, Barcelona, 1992."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender and J. Jiao. Depth reduction for noncommutative arithmetic circuits. In Proceedings of the Symposium on Theory of Computing (STOC), 1993.","DOI":"10.1145\/167088.167226"},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. \u00c1lvarez","year":"1993","unstructured":"C. \u00c1lvarez and B. Jenner. A very hard log-space counting class. Theoretical Computer Science, 107: 3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"S. Kosaraju. On the parallel evaluation of classes of circuits. In Proceedings of the 10th FST&TCS Conference, pages 232\u2013237, December 1990. LNCS 472.","DOI":"10.1007\/3-540-53487-3_48"},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1137\/0217044","volume":"17","author":"G. Miller","year":"1988","unstructured":"G. Miller, V. Ramachandran, and E. Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM Journal on Computing, 17: 687\u2013695, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"M. Mahajan and V Vinay. Non-commutative computation, depth reduction, and skew circuits. Technical Report IMSc-94\/09, The Institute of Mathematical Sciences, Madras, India, March 1994. Available in ftp\/pub\/tcs\/trimsc at imsc.ernet.in.","DOI":"10.1007\/3-540-58715-2_113"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"N. Nisan. Lower bounds for noncommutative computation. In Proceedings of the Symposium on Theory of Computing (STOC), 1991.","DOI":"10.1145\/103418.103462"},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"42","author":"H. Venkateswaran","year":"1991","unstructured":"H. Venkateswaran. Properties that characterise LOGCFL. Journal of Computer and System Sciences, 42: 380\u2013404, 1991. also in Proceedings of 19th STOC 1987, pp 141\u2013150.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR9","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/0221040","volume":"21","author":"H. Venkateswaran","year":"1992","unstructured":"H. Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM Journal on Computing, 21: 655\u2013670, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR10","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-bounded arithmetic circuits. In Proceedings of the 6th Annual Conference on Structure in Complexity Theory, pages 270\u2013284, 1991."},{"key":"5_CR11","series-title":"PhD thesis","volume-title":"Semi-unboundedness and complexity classes","author":"V. Vinay","year":"1991","unstructured":"V. Vinay. Semi-unboundedness and complexity classes. PhD thesis, Indian Institute of Science, Bangalore, India, 1991."},{"key":"5_CR12","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L. Valiant","year":"1983","unstructured":"L. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12: 641\u2013644, 1983.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_113.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:23:40Z","timestamp":1605648220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_113","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}