---
_id: '6681'
_version: 30
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."
accept: '1'
alternative_title:
- IST Austria Thesis
author:
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
cc_license: cc_by
citation:
ama: Zhechev SY. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria; 2019. doi:10.15479/AT:ISTA:6681
apa: Zhechev, S. Y. (2019). *Algorithmic aspects of homotopy theory and embeddability*.
IST Austria. https://doi.org/10.15479/AT:ISTA:6681
chicago: Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.
ieee: S. Y. Zhechev, *Algorithmic aspects of homotopy theory and embeddability*.
IST Austria, 2019.
ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability,
IST Austria, 104p.
mla: Zhechev, Stephan Y. *Algorithmic Aspects of Homotopy Theory and Embeddability*.
IST Austria, 2019, doi:10.15479/AT:ISTA:6681.
short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, IST
Austria, 2019.
creator:
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
login: szhechev
date_created: 2019-07-26T11:14:34Z
date_published: 2019-08-08T00:00:00Z
date_updated: 2020-01-21T13:21:43Z
day: '08'
ddc:
- '514'
department:
- _id: UlWa
tree:
- _id: ResearchGroups
- _id: IST
doi: 10.15479/AT:ISTA:6681
file:
- access_level: open_access
content_type: application/pdf
creator: szhechev
date_created: 2019-08-07T13:02:50Z
date_updated: 2019-08-07T13:02:50Z
file_id: '6771'
file_name: Stephan_Zhechev_thesis.pdf
file_size: 1464227
open_access: 1
relation: main_file
request_a_copy: 0
- access_level: closed
content_type: application/octet-stream
creator: szhechev
date_created: 2019-08-07T13:03:22Z
date_updated: 2019-08-08T06:41:37Z
file_id: '6772'
file_name: Stephan_Zhechev_thesis.tex
file_size: 303988
open_access: 0
relation: source_file
request_a_copy: 0
- access_level: closed
content_type: application/zip
creator: szhechev
date_created: 2019-08-07T13:03:34Z
date_updated: 2019-08-08T06:41:37Z
file_id: '6773'
file_name: supplementary_material.zip
file_size: 1087004
open_access: 0
relation: supplementary_material
request_a_copy: 0
file_date_updated: 2019-08-08T06:41:37Z
language:
- iso: eng
month: '08'
oa_version: Published Version
page: '104'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: IST 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
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...