[{"file":[{"file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","creator":"dernst","file_size":1056278,"date_updated":"2020-07-14T12:47:40Z","access_level":"open_access","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","content_type":"application/pdf","relation":"main_file","file_id":"6775","date_created":"2019-08-08T06:55:21Z"}],"date_published":"2018-12-01T00:00:00Z","_id":"6774","abstract":[{"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(𝑋) .","lang":"eng"}],"issue":"3-4","file_date_updated":"2020-07-14T12:47:40Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"volume":2,"publication_status":"published","oa":1,"article_type":"original","has_accepted_license":"1","oa_version":"Published Version","year":"2018","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-07T13:10:36Z","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"month":"12","date_created":"2019-08-08T06:47:40Z","page":"177-231","publication":"Journal of Applied and Computational Topology","quality_controlled":"1","department":[{"_id":"UlWa"}],"status":"public","intvolume":"         2","publisher":"Springer","day":"01","type":"journal_article","author":[{"first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8878-8397","full_name":"Franek, Peter","first_name":"Peter","last_name":"Franek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y","first_name":"Stephan Y","last_name":"Zhechev"}],"citation":{"short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","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>","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.","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.","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>."},"title":"Computing simplicial representatives of homotopy group elements","language":[{"iso":"eng"}],"ddc":["514"],"doi":"10.1007/s41468-018-0021-5","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"6681"}]},"project":[{"_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M01980","name":"Robust invariants of Nonlinear Systems"},{"name":"FWF Open Access Fund","call_identifier":"FWF","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1"}]},{"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). ","project":[{"name":"Robust invariants of Nonlinear Systems","grant_number":"M01980","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1510"}]},"language":[{"iso":"eng"}],"doi":"10.1007/s00454-016-9794-2","ddc":["510"],"ec_funded":1,"citation":{"short":"P. Franek, M. Krcál, Discrete &#38; Computational Geometry 56 (2016) 126–164.","ama":"Franek P, Krcál M. On computability and triviality of well groups. <i>Discrete &#38; Computational Geometry</i>. 2016;56(1):126-164. doi:<a href=\"https://doi.org/10.1007/s00454-016-9794-2\">10.1007/s00454-016-9794-2</a>","apa":"Franek, P., &#38; Krcál, M. (2016). On computability and triviality of well groups. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-016-9794-2\">https://doi.org/10.1007/s00454-016-9794-2</a>","chicago":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00454-016-9794-2\">https://doi.org/10.1007/s00454-016-9794-2</a>.","ieee":"P. Franek and M. Krcál, “On computability and triviality of well groups,” <i>Discrete &#38; Computational Geometry</i>, vol. 56, no. 1. Springer, pp. 126–164, 2016.","ista":"Franek P, Krcál M. 2016. On computability and triviality of well groups. Discrete &#38; Computational Geometry. 56(1), 126–164.","mla":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups.” <i>Discrete &#38; Computational Geometry</i>, vol. 56, no. 1, Springer, 2016, pp. 126–64, doi:<a href=\"https://doi.org/10.1007/s00454-016-9794-2\">10.1007/s00454-016-9794-2</a>."},"title":"On computability and triviality of well groups","day":"01","type":"journal_article","author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","first_name":"Peter","full_name":"Franek, Peter","last_name":"Franek"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Krcál, Marek","last_name":"Krcál"}],"publisher":"Springer","quality_controlled":"1","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publication":"Discrete & Computational Geometry","intvolume":"        56","status":"public","page":"126 - 164","month":"07","date_created":"2018-12-11T11:51:51Z","date_updated":"2023-02-23T10:02:11Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publist_id":"5799","year":"2016","oa_version":"Published Version","has_accepted_license":"1","publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:44:53Z","volume":56,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"pubrep_id":"614","issue":"1","article_processing_charge":"Yes (via OA deal)","file":[{"creator":"system","file_size":905303,"file_name":"IST-2016-614-v1+1_s00454-016-9794-2.pdf","checksum":"e0da023abf6b72abd8c6a8c76740d53c","access_level":"open_access","date_updated":"2020-07-14T12:44:53Z","relation":"main_file","file_id":"4846","content_type":"application/pdf","date_created":"2018-12-12T10:10:55Z"}],"abstract":[{"lang":"eng","text":"The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status."}],"_id":"1408","date_published":"2016-07-01T00:00:00Z"}]