Fetching the paper…
Reading the bibliography…
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$.
“A Universality Theorem for Nested Polytopes”, arXiv preprint, 2019
Michael Dobbins, Andreas Holmsen and Tillmann Miltzow · 1908
Earlier work this paper cites.
“Dimensionstheorie”
Karl Menger · 1928
Earlier work this paper cites.
“Über n-dimensionale Komplexe, die im R 2 n + 1 \textrm{R}_{2n+1} absolut selbstverschlungen sind”
Antonio Flores · 1933
Earlier work this paper cites.
“Komplexe in euklidischen Räumen”
Egbert Van · 1933
Earlier work this paper cites.
“A new proof of the invariance of the homology groups of a complex”
Christos Papakyriakopoulos · 1943
Earlier work this paper cites.
“Obstructions to the imbedding of a complex in a Euclidean space.: I. The first obstruction”
Arnold Shapiro · 1957
Earlier work this paper cites.
“An Alternative Proof that 3-Manifolds Can be Triangulated”
R.. Bing · 1959
Earlier work this paper cites.
“Imbeddings of simplicial complexes”
Branko Gr“”unbaum · 1969
Earlier work this paper cites.
“Polytopes, graphs, and complexes”
Branko Gr“”unbaum · 1970
Earlier work this paper cites.
“Approximating embeddings of polyhedra in codimension three”
J.. Bryant · 1972
Earlier work this paper cites.
“Efficient planarity testing”
John Hopcroft and Robert Tarjan · 1974
Earlier work this paper cites.
“On Whitney’s theorem on the unique embeddability of 3-connected planar graphs”
Wilfried Imrich · 1975
Earlier work this paper cites.
“The Product of Nonplanar Complexes does not Imbed in 4-Space”
Brian. Ummel · 1978
Earlier work this paper cites.
“A nonpolyhedral triangulated Möbius strip”
Ulrich Brehm · 1983
Earlier work this paper cites.
“Some algebraic and geometric computations in PSPACE”
John Canny · 1988
Earlier work this paper cites.
“The universality theorems on the classification problem of configuration varieties and convex polytopes varieties”
Nicolai Mn“”ev · 1988
Earlier work this paper cites.
“Stretchability of pseudolines is NP-hard”
Peter Shor · 1991
Earlier work this paper cites.
“Linear vs. Piecewise-Linear Embeddability of Simplicial complexes” available at http://kssarkaria.org/docs/Linear
Ulrich Brehm and Karanbir. Sarkaria · 1992
Earlier work this paper cites.
“Van Kampen’s embedding Obstruction is incomplete for 2 2 -Complexes in ℝ 4 \mathbb{R}^{4} ”
Michael. Freedman, Vyacheslav. Krushkal and Peter Teichner · 1994
Earlier work this paper cites.
“Realization spaces of 4-polytopes are universal”
J“”urgen Richter-Gebert and G“”unter. Ziegler · 1995
Earlier work this paper cites.
“Realization spaces of polytopes” 1643
J“”urgen Richter-Gebert · 1996
Earlier work this paper cites.
“On the generation of oriented matroids”
J“”urgen Bokowski and A. de Oliveira · 2000
Earlier work this paper cites.
“A note on geometric embeddings of simplicial complexes in a Euclidean space”
Isabella Novik · 2000
Cited alongside, same era.
“Realization of Posets”
Patrice Ossona deMendez · 2002
Cited alongside, same era.
“On embeddability of joins and their ’factors”’, arXiv preprint, 2020
S. Parsa and A. Skopenkov · 2003
Cited alongside, same era.
“Knots and links in spatial graphs: a survey”
JL“’rez Alfons“’n · 2005
Cited alongside, same era.
“Extendability of simplicial maps is undecidable”, arXiv preprint, 2020
Arkadiy Skopenkov · 2008
Cited alongside, same era.
“Necessary conditions for geometric realizability of simplicial complexes”
“Embedding products of graphs into Euclidean spaces”, arXiv preprint, 2016
Mikhail Skopenkov · 2016
Later among the works it cites.
“Algorithmic solvability of the lifting-extension problem”
Martin Cadek, Marek Krc“’al and Luk“’as Vokr“’nek · 2017
Later among the works it cites.
“Recognition and complexity of point visibility graphs”
Jean Cardinal and Udo Hoffmann · 2017
Later among the works it cites.
“Polyhedral Maps”
Egon Schulte and Ulrich Brehm · 2017
Later among the works it cites.
“The art gallery problem is ∃ ℝ \exists\mathbb{R} -complete”
Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow · 2018
Later among the works it cites.
“ ∃ ℝ \exists\mathbb{R} -Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria”
Jugal Garg, Ruta Mehta, Vijay. Vazirani and Sadra Yazdanbod · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Dagmar Timmreck · 2008
Cited alongside, same era.
“A history of algebraic and differential topology, 1900-1960”
Jean Dieudonn“’e · 2009
Cited alongside, same era.
“Complexity of some geometric and topological problems”
Marcus Schaefer · 2009
Cited alongside, same era.
“Hardness of embedding simplicial complexes in ℝ d \mathbb{R}^{d} ”
Jir“’ Matousek, Martin Tancer and Uli Wagner · 2011
Cited alongside, same era.
“Integer realizations of disk and segment graphs”
Colin McDiarmid and Tobias M“”uller · 2012
Cited alongside, same era.
“Polynomial-time homology for simplicial Eilenberg–MacLane spaces”
Marek Krc“’al, Jir“’ Matousek and Francis Sergeraert · 2013
Cited alongside, same era.
“Computing all maps into a sphere”
Martin Cadek, Marek Krc“’al, Jir“’ Matousek, Francis Sergeraert, Luk“’as Vokr“’nek and Uli Wagner · 2014
Cited alongside, same era.
Later among the works it cites.
“On the Complexity of Embeddable Simplicial Complexes” diploma thesis, arXiv preprint, 2018
Anna Gundert · 2018
Later among the works it cites.
“The Complexity of Drawing a Graph in a Polygonal Region”
Anna Lubiw, Tillmann Miltzow and Debajyoti Mondal · 2018
Later among the works it cites.
“Embeddability in the 3-sphere is decidable”
Jir“’ Matousek, Eric Sedgwick, Martin Tancer and Uli Wagner · 2018
Later among the works it cites.
“On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2 d-Space”
Salman Parsa · 2018
Later among the works it cites.
Johannes Carmesin · 2019
Later among the works it cites.
“A short exposition of Salman Parsa’s theorems on intrinsic linking and non-realizability”
Arkadiy Skopenkov · 2019
Later among the works it cites.
“Hardness of almost embedding simplicial complexes in ℝ d \mathbb{R}^{d} ”
Arkadiy Skopenkov and Martin Tancer · 2019
Later among the works it cites.
“Framework for ER-Completeness of Two-Dimensional Packing Problems”
Mikkel Abrahamsen, Tillmann Miltzow and Nadja Seiferth · 2020
Later among the works it cites.
“Smoothing the gap between NP and ER”
Jeff Erickson, Ivor van der Hoog and Tillmann Miltzow · 2020
Later among the works it cites.
“Embeddability of Simplicial Complexes is Undecidable”
Marek Filakovsk“’y, Uli Wagner and Stephan Zhechev · 2020
Later among the works it cites.
“Embeddability in ℝ 3 \mathbb{R}^{3} is NP-hard”
Arnaud Mesmay, Yo’av Rieck, Eric Sedgwick and Martin Tancer · 2020
Later among the works it cites.
“Invariants of graph drawings in the plane”
Arkadiy Skopenkov · 2020
Later among the works it cites.
“Covering Polygons is Even Harder” to appear
Mikkel Abrahamsen · 2021
Closest in time.
“Training Neural Networks is ∃ ℝ \exists\mathbb{R} -complete” to appear
Mikkel Abrahamsen, Linda Kleist and Tillmann Miltzow · 2021
Closest in time.
“Jordan Curve Theorem” accessed 18-10-2021, https://en.wikipedia.org/wiki/Jordan_curve_theorem
Wikipedia · 2021
Closest in time.