Geometric Embeddability of Complexes Is ∃R-Complete

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt

Standard

Geometric Embeddability of Complexes Is ∃R-Complete. / Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann.

39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 1 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt

Harvard

Abrahamsen, M, Kleist, L & Miltzow, T 2023, Geometric Embeddability of Complexes Is ∃R-Complete. i EW Chambers & J Gudmundsson (red), 39th International Symposium on Computational Geometry, SoCG 2023., 1, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 258, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, USA, 12/06/2023. https://doi.org/10.4230/LIPIcs.SoCG.2023.1

APA

Abrahamsen, M., Kleist, L., & Miltzow, T. (2023). Geometric Embeddability of Complexes Is ∃R-Complete. I E. W. Chambers, & J. Gudmundsson (red.), 39th International Symposium on Computational Geometry, SoCG 2023 [1] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 258 https://doi.org/10.4230/LIPIcs.SoCG.2023.1

Vancouver

Abrahamsen M, Kleist L, Miltzow T. Geometric Embeddability of Complexes Is ∃R-Complete. I Chambers EW, Gudmundsson J, red., 39th International Symposium on Computational Geometry, SoCG 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 1. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258). https://doi.org/10.4230/LIPIcs.SoCG.2023.1

Author

Abrahamsen, Mikkel ; Kleist, Linda ; Miltzow, Tillmann. / Geometric Embeddability of Complexes Is ∃R-Complete. 39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

Bibtex

@inproceedings{255828c6a4914fd2aad8ae95c989cff5,
title = "Geometric Embeddability of Complexes Is ∃R-Complete",
abstract = "We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.",
keywords = "existential theory of the reals, geometric embedding, hypergraph, linear embedding, recognition, simplicial complex",
author = "Mikkel Abrahamsen and Linda Kleist and Tillmann Miltzow",
note = "Publisher Copyright: {\textcopyright} Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0.; 39th International Symposium on Computational Geometry, SoCG 2023 ; Conference date: 12-06-2023 Through 15-06-2023",
year = "2023",
doi = "10.4230/LIPIcs.SoCG.2023.1",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Chambers, {Erin W.} and Joachim Gudmundsson",
booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",

}

RIS

TY - GEN

T1 - Geometric Embeddability of Complexes Is ∃R-Complete

AU - Abrahamsen, Mikkel

AU - Kleist, Linda

AU - Miltzow, Tillmann

N1 - Publisher Copyright: © Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow; licensed under Creative Commons License CC-BY 4.0.

PY - 2023

Y1 - 2023

N2 - We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

AB - We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

KW - existential theory of the reals

KW - geometric embedding

KW - hypergraph

KW - linear embedding

KW - recognition

KW - simplicial complex

UR - http://www.scopus.com/inward/record.url?scp=85163072339&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2023.1

DO - 10.4230/LIPIcs.SoCG.2023.1

M3 - Article in proceedings

AN - SCOPUS:85163072339

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 39th International Symposium on Computational Geometry, SoCG 2023

Y2 - 12 June 2023 through 15 June 2023

ER -

ID: 384029530