Informatics Colloquium 5.10. Computational complexity in combinatorial topology
Informatics Colloquium 5.10. 2021, 14:00 lecture hall D2 doc. RNDr. Martin Tancer, Ph.D., MFF UK Computational complexity in combinatorial topology Abstract:Interactions between the theory of computation and topology date back at least to 1950's when Novikov proved that simple conectedness (of a triangulated topological spaces) is algorithmically undecidable. Nowadays, there are a plethora of interactions that mutually enrich both fields. The aim of the talk is to survey and explain some such recent interactions---naturally those that I have been working on. This will include the algorithmic embeddability question, various decompositions of simplicial complexes, or untangling (un)knots.