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