{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T18:05:40Z","timestamp":1759514740718},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1007\/bf01270384","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:42:18Z","timestamp":1111639338000},"page":"301-311","source":"Crossref","is-referenced-by-count":11,"title":["Lower bounds for polynomial evaluation and interpolation problems"],"prefix":"10.1007","volume":"6","author":[{"given":"Victor","family":"Shoup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Smolensky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading MA, 1974."},{"key":"CR2","volume-title":"The Computational Complexity of algebraic and numeric Problems","author":"A. Borodin","year":"1975","unstructured":"A. Borodin andI. Munro,The Computational Complexity of algebraic and numeric Problems. American Elsevier, New York NY, 1975."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"J. F. Canny, E. Kaltofen, and L. Yagati, Solving systems of non-linear polynomial equations faster. InProc. International Symposium on Symbolic and Algebraic Computation, 1989, 121?128.","DOI":"10.1145\/74540.74556"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"J. Friedman","year":"1993","unstructured":"J. Friedman, Note on matrix rigidity.Combinatorica 13 (1993), 235?239.","journal-title":"Combinatorica"},{"issue":"2","key":"CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/321752.321761","volume":"20","author":"J. Morgenstern","year":"1973","unstructured":"J. Morgenstern, Note on a lower bound of the linear complexity of the Fast Fourier Transform.JACM 20(2) (1973), 305?306.","journal-title":"JACM"},{"key":"CR6","unstructured":"A. A. Razborov, On rigid matrices. Preprint, 1991."},{"key":"CR7","first-page":"182","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen, Vermeidung von Divisionen.J. reine u. angew. Math. 264 (1973a), 182?202.","journal-title":"J. reine u. angew. Math."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01436566","volume":"20","author":"V. Strassen","year":"1973","unstructured":"V. Strassen, Die Berechnungskomplexit\u00e4t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten.Numer. Math. 20 (1973b), 238?251.","journal-title":"Numer. Math."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, Graph-theoretic arguments in low-level complexity. InMFCS 1977, Springer-Verlag LNCS, 1977, 162?176.","DOI":"10.1007\/3-540-08353-7_135"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270384.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01270384\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:56:09Z","timestamp":1586177769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01270384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF01270384"],"URL":"https:\/\/doi.org\/10.1007\/bf01270384","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}