---
_id: '1073'
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.
article_processing_charge: No
author:
- first_name: Martin
  full_name: Čadek, Martin
  last_name: Čadek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Lukáš
  full_name: Vokřínek, Lukáš
  last_name: Vokřínek
citation:
  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>
  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>.
  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.
  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.
  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>.
  short: M. Čadek, M. Krcál, L. Vokřínek, Discrete &#38; Computational Geometry 54
    (2017) 915–965.
date_created: 2018-12-11T11:50:00Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:01:28Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-016-9855-6
external_id:
  isi:
  - '000400072700008'
intvolume: '        54'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1307.6444
month: '06'
oa: 1
oa_version: Submitted Version
page: 915 - 965
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - '01795376'
publication_status: published
publisher: Springer
publist_id: '6309'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithmic solvability of the lifting extension problem
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 54
year: '2017'
...
---
_id: '568'
abstract:
- lang: eng
  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).'
author:
- first_name: Peter
  full_name: Franek, Peter
  id: 473294AE-F248-11E8-B48F-1D18A9856A87
  last_name: Franek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
citation:
  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>
  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>.
  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.
  ista: Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and
    Applications. 19(2), 313–342.
  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>.
  short: P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.
date_created: 2018-12-11T11:47:14Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:03:12Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.4310/HHA.2017.v19.n2.a16
ec_funded: 1
intvolume: '        19'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1507.04310
month: '01'
oa: 1
oa_version: Submitted Version
page: 313 - 342
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
- _id: 2590DB08-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '701309'
  name: Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes
    (H2020)
publication: Homology, Homotopy and Applications
publication_identifier:
  issn:
  - '15320073'
publication_status: published
publisher: International Press
publist_id: '7246'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistence of zero sets
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 19
year: '2017'
...
---
_id: '1408'
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.'
acknowledgement: 'Open access funding provided by Institute of Science and Technology
  (IST Austria). '
article_processing_charge: Yes (via OA deal)
author:
- first_name: Peter
  full_name: Franek, Peter
  id: 473294AE-F248-11E8-B48F-1D18A9856A87
  last_name: Franek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
citation:
  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>.
  short: P. Franek, M. Krcál, Discrete &#38; Computational Geometry 56 (2016) 126–164.
date_created: 2018-12-11T11:51:51Z
date_published: 2016-07-01T00:00:00Z
date_updated: 2023-02-23T10:02:11Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/s00454-016-9794-2
ec_funded: 1
file:
- access_level: open_access
  checksum: e0da023abf6b72abd8c6a8c76740d53c
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:55Z
  date_updated: 2020-07-14T12:44:53Z
  file_id: '4846'
  file_name: IST-2016-614-v1+1_s00454-016-9794-2.pdf
  file_size: 905303
  relation: main_file
file_date_updated: 2020-07-14T12:44:53Z
has_accepted_license: '1'
intvolume: '        56'
issue: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 126 - 164
project:
- _id: 25F8B9BC-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M01980
  name: Robust invariants of Nonlinear Systems
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5799'
pubrep_id: '614'
quality_controlled: '1'
related_material:
  record:
  - id: '1510'
    relation: earlier_version
    status: public
scopus_import: 1
status: public
title: On computability and triviality of well groups
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2016'
...
---
_id: '1237'
abstract:
- lang: eng
  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.'
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.).
alternative_title:
- LNCS
author:
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Pawel
  full_name: Pilarczyk, Pawel
  id: 3768D56A-F248-11E8-B48F-1D18A9856A87
  last_name: Pilarczyk
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>'
  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>'
  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>.
  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.'
  ista: 'Krcál M, Pilarczyk P. 2016. Computation of cubical Steenrod squares. CTIC:
    Computational Topology in Image Context, LNCS, vol. 9667, 140–151.'
  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>.
  short: M. Krcál, P. Pilarczyk, in:, Springer, 2016, pp. 140–151.
conference:
  end_date: 2016-06-17
  location: Marseille, France
  name: 'CTIC: Computational Topology in Image Context'
  start_date: 2016-06-15
date_created: 2018-12-11T11:50:52Z
date_published: 2016-06-02T00:00:00Z
date_updated: 2021-01-12T06:49:18Z
day: '02'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/978-3-319-39441-1_13
ec_funded: 1
intvolume: '      9667'
language:
- iso: eng
month: '06'
oa_version: None
page: 140 - 151
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
- _id: 255F06BE-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '622033'
  name: Persistent Homology - Images, Data and Maps
publication_status: published
publisher: Springer
publist_id: '6096'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computation of cubical Steenrod squares
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9667
year: '2016'
...
---
_id: '1682'
abstract:
- lang: eng
  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.'
article_number: '26'
author:
- first_name: Peter
  full_name: Franek, Peter
  last_name: Franek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
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>
  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>
  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>.
  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.
  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>.
  short: P. Franek, M. Krcál, Journal of the ACM 62 (2015).
date_created: 2018-12-11T11:53:27Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:52:30Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2751524
intvolume: '        62'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1402.0858
month: '08'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '5466'
quality_controlled: '1'
scopus_import: 1
status: public
title: Robust satisfiability of systems of equations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2015'
...
---
_id: '1510'
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 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. '
alternative_title:
- LIPIcs
author:
- first_name: Peter
  full_name: Franek, Peter
  id: 473294AE-F248-11E8-B48F-1D18A9856A87
  last_name: Franek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
citation:
  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>'
  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>'
  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>.
  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.'
  ista: 'Franek P, Krcál M. 2015. On computability and triviality of well groups.
    SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 842–856.'
  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>.
  short: P. Franek, M. Krcál, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2015, pp. 842–856.
conference:
  end_date: 2015-06-25
  location: Eindhoven, Netherlands
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2015-06-22
date_created: 2018-12-11T11:52:26Z
date_published: 2015-06-11T00:00:00Z
date_updated: 2023-02-21T17:02:57Z
day: '11'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.4230/LIPIcs.SOCG.2015.842
ec_funded: 1
file:
- access_level: open_access
  checksum: 49eb5021caafaabe5356c65b9c5f8c9c
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:13:19Z
  date_updated: 2020-07-14T12:44:59Z
  file_id: '5001'
  file_name: IST-2016-503-v1+1_32.pdf
  file_size: 623563
  relation: main_file
file_date_updated: 2020-07-14T12:44:59Z
has_accepted_license: '1'
intvolume: '        34'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 842 - 856
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5667'
pubrep_id: '503'
quality_controlled: '1'
related_material:
  record:
  - id: '1408'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: On computability and triviality of well groups
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2015'
...
---
_id: '1842'
abstract:
- lang: eng
  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.
acknowledgement: Marek Krčál was supported by the ERC Advanced Grant No. 267165.
author:
- first_name: Josef
  full_name: Cibulka, Josef
  last_name: Cibulka
- first_name: Pu
  full_name: Gao, Pu
  last_name: Gao
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Tomáš
  full_name: Valla, Tomáš
  last_name: Valla
- first_name: Pavel
  full_name: Valtr, Pavel
  last_name: Valtr
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete &#38; Computational
    Geometry 53 (2014) 64–79.
date_created: 2018-12-11T11:54:18Z
date_published: 2014-11-14T00:00:00Z
date_updated: 2021-01-12T06:53:33Z
day: '14'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/s00454-014-9646-x
intvolume: '        53'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1310.7004
month: '11'
oa: 1
oa_version: Submitted Version
page: 64 - 79
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5260'
scopus_import: 1
status: public
title: On the geometric ramsey number of outerplanar graphs
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 53
year: '2014'
...
---
_id: '2184'
abstract:
- lang: eng
  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.'
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).
article_number: '17 '
author:
- first_name: Martin
  full_name: Čadek, Martin
  last_name: Čadek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Francis
  full_name: Sergeraert, Francis
  last_name: Sergeraert
- first_name: Lukáš
  full_name: Vokřínek, Lukáš
  last_name: Vokřínek
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  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>
  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>.
  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.
  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.
  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>.
  short: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal
    of the ACM 61 (2014).
date_created: 2018-12-11T11:56:12Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2021-01-12T06:55:50Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2597629
intvolume: '        61'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1105.6257
month: '05'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '4797'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing all maps into a sphere
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2014'
...
---
_id: '2807'
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. '
author:
- first_name: Martin
  full_name: Čadek, Martin
  last_name: Čadek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Lukáš
  full_name: Vokřínek, Lukáš
  last_name: Vokřínek
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
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>'
  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>'
  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>.'
  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.'
  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>.'
  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.
conference:
  end_date: 2013-06-04
  location: Palo Alto, CA, United States
  name: 'STOC: Symposium on the Theory of Computing'
  start_date: 2013-06-01
date_created: 2018-12-11T11:59:42Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2021-01-12T06:59:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2488608.2488683
file:
- access_level: open_access
  checksum: 06c2ce5c1135fbc1f71ca15eeb242dcf
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:14:29Z
  date_updated: 2020-07-14T12:45:48Z
  file_id: '5081'
  file_name: IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf
  file_size: 447945
  relation: main_file
file_date_updated: 2020-07-14T12:45:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 595 - 604
publication: 45th Annual ACM Symposium on theory of computing
publication_status: published
publisher: ACM
publist_id: '4078'
pubrep_id: '533'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Extending continuous maps: Polynomiality and undecidability'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2440'
abstract:
- lang: eng
  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.
author:
- first_name: Martin
  full_name: Čadek, Martin
  last_name: Čadek
- first_name: Marek
  full_name: Marek Krcál
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Francis
  full_name: Sergeraert, Francis
  last_name: Sergeraert
- first_name: Lukáš
  full_name: Vokřínek, Lukáš
  last_name: Vokřínek
- first_name: Uli
  full_name: Uli Wagner
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
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.'
  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.'
  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.
  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.'
  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.'
  mla: Čadek, Martin, et al. <i>Computing All Maps into a Sphere</i>. SIAM, 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.
conference:
  name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2018-12-11T11:57:40Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2021-01-12T06:57:30Z
day: '01'
extern: 1
main_file_link:
- open_access: '0'
  url: http://arxiv.org/abs/1105.6257
month: '01'
page: 1 - 10
publication_status: published
publisher: SIAM
publist_id: '4466'
quality_controlled: 0
status: public
title: Computing all maps into a sphere
type: conference
year: '2012'
...