Jiri Matousek - Algorithmic aspects of embedding simplical complexes in R^d 

It is well known that one can test in linear time whether a given graph is planar.
We consider the higher-dimensional generalization of this problem:
given a k-dimensional simplicial complex K and a target dimension d, does K embed
(piecewise linearly) into R^d? The algorithmic complexity of this problem turns out
to depend strongly on k and d. In some cases (k = d-1 and d>4) the problem is
algorithmically undecidable, in others it is polynomial-time solvable, and in some
cases we have results such as decidability or NP-hardness. We will survey the main
results, which in some cases involve methods of classical homotopy theory combined
with more recent algorithmic methods, and in others (embedding in R^3) methods of
3-dimensional topology. Joint work with Martin Cadek, Marek Krcal, Eric Sedgwick,
Francis Sergeraert, Martin Tancer, Lukas Vokrinek, and Uli Wagner.