[{"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1307.6444"}],"page":"915 - 965","type":"journal_article","_id":"1073","date_updated":"2023-09-20T12:01:28Z","publisher":"Springer","article_processing_charge":"No","doi":"10.1007/s00454-016-9855-6","date_published":"2017-06-01T00:00:00Z","status":"public","publication":"Discrete & Computational Geometry","publist_id":"6309","external_id":{"isi":["000400072700008"]},"year":"2017","isi":1,"publication_status":"published","publication_identifier":{"issn":["01795376"]},"intvolume":"        54","abstract":[{"lang":"eng","text":"Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation."}],"date_created":"2018-12-11T11:50:00Z","volume":54,"oa_version":"Submitted Version","title":"Algorithmic solvability of the lifting extension problem","day":"01","scopus_import":"1","author":[{"last_name":"Čadek","full_name":"Čadek, Martin","first_name":"Martin"},{"last_name":"Krcál","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"},{"last_name":"Vokřínek","full_name":"Vokřínek, Lukáš","first_name":"Lukáš"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ieee":"M. Čadek, M. Krcál, and L. Vokřínek, “Algorithmic solvability of the lifting extension problem,” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4. Springer, pp. 915–965, 2017.","short":"M. Čadek, M. Krcál, L. Vokřínek, Discrete &#38; Computational Geometry 54 (2017) 915–965.","ama":"Čadek M, Krcál M, Vokřínek L. Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. 2017;54(4):915-965. doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>","apa":"Čadek, M., Krcál, M., &#38; Vokřínek, L. (2017). Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>","mla":"Čadek, Martin, et al. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4, Springer, 2017, pp. 915–65, doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>.","chicago":"Čadek, Martin, Marek Krcál, and Lukáš Vokřínek. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>.","ista":"Čadek M, Krcál M, Vokřínek L. 2017. Algorithmic solvability of the lifting extension problem. Discrete &#38; Computational Geometry. 54(4), 915–965."},"issue":"4","language":[{"iso":"eng"}],"oa":1,"department":[{"_id":"UlWa"}],"month":"06"},{"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"P. Franek and M. Krcál, “Persistence of zero sets,” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2. International Press, pp. 313–342, 2017.","short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.","ama":"Franek P, Krcál M. Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. 2017;19(2):313-342. doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>","apa":"Franek, P., &#38; Krcál, M. (2017). Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. International Press. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>","mla":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>.","chicago":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>. International Press, 2017. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>.","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342."},"issue":"2","language":[{"iso":"eng"}],"oa":1,"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"01","publication_status":"published","publication_identifier":{"issn":["15320073"]},"intvolume":"        19","abstract":[{"text":"We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z&lt; r(f) := (g-1(0): ||g - f|| &lt; r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z&lt; r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r &gt; 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C).","lang":"eng"}],"date_created":"2018-12-11T11:47:14Z","volume":19,"oa_version":"Submitted Version","title":"Persistence of zero sets","scopus_import":1,"day":"01","author":[{"full_name":"Franek, Peter","id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek","first_name":"Peter"},{"last_name":"Krcál","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"}],"date_published":"2017-01-01T00:00:00Z","ec_funded":1,"publication":"Homology, Homotopy and Applications","status":"public","project":[{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","grant_number":"701309","_id":"2590DB08-B435-11E9-9278-68D0E5697425"}],"publist_id":"7246","year":"2017","quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1507.04310","open_access":"1"}],"page":"313 - 342","type":"journal_article","_id":"568","date_updated":"2021-01-12T08:03:12Z","publisher":"International Press","doi":"10.4310/HHA.2017.v19.n2.a16"},{"type":"journal_article","_id":"1408","date_updated":"2023-02-23T10:02:11Z","publisher":"Springer","article_processing_charge":"Yes (via OA deal)","doi":"10.1007/s00454-016-9794-2","quality_controlled":"1","ddc":["510"],"page":"126 - 164","publist_id":"5799","related_material":{"record":[{"id":"1510","status":"public","relation":"earlier_version"}]},"year":"2016","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). ","date_published":"2016-07-01T00:00:00Z","ec_funded":1,"publication":"Discrete & Computational Geometry","status":"public","project":[{"_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","grant_number":"M01980","name":"Robust invariants of Nonlinear Systems","call_identifier":"FWF"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"date_created":"2018-12-11T11:51:51Z","volume":56,"title":"On computability and triviality of well groups","oa_version":"Published Version","day":"01","scopus_import":1,"author":[{"first_name":"Peter","last_name":"Franek","id":"473294AE-F248-11E8-B48F-1D18A9856A87","full_name":"Franek, Peter"},{"first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál"}],"file_date_updated":"2020-07-14T12:44:53Z","publication_status":"published","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":"        56","abstract":[{"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.","lang":"eng"}],"has_accepted_license":"1","file":[{"file_name":"IST-2016-614-v1+1_s00454-016-9794-2.pdf","access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"e0da023abf6b72abd8c6a8c76740d53c","date_created":"2018-12-12T10:10:55Z","file_size":905303,"date_updated":"2020-07-14T12:44:53Z","creator":"system","file_id":"4846"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"07","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"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>.","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>","ista":"Franek P, Krcál M. 2016. On computability and triviality of well groups. Discrete &#38; Computational Geometry. 56(1), 126–164.","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>.","short":"P. Franek, M. Krcál, Discrete &#38; Computational Geometry 56 (2016) 126–164.","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.","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>"},"issue":"1","language":[{"iso":"eng"}],"pubrep_id":"614","oa":1},{"month":"06","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"language":[{"iso":"eng"}],"citation":{"ama":"Krcál M, Pilarczyk P. Computation of cubical Steenrod squares. In: Vol 9667. Springer; 2016:140-151. doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>","ieee":"M. Krcál and P. Pilarczyk, “Computation of cubical Steenrod squares,” presented at the CTIC: Computational Topology in Image Context, Marseille, France, 2016, vol. 9667, pp. 140–151.","short":"M. Krcál, P. Pilarczyk, in:, Springer, 2016, pp. 140–151.","chicago":"Krcál, Marek, and Pawel Pilarczyk. “Computation of Cubical Steenrod Squares,” 9667:140–51. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>.","ista":"Krcál M, Pilarczyk P. 2016. Computation of cubical Steenrod squares. CTIC: Computational Topology in Image Context, LNCS, vol. 9667, 140–151.","apa":"Krcál, M., &#38; Pilarczyk, P. (2016). Computation of cubical Steenrod squares (Vol. 9667, pp. 140–151). Presented at the CTIC: Computational Topology in Image Context, Marseille, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>","mla":"Krcál, Marek, and Pawel Pilarczyk. <i>Computation of Cubical Steenrod Squares</i>. Vol. 9667, Springer, 2016, pp. 140–51, doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"day":"02","author":[{"first_name":"Marek","last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek"},{"first_name":"Pawel","last_name":"Pilarczyk","id":"3768D56A-F248-11E8-B48F-1D18A9856A87","full_name":"Pilarczyk, Pawel"}],"oa_version":"None","title":"Computation of cubical Steenrod squares","volume":9667,"date_created":"2018-12-11T11:50:52Z","intvolume":"      9667","abstract":[{"text":"Bitmap images of arbitrary dimension may be formally perceived as unions of m-dimensional boxes aligned with respect to a rectangular grid in ℝm. Cohomology and homology groups are well known topological invariants of such sets. Cohomological operations, such as the cup product, provide higher-order algebraic topological invariants, especially important for digital images of dimension higher than 3. If such an operation is determined at the level of simplicial chains [see e.g. González-Díaz, Real, Homology, Homotopy Appl, 2003, 83-93], then it is effectively computable. However, decomposing a cubical complex into a simplicial one deleteriously affects the efficiency of such an approach. In order to avoid this overhead, a direct cubical approach was applied in [Pilarczyk, Real, Adv. Comput. Math., 2015, 253-275] for the cup product in cohomology, and implemented in the ChainCon software package [http://www.pawelpilarczyk.com/chaincon/]. We establish a formula for the Steenrod square operations [see Steenrod, Annals of Mathematics. Second Series, 1947, 290-320] directly at the level of cubical chains, and we prove the correctness of this formula. An implementation of this formula is programmed in C++ within the ChainCon software framework. We provide a few examples and discuss the effectiveness of this approach. One specific application follows from the fact that Steenrod squares yield tests for the topological extension problem: Can a given map A → Sd to a sphere Sd be extended to a given super-complex X of A? In particular, the ROB-SAT problem, which is to decide for a given function f: X → ℝm and a value r &gt; 0 whether every g: X → ℝm with ∥g - f ∥∞ ≤ r has a root, reduces to the extension problem.","lang":"eng"}],"publication_status":"published","year":"2016","publist_id":"6096","status":"public","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7"},{"_id":"255F06BE-B435-11E9-9278-68D0E5697425","grant_number":"622033","name":"Persistent Homology - Images, Data and Maps","call_identifier":"FP7"}],"ec_funded":1,"acknowledgement":"The research conducted by both authors has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreements no. 291734 (for M. K.) and no. 622033 (for P. P.).","date_published":"2016-06-02T00:00:00Z","conference":{"name":"CTIC: Computational Topology in Image Context","end_date":"2016-06-17","start_date":"2016-06-15","location":"Marseille, France"},"alternative_title":["LNCS"],"doi":"10.1007/978-3-319-39441-1_13","publisher":"Springer","_id":"1237","date_updated":"2021-01-12T06:49:18Z","type":"conference","page":"140 - 151","quality_controlled":"1"},{"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publist_id":"5466","article_number":"26","year":"2015","month":"08","issue":"4","citation":{"ama":"Franek P, Krcál M. Robust satisfiability of systems of equations. <i>Journal of the ACM</i>. 2015;62(4). doi:<a href=\"https://doi.org/10.1145/2751524\">10.1145/2751524</a>","short":"P. Franek, M. Krcál, Journal of the ACM 62 (2015).","ieee":"P. Franek and M. Krcál, “Robust satisfiability of systems of equations,” <i>Journal of the ACM</i>, vol. 62, no. 4. ACM, 2015.","chicago":"Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.” <i>Journal of the ACM</i>. ACM, 2015. <a href=\"https://doi.org/10.1145/2751524\">https://doi.org/10.1145/2751524</a>.","ista":"Franek P, Krcál M. 2015. Robust satisfiability of systems of equations. Journal of the ACM. 62(4), 26.","mla":"Franek, Peter, and Marek Krcál. “Robust Satisfiability of Systems of Equations.” <i>Journal of the ACM</i>, vol. 62, no. 4, 26, ACM, 2015, doi:<a href=\"https://doi.org/10.1145/2751524\">10.1145/2751524</a>.","apa":"Franek, P., &#38; Krcál, M. (2015). Robust satisfiability of systems of equations. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2751524\">https://doi.org/10.1145/2751524</a>"},"date_published":"2015-08-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication":"Journal of the ACM","language":[{"iso":"eng"}],"status":"public","date_updated":"2021-01-12T06:52:30Z","volume":62,"_id":"1682","type":"journal_article","date_created":"2018-12-11T11:53:27Z","author":[{"first_name":"Peter","last_name":"Franek","full_name":"Franek, Peter"},{"full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","first_name":"Marek"}],"doi":"10.1145/2751524","day":"01","scopus_import":1,"publisher":"ACM","oa_version":"Preprint","title":"Robust satisfiability of systems of equations","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1402.0858"}],"publication_status":"published","quality_controlled":"1","abstract":[{"text":"We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α &gt; 0, it holds that each function g: K → ℝn such that ||g - f || ∞ &lt; α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K &gt; 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.","lang":"eng"}],"intvolume":"        62"},{"publication_status":"published","file_date_updated":"2020-07-14T12:44:59Z","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)"},"abstract":[{"text":"The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r &gt; 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. 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 R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K &lt; 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n 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. ","lang":"eng"}],"intvolume":"        34","has_accepted_license":"1","date_created":"2018-12-11T11:52:26Z","volume":34,"oa_version":"Published Version","title":"On computability and triviality of well groups","author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","full_name":"Franek, Peter","last_name":"Franek","first_name":"Peter"},{"last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","first_name":"Marek"}],"day":"11","scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Franek, P., &#38; Krcál, M. (2015). On computability and triviality of well groups (Vol. 34, pp. 842–856). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>","mla":"Franek, Peter, and Marek Krcál. <i>On Computability and Triviality of Well Groups</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–56, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>.","chicago":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups,” 34:842–56. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>.","ista":"Franek P, Krcál M. 2015. On computability and triviality of well groups. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 842–856.","ieee":"P. Franek and M. Krcál, “On computability and triviality of well groups,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 842–856.","short":"P. Franek, M. Krcál, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–856.","ama":"Franek P, Krcál M. On computability and triviality of well groups. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:842-856. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>"},"pubrep_id":"503","language":[{"iso":"eng"}],"oa":1,"file":[{"file_size":623563,"date_created":"2018-12-12T10:13:19Z","creator":"system","date_updated":"2020-07-14T12:44:59Z","file_id":"5001","file_name":"IST-2016-503-v1+1_32.pdf","access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"49eb5021caafaabe5356c65b9c5f8c9c"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"06","quality_controlled":"1","ddc":["510"],"page":"842 - 856","type":"conference","date_updated":"2023-02-21T17:02:57Z","_id":"1510","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.SOCG.2015.842","alternative_title":["LIPIcs"],"date_published":"2015-06-11T00:00:00Z","conference":{"location":"Eindhoven, Netherlands","name":"SoCG: Symposium on Computational Geometry","start_date":"2015-06-22","end_date":"2015-06-25"},"ec_funded":1,"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"status":"public","publist_id":"5667","related_material":{"record":[{"relation":"later_version","status":"public","id":"1408"}]},"year":"2015"},{"status":"public","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","oa":1,"date_published":"2014-11-14T00:00:00Z","acknowledgement":"Marek Krčál was supported by the ERC Advanced Grant No. 267165.","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","issue":"1","citation":{"short":"J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete &#38; Computational Geometry 53 (2014) 64–79.","ieee":"J. Cibulka, P. Gao, M. Krcál, T. Valla, and P. Valtr, “On the geometric ramsey number of outerplanar graphs,” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 1. Springer, pp. 64–79, 2014.","ama":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. On the geometric ramsey number of outerplanar graphs. <i>Discrete &#38; Computational Geometry</i>. 2014;53(1):64-79. doi:<a href=\"https://doi.org/10.1007/s00454-014-9646-x\">10.1007/s00454-014-9646-x</a>","mla":"Cibulka, Josef, et al. “On the Geometric Ramsey Number of Outerplanar Graphs.” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 1, Springer, 2014, pp. 64–79, doi:<a href=\"https://doi.org/10.1007/s00454-014-9646-x\">10.1007/s00454-014-9646-x</a>.","apa":"Cibulka, J., Gao, P., Krcál, M., Valla, T., &#38; Valtr, P. (2014). On the geometric ramsey number of outerplanar graphs. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-014-9646-x\">https://doi.org/10.1007/s00454-014-9646-x</a>","ista":"Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey number of outerplanar graphs. Discrete &#38; Computational Geometry. 53(1), 64–79.","chicago":"Cibulka, Josef, Pu Gao, Marek Krcál, Tomáš Valla, and Pavel Valtr. “On the Geometric Ramsey Number of Outerplanar Graphs.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00454-014-9646-x\">https://doi.org/10.1007/s00454-014-9646-x</a>."},"month":"11","year":"2014","publist_id":"5260","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"abstract":[{"text":"We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.","lang":"eng"}],"intvolume":"        53","page":"64 - 79","publication_status":"published","main_file_link":[{"url":"http://arxiv.org/abs/1310.7004","open_access":"1"}],"oa_version":"Submitted Version","publisher":"Springer","title":"On the geometric ramsey number of outerplanar graphs","author":[{"full_name":"Cibulka, Josef","last_name":"Cibulka","first_name":"Josef"},{"full_name":"Gao, Pu","last_name":"Gao","first_name":"Pu"},{"first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál"},{"first_name":"Tomáš","last_name":"Valla","full_name":"Valla, Tomáš"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"}],"doi":"10.1007/s00454-014-9646-x","day":"14","scopus_import":1,"type":"journal_article","date_created":"2018-12-11T11:54:18Z","date_updated":"2021-01-12T06:53:33Z","volume":53,"_id":"1842"},{"publication_status":"published","abstract":[{"text":"Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X→ Y. We consider a computational version, where X,Y are given as finite simplicial complexes, and the goal is to compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected; in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or computing the Z2-index-everything in the stable range. Outside the stable range, the extension problem is undecidable.","lang":"eng"}],"intvolume":"        61","date_created":"2018-12-11T11:56:12Z","volume":61,"title":"Computing all maps into a sphere","oa_version":"Preprint","scopus_import":1,"day":"01","author":[{"last_name":"Čadek","full_name":"Čadek, Martin","first_name":"Martin"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","last_name":"Krcál","first_name":"Marek"},{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Francis","last_name":"Sergeraert","full_name":"Sergeraert, Francis"},{"first_name":"Lukáš","full_name":"Vokřínek, Lukáš","last_name":"Vokřínek"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Čadek, Martin, et al. “Computing All Maps into a Sphere.” <i>Journal of the ACM</i>, vol. 61, no. 3, 17, ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2597629\">10.1145/2597629</a>.","apa":"Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., &#38; Wagner, U. (2014). Computing all maps into a sphere. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2597629\">https://doi.org/10.1145/2597629</a>","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere.” <i>Journal of the ACM</i>. ACM, 2014. <a href=\"https://doi.org/10.1145/2597629\">https://doi.org/10.1145/2597629</a>.","ista":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing all maps into a sphere. Journal of the ACM. 61(3), 17.","short":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal of the ACM 61 (2014).","ieee":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” <i>Journal of the ACM</i>, vol. 61, no. 3. ACM, 2014.","ama":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. <i>Journal of the ACM</i>. 2014;61(3). doi:<a href=\"https://doi.org/10.1145/2597629\">10.1145/2597629</a>"},"issue":"3","language":[{"iso":"eng"}],"oa":1,"article_number":"17 ","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"month":"05","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1105.6257","open_access":"1"}],"type":"journal_article","_id":"2184","date_updated":"2021-01-12T06:55:50Z","publisher":"ACM","doi":"10.1145/2597629","date_published":"2014-05-01T00:00:00Z","acknowledgement":"The research by M. K. was supported by project GAUK 49209. The research by M. K. was also supported by project 1M0545 by the Ministry of Education of the Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague (project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).","publication":"Journal of the ACM","status":"public","publist_id":"4797","year":"2014"},{"date_updated":"2021-01-12T06:59:51Z","_id":"2807","type":"conference","doi":"10.1145/2488608.2488683","publisher":"ACM","quality_controlled":"1","page":"595 - 604","ddc":["510"],"publist_id":"4078","year":"2013","date_published":"2013-06-01T00:00:00Z","conference":{"location":"Palo Alto, CA, United States","name":"STOC: Symposium on the Theory of Computing","end_date":"2013-06-04","start_date":"2013-06-01"},"status":"public","publication":"45th Annual ACM Symposium on theory of computing","date_created":"2018-12-11T11:59:42Z","author":[{"first_name":"Martin","full_name":"Čadek, Martin","last_name":"Čadek"},{"first_name":"Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek","last_name":"Krcál"},{"first_name":"Jiří","full_name":"Matoušek, Jiří","last_name":"Matoušek"},{"full_name":"Vokřínek, Lukáš","last_name":"Vokřínek","first_name":"Lukáš"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"scopus_import":1,"day":"01","oa_version":"Submitted Version","title":"Extending continuous maps: Polynomiality and undecidability","publication_status":"published","file_date_updated":"2020-07-14T12:45:48Z","has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \\no holes up to dimension k-1&quot; (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. "}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"file":[{"relation":"main_file","checksum":"06c2ce5c1135fbc1f71ca15eeb242dcf","file_name":"IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf","access_level":"open_access","content_type":"application/pdf","file_id":"5081","file_size":447945,"date_created":"2018-12-12T10:14:29Z","creator":"system","date_updated":"2020-07-14T12:45:48Z"}],"month":"06","citation":{"ama":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps: Polynomiality and undecidability. In: <i>45th Annual ACM Symposium on Theory of Computing</i>. ACM; 2013:595-604. doi:<a href=\"https://doi.org/10.1145/2488608.2488683\">10.1145/2488608.2488683</a>","short":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, U. Wagner, in:, 45th Annual ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604.","ieee":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous maps: Polynomiality and undecidability,” in <i>45th Annual ACM Symposium on theory of computing</i>, Palo Alto, CA, United States, 2013, pp. 595–604.","ista":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of computing. STOC: Symposium on the Theory of Computing, 595–604.","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. “Extending Continuous Maps: Polynomiality and Undecidability.” In <i>45th Annual ACM Symposium on Theory of Computing</i>, 595–604. ACM, 2013. <a href=\"https://doi.org/10.1145/2488608.2488683\">https://doi.org/10.1145/2488608.2488683</a>.","mla":"Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.” <i>45th Annual ACM Symposium on Theory of Computing</i>, ACM, 2013, pp. 595–604, doi:<a href=\"https://doi.org/10.1145/2488608.2488683\">10.1145/2488608.2488683</a>.","apa":"Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., &#38; Wagner, U. (2013). Extending continuous maps: Polynomiality and undecidability. In <i>45th Annual ACM Symposium on theory of computing</i> (pp. 595–604). Palo Alto, CA, United States: ACM. <a href=\"https://doi.org/10.1145/2488608.2488683\">https://doi.org/10.1145/2488608.2488683</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"pubrep_id":"533"},{"publist_id":"4466","month":"01","year":"2012","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"date_published":"2012-01-01T00:00:00Z","citation":{"ama":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. In: SIAM; 2012:1-10.","ieee":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 1–10.","short":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, in:, SIAM, 2012, pp. 1–10.","ista":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2012. Computing all maps into a sphere. SODA: Symposium on Discrete Algorithms, 1–10.","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere,” 1–10. SIAM, 2012.","apa":"Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., &#38; Wagner, U. (2012). Computing all maps into a sphere (pp. 1–10). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","mla":"Čadek, Martin, et al. <i>Computing All Maps into a Sphere</i>. SIAM, 2012, pp. 1–10."},"extern":1,"status":"public","type":"conference","date_created":"2018-12-11T11:57:40Z","date_updated":"2021-01-12T06:57:30Z","_id":"2440","publisher":"SIAM","title":"Computing all maps into a sphere","author":[{"full_name":"Čadek, Martin","last_name":"Čadek","first_name":"Martin"},{"last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Marek Krcál","first_name":"Marek"},{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Francis","last_name":"Sergeraert","full_name":"Sergeraert, Francis"},{"full_name":"Vokřínek, Lukáš","last_name":"Vokřínek","first_name":"Lukáš"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"day":"01","publication_status":"published","quality_controlled":0,"main_file_link":[{"url":"http://arxiv.org/abs/1105.6257","open_access":"0"}],"abstract":[{"text":"We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d - 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere S d), and dim X ≤ 2d - 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ 2-index, which is a quantity playing a prominent role in Borsuk-Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝ d also amounts to a ℤ 2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science.","lang":"eng"}],"page":"1 - 10"}]