[{"publisher":"Association for Computing Machinery","day":"15","article_processing_charge":"Yes (in subscription journal)","has_accepted_license":"1","department":[{"_id":"UlWa"}],"OA_type":"hybrid","year":"2025","language":[{"iso":"eng"}],"license":"https://creativecommons.org/licenses/by/4.0/","page":"72-83","oa":1,"month":"06","ddc":["000"],"_id":"20008","file_date_updated":"2025-07-14T06:42:58Z","status":"public","oa_version":"Published Version","doi":"10.1145/3717823.3718154","scopus_import":"1","author":[{"first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"full_name":"Opršal, Jakub","last_name":"Opršal","orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"date_created":"2025-07-13T22:01:23Z","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20339"}]},"file":[{"access_level":"open_access","creator":"dernst","date_updated":"2025-07-14T06:42:58Z","success":1,"date_created":"2025-07-14T06:42:58Z","file_name":"2025_STOC_Avvakumov.pdf","checksum":"2c9ae7ad0102c41124976f4cb5182760","content_type":"application/pdf","relation":"main_file","file_id":"20013","file_size":940827}],"OA_place":"publisher","type":"conference","acknowledgement":"This research was supported by the Austrian Science Fund (FWF project P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed by the Ministry of Education, Youth and Sports of the Czech Republic. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.","conference":{"end_date":"2025-06-27","start_date":"2025-06-23","location":"Prague, Czechia","name":"STOC: Symposium on Theory of Computing"},"citation":{"apa":"Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>","chicago":"Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>.","short":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83.","ieee":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.","ama":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>","ista":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.","mla":"Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 72–83, doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","corr_author":"1","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"ec_funded":1,"publication_status":"published","project":[{"call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413"}],"title":"Hardness of 4-colouring G-colourable graphs","date_updated":"2026-04-07T12:36:50Z","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","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_published":"2025-06-15T00:00:00Z","abstract":[{"text":"We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.","lang":"eng"}],"quality_controlled":"1"},{"oa":1,"month":"03","_id":"15168","file_date_updated":"2024-03-25T07:44:30Z","ddc":["510"],"oa_version":"Published Version","status":"public","article_number":"34","doi":"10.4230/LIPIcs.STACS.2024.34","scopus_import":"1","intvolume":"       289","author":[{"first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"last_name":"Nakajima","full_name":"Nakajima, Tamio Vesa","first_name":"Tamio Vesa"},{"orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub","last_name":"Opršal","first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","last_name":"Tasinato","full_name":"Tasinato, Gianluca"},{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"volume":289,"related_material":{"record":[{"id":"20339","relation":"dissertation_contains","status":"public"}]},"date_created":"2024-03-24T23:00:59Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"01","article_processing_charge":"No","has_accepted_license":"1","department":[{"_id":"UlWa"}],"year":"2024","language":[{"iso":"eng"}],"corr_author":"1","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"arxiv":1,"ec_funded":1,"project":[{"grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020"}],"publication_status":"published","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","date_updated":"2026-04-07T12:36:50Z","date_published":"2024-03-01T00:00:00Z","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","short":"CC BY (4.0)","image":"/images/cc_by.png"},"isi":1,"external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"abstract":[{"text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).","lang":"eng"}],"quality_controlled":"1","file":[{"checksum":"0524d4189fd1ed08989546511343edf3","relation":"main_file","content_type":"application/pdf","file_size":927290,"file_id":"15175","creator":"dernst","access_level":"open_access","date_updated":"2024-03-25T07:44:30Z","success":1,"file_name":"2024_LIPICs_Filakovsky.pdf","date_created":"2024-03-25T07:44:30Z"}],"alternative_title":["LIPIcs"],"acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","type":"conference","conference":{"end_date":"2024-03-14","start_date":"2024-03-12","location":"Clermont-Ferrand, France","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"citation":{"ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>","chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"41st International Symposium on Theoretical Aspects of Computer Science"},{"doi":"10.1137/1.9781611975994.47","scopus_import":1,"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"},{"first_name":"Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.47","open_access":"1"}],"volume":"2020-January","date_created":"2020-05-10T22:00:48Z","oa":1,"month":"01","_id":"7806","oa_version":"Published Version","status":"public","year":"2020","language":[{"iso":"eng"}],"page":"767-785","publisher":"SIAM","day":"01","article_processing_charge":"No","department":[{"_id":"UlWa"}],"publication_status":"published","project":[{"grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"title":"Embeddability of simplicial complexes is undecidable","date_updated":"2021-01-12T08:15:38Z","date_published":"2020-01-01T00:00:00Z","quality_controlled":"1","abstract":[{"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.","lang":"eng"}],"publication_identifier":{"isbn":["9781611975994"]},"citation":{"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>.","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>","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>","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.","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>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","type":"conference","conference":{"end_date":"2020-01-08","start_date":"2020-01-05","location":"Salt Lake City, UT, United States","name":"SODA: Symposium on Discrete Algorithms"}},{"main_file_link":[{"url":"https://arxiv.org/abs/1312.2337","open_access":"1"}],"author":[{"full_name":"Filakovský, Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"},{"full_name":"Vokřínek, Lukas","last_name":"Vokřínek","first_name":"Lukas"}],"date_created":"2019-06-16T21:59:14Z","volume":20,"scopus_import":"1","doi":"10.1007/s10208-019-09419-x","intvolume":"        20","status":"public","oa_version":"Preprint","_id":"6563","oa":1,"month":"04","page":"311-330","language":[{"iso":"eng"}],"year":"2020","article_processing_charge":"No","department":[{"_id":"UlWa"}],"article_type":"original","publisher":"Springer Nature","day":"01","abstract":[{"lang":"eng","text":"This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋."}],"quality_controlled":"1","date_updated":"2025-07-10T11:53:32Z","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF"}],"title":"Are two given maps homotopic? An algorithmic viewpoint","publication_status":"published","isi":1,"external_id":{"arxiv":["1312.2337"],"isi":["000522437400004"]},"date_published":"2020-04-01T00:00:00Z","arxiv":1,"publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"publication":"Foundations of Computational Mathematics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330.","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>.","apa":"Filakovský, M., &#38; Vokřínek, L. (2020). Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>","ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 311–330.","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>, vol. 20, Springer Nature, 2020, pp. 311–30, doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>.","ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. 2020;20:311-330. doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” <i>Foundations of Computational Mathematics</i>, vol. 20. Springer Nature, pp. 311–330, 2020."},"type":"journal_article"},{"status":"public","oa_version":"Published Version","ddc":["514"],"_id":"6774","file_date_updated":"2020-07-14T12:47:40Z","month":"12","oa":1,"date_created":"2019-08-08T06:47:40Z","related_material":{"record":[{"id":"6681","relation":"dissertation_contains","status":"public"}]},"volume":2,"author":[{"last_name":"Filakovský","full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"},{"first_name":"Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8878-8397","full_name":"Franek, Peter","last_name":"Franek"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"intvolume":"         2","scopus_import":"1","doi":"10.1007/s41468-018-0021-5","department":[{"_id":"UlWa"}],"has_accepted_license":"1","day":"01","issue":"3-4","article_type":"original","publisher":"Springer","page":"177-231","language":[{"iso":"eng"}],"year":"2018","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"corr_author":"1","quality_controlled":"1","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"}],"date_published":"2018-12-01T00:00:00Z","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","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_updated":"2026-04-08T13:56:01Z","project":[{"call_identifier":"FWF","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","name":"Robust Invariants of Nonlinear Systems","grant_number":"M01980"},{"call_identifier":"FWF","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1","name":"FWF Open Access Fund"}],"title":"Computing simplicial representatives of homotopy group elements","publication_status":"published","type":"journal_article","file":[{"content_type":"application/pdf","relation":"main_file","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","file_size":1056278,"file_id":"6775","date_updated":"2020-07-14T12:47:40Z","access_level":"open_access","creator":"dernst","date_created":"2019-08-08T06:55:21Z","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf"}],"publication":"Journal of Applied and Computational Topology","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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>","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>.","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.","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.","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>."}}]