[{"month":"01","department":[{"_id":"UlWa"}],"language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>.","apa":"Filakovský, M., Wagner, U., &#38; Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>","ista":"Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:767–85. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>.","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785.","ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:767-785. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>"},"title":"Embeddability of simplicial complexes is undecidable","oa_version":"Published Version","day":"01","scopus_import":1,"author":[{"first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek"},{"last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568"},{"full_name":"Zhechev, Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev","first_name":"Stephan Y"}],"date_created":"2020-05-10T22:00:48Z","volume":"2020-January","abstract":[{"lang":"eng","text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4."}],"publication_status":"published","publication_identifier":{"isbn":["9781611975994"]},"year":"2020","status":"public","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"conference":{"location":"Salt Lake City, UT, United States","name":"SODA: Symposium on Discrete Algorithms","start_date":"2020-01-05","end_date":"2020-01-08"},"date_published":"2020-01-01T00:00:00Z","publisher":"SIAM","article_processing_charge":"No","doi":"10.1137/1.9781611975994.47","type":"conference","_id":"7806","date_updated":"2021-01-12T08:15:38Z","page":"767-785","quality_controlled":"1","main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.47","open_access":"1"}]},{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019.","ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","ama":"Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6681\">10.15479/AT:ISTA:6681</a>","mla":"Zhechev, Stephan Y. <i>Algorithmic Aspects of Homotopy Theory and Embeddability</i>. Institute of Science and Technology Austria, 2019, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:6681\">10.15479/AT:ISTA:6681</a>.","apa":"Zhechev, S. Y. (2019). <i>Algorithmic aspects of homotopy theory and embeddability</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:6681\">https://doi.org/10.15479/AT:ISTA:6681</a>","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.","chicago":"Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. <a href=\"https://doi.org/10.15479/AT:ISTA:6681\">https://doi.org/10.15479/AT:ISTA:6681</a>."},"language":[{"iso":"eng"}],"oa":1,"file":[{"file_size":1464227,"date_created":"2019-08-07T13:02:50Z","date_updated":"2020-07-14T12:47:37Z","creator":"szhechev","file_id":"6771","file_name":"Stephan_Zhechev_thesis.pdf","access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"3231e7cbfca3b5687366f84f0a57a0c0"},{"file_id":"6772","file_size":303988,"date_created":"2019-08-07T13:03:22Z","date_updated":"2020-07-14T12:47:37Z","creator":"szhechev","relation":"source_file","checksum":"85d65eb27b4377a9e332ee37a70f08b6","file_name":"Stephan_Zhechev_thesis.tex","access_level":"closed","content_type":"application/octet-stream"},{"file_id":"6773","date_created":"2019-08-07T13:03:34Z","file_size":1087004,"date_updated":"2020-07-14T12:47:37Z","creator":"szhechev","relation":"supplementary_material","checksum":"86b374d264ca2dd53e712728e253ee75","file_name":"supplementary_material.zip","access_level":"closed","content_type":"application/zip"}],"department":[{"_id":"UlWa"}],"month":"08","supervisor":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"file_date_updated":"2020-07-14T12:47:37Z","publication_identifier":{"issn":["2663-337X"]},"publication_status":"published","abstract":[{"lang":"eng","text":"The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"has_accepted_license":"1","date_created":"2019-07-26T11:14:34Z","title":"Algorithmic aspects of homotopy theory and embeddability","oa_version":"Published Version","day":"08","author":[{"first_name":"Stephan Y","full_name":"Zhechev, Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev"}],"date_published":"2019-08-08T00:00:00Z","status":"public","degree_awarded":"PhD","related_material":{"record":[{"id":"6774","relation":"part_of_dissertation","status":"public"}]},"year":"2019","ddc":["514"],"page":"104","type":"dissertation","_id":"6681","date_updated":"2023-09-07T13:10:36Z","publisher":"Institute of Science and Technology Austria","article_processing_charge":"No","alternative_title":["ISTA Thesis"],"doi":"10.15479/AT:ISTA:6681"},{"file_date_updated":"2020-07-14T12:47:40Z","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"publication_status":"published","abstract":[{"lang":"eng","text":"A central problem of algebraic topology is to understand the homotopy groups  𝜋𝑑(𝑋)  of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group  𝜋1(𝑋)  of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with   𝜋1(𝑋)  trivial), compute the higher homotopy group   𝜋𝑑(𝑋)  for any given   𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of   𝜋𝑑(𝑋) ,   𝑑≥2  as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of   𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere   𝑆𝑑  to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes   𝜋𝑑(𝑋)  and represents its elements as simplicial maps from a suitable triangulation of the d-sphere   𝑆𝑑  to X. For fixed d, the algorithm runs in time exponential in   size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed   𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of   𝜋𝑑(𝑋) , the size of the triangulation of   𝑆𝑑  on which the map is defined, is exponential in size(𝑋) ."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"intvolume":"         2","has_accepted_license":"1","date_created":"2019-08-08T06:47:40Z","article_type":"original","volume":2,"oa_version":"Published Version","title":"Computing simplicial representatives of homotopy group elements","day":"01","author":[{"first_name":"Marek","last_name":"Filakovský","full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-8878-8397","first_name":"Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87","full_name":"Franek, Peter","last_name":"Franek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"},{"first_name":"Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4), 177–231.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>.","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>.","apa":"Filakovský, M., Franek, P., Wagner, U., &#38; Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. Springer. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>","ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. 2018;2(3-4):177-231. doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4. Springer, pp. 177–231, 2018."},"issue":"3-4","language":[{"iso":"eng"}],"oa":1,"file":[{"file_id":"6775","file_size":1056278,"date_created":"2019-08-08T06:55:21Z","date_updated":"2020-07-14T12:47:40Z","creator":"dernst","relation":"main_file","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","access_level":"open_access","content_type":"application/pdf"}],"department":[{"_id":"UlWa"}],"month":"12","quality_controlled":"1","ddc":["514"],"page":"177-231","type":"journal_article","_id":"6774","date_updated":"2023-09-07T13:10:36Z","publisher":"Springer","doi":"10.1007/s41468-018-0021-5","date_published":"2018-12-01T00:00:00Z","publication":"Journal of Applied and Computational Topology","status":"public","project":[{"_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","grant_number":"M01980","name":"Robust invariants of Nonlinear Systems","call_identifier":"FWF"},{"_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1","call_identifier":"FWF","name":"FWF Open Access Fund"}],"related_material":{"record":[{"id":"6681","relation":"dissertation_contains","status":"public"}]},"year":"2018"}]