{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:20:38Z","timestamp":1775794838050,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540626169","type":"print"},{"value":"9783540683421","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023480","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:06:33Z","timestamp":1132383993000},"page":"451-462","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The computational complexity of some problems of linear algebra"],"prefix":"10.1007","author":[{"given":"Jonathan F.","family":"Buss","sequence":"first","affiliation":[]},{"given":"Gudmund S.","family":"Frandsen","sequence":"additional","affiliation":[]},{"given":"Jeffrey O.","family":"Shallit","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs and non-approximability \u2014 towards tight results (3rd revision). Report Series 1995, Revision 02 of ECCC TR95-024, Electronic Colloqium on Computational Complexity, http:\/\/www.eccc.uni-trier.de\/eccc\/, December 1995. Earlier results appeared in Proc. 36th Ann. Symp. Found. Comput. Sci. (1995), 422\u2013431.","DOI":"10.1109\/SFCS.1995.492573"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"J. Canny. Some algebraic and geometric computations in PSPACE. In Proc. Twentieth ACM Symp. Theor. Comput, pp. 460\u2013467, 1988.","DOI":"10.1145\/62212.62257"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"L. Egidi. The complexity of the theory of p-adic numbers. In Proc. 34th Ann. Symp. Found. Comput. Sci., pp. 412\u2013421, 1993.","DOI":"10.1109\/SFCS.1993.366846"},{"key":"37_CR4","unstructured":"H. B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972."},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01303207","volume":"13","author":"J. Friedman","year":"1993","unstructured":"J. Friedman. A note on matrix rigidity. Combinatorica 13 (1993), 235\u2013239.","journal-title":"Combinatorica"},{"key":"37_CR6","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1051\/ita\/1984180302411","volume":"18","author":"C. Hespel","year":"1984","unstructured":"C. Hespel. Approximation de s\u00e9ries formelles par des s\u00e9ries rationnelles. RAIRO Inform. Th\u00e9or. 18 (1984), 241\u2013258.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"D. Ierardi. Quantifier elimination in the theory of an algebraically-closed field. In Proc. Twenty-first Ann. ACM Symp. Theor. Comput., pp. 138\u2013147, 1989.","DOI":"10.1145\/73007.73020"},{"key":"37_CR8","unstructured":"S. Lang. Algebra. Addison-Wesley, 1971."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"S. V. Lokam. Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity. In Proc. 36th Ann. Symp. Found. Comput. Sci., pp. 6\u201316, 1995.","DOI":"10.1109\/SFCS.1995.492457"},{"key":"37_CR10","unstructured":"Y. V. Matiyasevich. Hilbert's Tenth Problem. The MIT Press, 1993."},{"key":"37_CR11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. part I: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. J. Symbolic Comput. 13 (1992), 255\u2013299.","journal-title":"J. Symbolic Comput."},{"key":"37_CR12","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach. 27 (1980), 701\u2013717.","journal-title":"J. Assoc. Comput. Mach."},{"key":"37_CR13","unstructured":"J. O. Shallit. On approximation by rational series in noncommuting variables. Unpublished manuscript, in preparation, 1996."},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"L. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Mathematical Foundations of Computer Science, Vol. 197 of Lecture Notes in Computer Science, pp. 162\u2013176. Springer-Verlag, 1977.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. Completeness classes in algebra. In Proc. Eleventh Ann. ACM Symp. Theor. Comput., pp. 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T18:56:14Z","timestamp":1736103374000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023480"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0023480","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"10 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}