{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T16:11:05Z","timestamp":1770221465748,"version":"3.49.0"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"Independent Research Fund Denmark","award":["1054-00032B"],"award-info":[{"award-number":["1054-00032B"]}]},{"DOI":"10.13039\/100008398","name":"VILLUM Foundation","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["016.Veni.192.250"],"award-info":[{"award-number":["016.Veni.192.250"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"<jats:p>\n            We show that the decision problem of determining whether a given (abstract simplicial)\n            <jats:italic>k<\/jats:italic>\n            -complex has a geometric embedding in \u211d\n            <jats:sup>d<\/jats:sup>\n            is complete for the Existential Theory of the Reals for all\n            <jats:italic>d<\/jats:italic>\n            \u2265 3 and\n            <jats:italic>k<\/jats:italic>\n            \u2208 {\n            <jats:italic>d<\/jats:italic>\n            -1,\n            <jats:italic>d<\/jats:italic>\n            } by reducing from pseudoline stretchability. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matou\u0161ek, Sedgwick, Tancer, and Wagner, J.\u00a0ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J.\u00a0ACM 2020] and establishes connections to computational topology.\n          <\/jats:p>","DOI":"10.1145\/3707201","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T10:26:03Z","timestamp":1733826363000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Geometric Embeddability of Complexes is \u2203\u211d-complete"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2734-4690","authenticated-orcid":false,"given":"Mikkel","family":"Abrahamsen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Copenhagen, K\u00f8benhavn, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Universit\u00e4t Potsdam, Potsdam, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4563-2864","authenticated-orcid":false,"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Computer Science, Utrecht University, Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2016.3"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00045"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188868"},{"key":"e_1_3_2_5_2","first-page":"18293","volume-title":"Conference on Neural Information Processing Systems (NeurIPS\u201921)","volume":"34","author":"Abrahamsen Mikkel","year":"2021","unstructured":"Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. 2021. Training neural networks is \\(\\exists \\mathbb {R}\\) -complete. In Conference on Neural Information Processing Systems (NeurIPS\u201921), Vol. 34. 18293\u201318306. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2021\/file\/9813b270ed0288e7c0388f0fd4ec68f5-Paper.pdf"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00098"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.07.035"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2016.17"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970092"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010027"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1983-0715878-1"},{"key":"e_1_3_2_12_2","unstructured":"Ulrich Brehm and Karanbir S. Sarkaria. 1992. Linear vs. Piecewise-Linear Embeddability of Simplicial Complexes. 14 pages. Technical Report MPI Bonn available at https:\/\/archive.mpim-bonn.mpg.de\/id\/eprint\/1946\/1\/preprint_1992_52.pdf"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1972-0307245-7"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2597629"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9551-8"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/120899029"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9855-6"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2852040.2852053"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9831-1"},{"key":"e_1_3_2_21_2","unstructured":"Johannes Carmesin. 2019. Embedding Simply Connected 2-complexes in 3-space \u2013 I. A Kuratowski-type Characterisation. arXiv:1709.04642. Retrieved from https:\/\/arxiv.org\/abs\/1709.04642"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4907-4"},{"key":"e_1_3_2_23_2","unstructured":"Michael Gene Dobbins Andreas Holmsen and Tillmann Miltzow. 2019. A Universality Theorem for Nested Polytopes. arXiv:1908.02213. Retrieved from https:\/\/arxiv.org\/abs\/1908.02213"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00099"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"issue":"229","key":"e_1_3_2_26_2","first-page":"2","article-title":"On straight-line representation of planar graphs","volume":"11","author":"F\u00e1ry Istv\u00e1n","year":"1948","unstructured":"Istv\u00e1n F\u00e1ry. 1948. On straight-line representation of planar graphs. Acta Scientiarum Mathematicarum 11, 229\u2013233 (1948), 2. Retrieved from http:\/\/acta.bibl.u-szeged.hu\/13574\/1\/math_011_fasc_004_229-233.pdf","journal-title":"Acta Scientiarum Mathematicarum"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.47"},{"key":"e_1_3_2_28_2","first-page":"4","volume-title":"Ergeb. Math. Kolloq","author":"Flores Antonio","year":"1933","unstructured":"Antonio Flores. 1933. \u00dcber n-dimensionale Komplexe, die im \\(\\textrm {R}_{2n+1}\\) absolut selbstverschlungen sind. In Ergeb. Math. Kolloq, Vol. 34. 4\u20136."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.1994.v1.n2.a4"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-023-00644-4"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3175494"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322156"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5169\/seals-33795"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1970-12601-5"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589233"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_37_2","first-page":"303","volume-title":"Recent Advances in Graph Theory: Proceedings of the Symposium Held in Prague","author":"Imrich Wilfried","year":"1975","unstructured":"Wilfried Imrich. 1975. On Whitney\u2019s theorem on the unique embeddability of 3-connected planar graphs. In Recent Advances in Graph Theory: Proceedings of the Symposium Held in Prague. 303\u2013306."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-013-9159-7"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_28"},{"key":"e_1_3_2_40_2","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 2014. Intersection Graphs of Segments and \\(\\exists \\mathbb {R}\\) . arXiv:1406.2636. Retrieved from https:\/\/arxiv.org\/abs\/1406.2636"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582137"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/252"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.004"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-16056-4"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3396593"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00081"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082792"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004549910019"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00048"},{"key":"e_1_3_2_50_2","first-page":"1","article-title":"A new proof of the invariance of the homology groups of a complex","volume":"22","author":"Papakyriakopoulos Christos","year":"1943","unstructured":"Christos Papakyriakopoulos. 1943. A new proof of the invariance of the homology groups of a complex. Bulletin of the Greek Mathematical Society 22 (1943), 1\u2013154.","journal-title":"Bulletin of the Greek Mathematical Society"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.topol.2023.108409"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0093761"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00604-X"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"e_1_3_2_55_2","unstructured":"Marcus Schaefer Jean Cardinal and Tillmann Miltzow. 2024. The Existential Theory of the Reals as a Complexity Class: A Compendium. arXiv:2407.18006. Retrieved from https:\/\/arxiv.org\/abs\/2407.18006"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781315119601"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969998"},{"key":"e_1_3_2_58_2","unstructured":"Yaroslav Shitov. 2016. A Universality Theorem for Nonnegative Matrix Factorizations. arXiv:1606.09068. Retrieved from https:\/\/arxiv.org\/abs\/1606.09068"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1090\/DIMACS\/004\/41"},{"key":"e_1_3_2_60_2","unstructured":"Arkadiy Skopenkov. 2014. Realizability of Hypergraphs and Ramsey Link Theory. arXiv:1402.0658. Retrieved from https:\/\/arxiv.org\/abs\/1402.0658"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00454-0"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s40598-019-00128-5"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0013-1"},{"key":"e_1_3_2_64_2","unstructured":"Mikhail Skopenkov. 2016. Embedding Products of Graphs into Euclidean Spaces. arXiv:0808.1199. Retrieved from https:\/\/arxiv.org\/abs\/0808.1199"},{"key":"e_1_3_2_65_2","first-page":"1","volume-title":"Encyclop\u00e4die der Mathematischen Wissenschaften","author":"Steinitz Ernst","year":"1922","unstructured":"Ernst Steinitz. 1922. Polyeder und Raumeinteilungen. In Encyclop\u00e4die der Mathematischen Wissenschaften. Vol. 3-1-2 (Geometrie). B. G. Teubner, Leipzig, Chapter 12, 1\u2013139."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-8621-4_11"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.17169\/refubium-14465"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.2307\/1997741"},{"key":"e_1_3_2_69_2","first-page":"72","volume-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg","author":"Kampen Egbert R. Van","year":"1933","unstructured":"Egbert R. Van Kampen. 1933. Komplexe in euklidischen R\u00e4umen. In Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg, Vol. 9. Springer, 72\u201378."},{"key":"e_1_3_2_70_2","unstructured":"Wikipedia. 1887. Jordan Curve Theorem. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Jordan_curve_theorem accessed 18-10-2021."},{"key":"e_1_3_2_71_2","volume-title":"A Theory of Imbedding, Immersion, and Isotopy of Polytopes in a Euclidean Space","author":"Wu Wen-ts\u00fcn","year":"1965","unstructured":"Wen-ts\u00fcn Wu. 1965. A Theory of Imbedding, Immersion, and Isotopy of Polytopes in a Euclidean Space. Science Press."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707201","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3707201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:14Z","timestamp":1750295894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3707201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3707201"],"URL":"https:\/\/doi.org\/10.1145\/3707201","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"2023-03-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}