Hardness of embedding simplicial complexes in ${\mathbb{R}}^d$

Jiří Matoušek, Martin Tancer, Uli Wagner

Let EMBED(k,d) be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into R^d? Know…