{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T15:44:52Z","timestamp":1784389492548,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T00:00:00Z","timestamp":1501804800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9800-y","type":"journal-article","created":{"date-parts":[[2017,8,4]],"date-time":"2017-08-04T06:01:55Z","timestamp":1501826515000},"page":"1161-1174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["The Complexity of Tensor Rank"],"prefix":"10.1007","volume":"62","author":[{"given":"Marcus","family":"Schaefer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,4]]},"reference":[{"key":"9800_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., Burgisser, P., Kjeldgaard-Pedersen, J., Bro Miltersen, P.: On the complexity of numerical analysis. In: CCC \u201906: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pp. 331\u2013339. IEEE Computer Society, DC, USA (2006)","DOI":"10.1109\/CCC.2006.30"},{"key":"9800_CR2","doi-asserted-by":"crossref","unstructured":"Basri, R., Felzenszwalb, P.F., Girshick, R.B., Jacobs, D.W., Klivans, C.J.: Visibility constraints on features of 3D objects. In: CVPR, pp. 1231\u20131238. IEEE Computer Society (2009)","DOI":"10.1109\/CVPRW.2009.5206726"},{"key":"9800_CR3","unstructured":"Bhangale, A., Kopparty, S.: The complexity of computing the minimum rank of a sign pattern matrix. CoRR, arXiv: 1503.04486 (2015)"},{"issue":"5","key":"9800_CR4","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discret. Comput. Geom. 6(5), 443\u2013459 (1991)","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"9800_CR5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1002\/jgt.3190170308","volume":"17","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Dean, N.: Bounds for rectilinear crossing numbers. J Graph Theory 17(3), 333\u2013348 (1993)","journal-title":"J Graph Theory"},{"key":"9800_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and real computation","author":"L Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation. Springer-Verlag, New York (1998)"},{"issue":"1","key":"9800_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. (N.S.) 21(1), 1\u201346 (1989)","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"issue":"3","key":"9800_CR8","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1006\/jcss.1998.1608","volume":"58","author":"JF Buss","year":"1999","unstructured":"Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. System Sci. 58(3), 572\u2013596 (1999)","journal-title":"J. Comput. System Sci."},{"key":"9800_CR9","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in pspace. In: STOC \u201988: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 460\u2013469. ACM, NY, USA (1988)","DOI":"10.1145\/62212.62257"},{"key":"9800_CR10","doi-asserted-by":"crossref","unstructured":"Davis, M., Matijasevi\u010d, Y., Robinson, J.: Hilbert\u2019s tenth problem: Diophantine equations: positive aspects of a negative solution. In: Mathematical Developments Arising from Hilbert Problems (Proc. Sympos. Pure Math., Vol. XXVIII, Northern Illinois Univ., De Kalb, Ill., 1974), pp. 323\u2013378. (loose erratum). American Mathematics Society, Providence, RI (1976)","DOI":"10.1090\/pspum\/028.2\/0432534"},{"key":"9800_CR11","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Tensor rank is NP-complete. In: Automata, languages and programming (Stresa, 1989), volume 372 of Lecture Notes in Computer Science, pp. 451\u2013460. Springer, Berlin (1989)","DOI":"10.1007\/BFb0035776"},{"issue":"4","key":"9800_CR12","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1016\/0196-6774(90)90014-6","volume":"11","author":"J H\u00e5stad","year":"1990","unstructured":"H\u00e5stad, J.: Tensor rank is NP-complete. J. Algorithm. 11(4), 644\u2013654 (1990)","journal-title":"J. Algorithm."},{"issue":"6","key":"9800_CR13","doi-asserted-by":"crossref","first-page":"Art. 45, 39","DOI":"10.1145\/2512329","volume":"60","author":"CJ Hillar","year":"2013","unstructured":"Hillar, C.J., Lim, L.-H.: Most tensor problems are NP-hard. J. ACM 60(6), Art. 45, 39 (2013)","journal-title":"J. ACM"},{"key":"9800_CR14","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0024-3795(78)90052-6","volume":"22","author":"TD Howell","year":"1978","unstructured":"Howell, T.D.: Global properties of tensor rank. Linear Algebra Appl. 22, 9\u201323 (1978)","journal-title":"Linear Algebra Appl."},{"key":"9800_CR15","unstructured":"Koenigsmann, J.: Defining \u2124 $\\mathbb {Z}$ in \u211a $\\mathbb {Q}$ ArXiv e-prints (2010)"},{"issue":"4","key":"9800_CR16","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1006\/jcom.1996.0019","volume":"12","author":"P Koiran","year":"1996","unstructured":"Koiran, P.: Hilbert\u2019s Nullstellensatz is in the polynomial hierarchy. J. Complex. 12(4), 273\u2013286 (1996). Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997)","journal-title":"J. Complex."},{"issue":"3","key":"9800_CR17","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1137\/07070111X","volume":"51","author":"TG Kolda","year":"2009","unstructured":"Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455\u2013500 (2009)","journal-title":"SIAM Rev."},{"issue":"2","key":"9800_CR18","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62(2), 289\u2013315 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"9800_CR19","first-page":"279","volume":"191","author":"JV Matijasevi\u010d","year":"1970","unstructured":"Matijasevi\u010d, J.V.: The Diophantineness of enumerable sets. Dokl. Akad. Nauk SSSR 191, 279\u2013282 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9800_CR20","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and geometry\u2014Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"issue":"3","key":"9800_CR21","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1353\/ajm.0.0057","volume":"131","author":"B Poonen","year":"2009","unstructured":"Poonen, B.: Characterizing integers among rational numbers with a universal-existential formula. Amer. J. Math. 131(3), 675\u2013682 (2009)","journal-title":"Amer. J. Math."},{"key":"9800_CR22","unstructured":"Richter-Gebert, J.: Mn\u00ebv\u2019s universality theorem revisited. S\u00e9m Lothar. Combin., pp. 34 (1995)"},{"key":"9800_CR23","volume-title":"Realization spaces of polytopes, volume 1643 of Lecture Notes in Mathematics","author":"J Richter-Gebert","year":"1996","unstructured":"Richter-Gebert, J.: Realization spaces of polytopes, volume 1643 of Lecture Notes in Mathematics. Springer-Verlag, Berlin (1996)"},{"key":"9800_CR24","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pp. 334\u2013344. Springer (2009)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"9800_CR25","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer (2012)","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"9800_CR26","doi-asserted-by":"crossref","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Fixed points Nash equilibria, and the existential theory of the reals. Theory of Computing Systems, pp. 1\u201322 (2015)","DOI":"10.1007\/s00224-015-9662-0"},{"key":"9800_CR27","unstructured":"Shitov, Y.: How hard is the tensor rank?. CoRR, arXiv: 1611.01559 (2016)"},{"key":"9800_CR28","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied geometry and discrete mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 531\u2013554. American Mathematics Society, Providence, RI (1991)","DOI":"10.1090\/dimacs\/004\/41"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9800-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9800-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9800-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T01:01:01Z","timestamp":1569978061000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9800-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,4]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9800"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9800-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,4]]}}}