{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:07Z","timestamp":1725664087631},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575290"},{"type":"electronic","value":"9783540482116"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57529-4_60","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:06:08Z","timestamp":1330243568000},"page":"268-283","source":"Crossref","is-referenced-by-count":0,"title":["A lower bound for solvability of polynomial equations"],"prefix":"10.1007","author":[{"given":"Ketan","family":"Mulmuley","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon, R. Boppana, The monotone circuit complexity of boolean functions, Combinatorica, 7, (1987), pp. 1\u201322.","journal-title":"Combinatorica"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, \u03a31 1-formulae on finite structures, Ann. Pure. Appl. Logic 24 (1983), 1\u201348.","journal-title":"Ann. Pure. Appl. Logic"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees, STOC 1983.","DOI":"10.1145\/800061.808735"},{"key":"22_CR4","unstructured":"J. Canny, The complexity of robot motion planning, The MIT press, 1987."},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csanky","year":"1976","unstructured":"L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. computing, 5, 1976, pp. 618\u2013623.","journal-title":"SIAM J. computing"},{"key":"22_CR6","unstructured":"W. Fulton, Algebraic curves, The Benjamin\/Cummings Publishing Company, 1969."},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, M. Sipser, Parity, circuits, and the polynomial time hierarchy, FOCS 1981.","DOI":"10.1109\/SFCS.1981.35"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"J. Hastad, Almost optimal lower bounds for small depth circuits, STOC 1986.","DOI":"10.1145\/12130.12132"},{"key":"22_CR9","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0020-0190(80)90042-3","volume":"11","author":"O. Ibarra","year":"1980","unstructured":"O. Ibarra, S. Moran, L. Rosier, A note on parallel complexity of computing the rank of order n matrices, Info. proc. letters, vol. 11, 1980, pp. 162.","journal-title":"Info. proc. letters"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"R. Karp, V. Ramachandran, A survey of parallel algorithms for shared-memory machines, Handbook of theoretical computer science, pp. 870\u2013941, Edited by J. van Leeuwen, Elsevier Science Publishers B.V., 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J. Milnor","year":"1964","unstructured":"J. Milnor, On the betti numbers of real varieties, Proc. of American Mathematical Society 15, 1964, 275\u2013280.","journal-title":"Proc. of American Mathematical Society"},{"key":"22_CR12","unstructured":"A. Razborov, Lower bounds on the monotone complexity of some boolean functions, Dokl. Ak. Nauk. (1985), pp. 798\u2013801."},{"key":"22_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J. Steele","year":"1982","unstructured":"J. Steele and A. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3, (1982), 1\u20138.","journal-title":"J. Algorithms"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"R. Thom, Sur l'homologie des varietes algebriques reelles, Differential and combinatorial topology, edited by S. Cairns, Princeton University Press, 1965.","DOI":"10.1515\/9781400874842-016"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"A. Yao, Separating the polynomial-time hierarchy by oracles, FOCS 1985.","DOI":"10.1109\/SFCS.1985.49"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"A. Yao, Lower bounds for algebraic computation trees with integer inputs, FOCS, 1989.","DOI":"10.1109\/SFCS.1989.63495"},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (1979) 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"22_CR18","unstructured":"B.L. van der Waerden, Modern algebra, Volume II, Frederick Ungar Publishing Co., 1950."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57529-4_60.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:12:45Z","timestamp":1605629565000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57529-4_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575290","9783540482116"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57529-4_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}