{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T18:43:03Z","timestamp":1743964983768},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"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":[[1991,6]]},"DOI":"10.1007\/bf01272518","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T07:41:27Z","timestamp":1111650087000},"page":"131-155","source":"Crossref","is-referenced-by-count":3,"title":["Some computational problems in linear algebra as hard as matrix multiplication"],"prefix":"10.1007","volume":"1","author":[{"given":"Peter","family":"B\ufffdrgisser","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Lickteig","sequence":"additional","affiliation":[]}],"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, Reading MA: Addison-Wesley, 1974."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(81)90070-0","volume":"15","author":"A. Alder","year":"1981","unstructured":"A. Alder andV. Strassen,On the algorithmic complexity of associative algebras, Theor. Computer Science15 (1981), 201?211.","journal-title":"Theor. Computer Science"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1982","unstructured":"W. Baur andV. Strassen,The complexity of partial derivatives. Theor. Computer Science22 (1982), 317?330.","journal-title":"Theor. Computer Science"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, andS. Smale,On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc.21 (1989), 1?46.","journal-title":"Bull. Amer. Math. Soc."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"J. Bunch","year":"1974","unstructured":"J. Bunch andJ. Hopcroft,Triangular factorization, and inversion by fast matrix multiplication, Math. Comp.28 (1974), 231?236.","journal-title":"Math. Comp."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith andS. Winograd,Matrix multiplication via arithmetic progressions, J. Symb. Comp.9 (1990), 251?280.","journal-title":"J. Symb. Comp."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"R. Hartshorne,Algebraic Geometry, Graduate Texts in Mathematics Vol. 52, Springer Verlag, 1977.","DOI":"10.1007\/978-1-4757-3849-0"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(88)90145-4","volume":"59","author":"K. Kalorkoti","year":"1988","unstructured":"K. Kalorkoti,The trace invariant and matrix inversion. Theor. Computer Science59 (1988), 277?286.","journal-title":"Theor. Computer Science"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0304-3975(85)90049-0","volume":"36","author":"W. Keller-Gehrig","year":"1985","unstructured":"W. Keller-Gehrig,Fast algorithms for the characteristic polynomial, Theor. Computer Science36 (1985), 309?317.","journal-title":"Theor. Computer Science"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"H. Kraft,Geometric methods in representation theory, in: Representations of Algebras, Workshop Proc., Puebla, Mexico 1980, LNM944, Berlin-Heidelberg-New York 1982.","DOI":"10.1007\/BFb0094059"},{"key":"CR11","unstructured":"J. C. Lafon and S. Winograd,A lower bound for the multiplicative complexity of the product of two matrices, (unpublished) manuscript, 1978."},{"key":"CR12","unstructured":"T. Lickteig,On semialgebraic decision complexity, Tech. Rep. TR-90-052 Int. Comp. Science Inst., Berkeley, and Univ. T\u00fcbingen, Habilitationsschrift, to appear."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/BF01402563","volume":"20","author":"A. Sch\u00f6nhage","year":"1973","unstructured":"A. Sch\u00f6nhage,Unit\u00e4re Transformationen grosser Matrizen, Num. Math.20 (1973), 409?417.","journal-title":"Num. Math."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"V. Strassen,Gaussian elimination is not optimal, Numer. Mathematik13 (1969), 354?356.","journal-title":"Numer. Mathematik"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF00289512","volume":"1","author":"V. Strassen","year":"1973","unstructured":"V. Strassen,Berechnung und Programm I, Acta Informatica1 (1973), 320?335.","journal-title":"Acta Informatica"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF00571464","volume":"2","author":"V. Strassen","year":"1973","unstructured":"V. Strassen,Berechnung und Programm II, Acta Informatica2 (1973), 64?79.","journal-title":"Acta Informatica"},{"key":"CR17","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen,Vermeidung von Divisionen, Crelles Journal f\u00fcr die reine und angewandte Mathematik264 (1973), 184?202.","journal-title":"Crelles Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0212001","volume":"12\/1","author":"V. Strassen","year":"1983","unstructured":"V. Strassen,The complexity of continued fraction, SIAM J. Comp.12\/1 (1983), 1?27.","journal-title":"SIAM J. Comp."},{"key":"CR19","first-page":"406","volume":"375\/376","author":"V. Strassen","year":"1987","unstructured":"V. Strassen,Relative bilinear complexity and matrix multiplication, J. f\u00fcr die reine und angewandte Mathematik375\/376 (1987), 406?443.","journal-title":"J. f\u00fcr die reine und angewandte Mathematik"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"I. Wegener,The complexity of Boolean functions, Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272518.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01272518\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272518","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:01:29Z","timestamp":1586178089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01272518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01272518"],"URL":"https:\/\/doi.org\/10.1007\/bf01272518","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}