{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:53Z","timestamp":1781031413599,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Carlsberg Foundation","award":["CF24-1929"],"award-info":[{"award-number":["CF24-1929"]}]},{"name":"Independent Research Fund Denmark","award":["1054-00032B"],"award-info":[{"award-number":["1054-00032B"]}]},{"name":"VILLUM Foundation","award":["16582"],"award-info":[{"award-number":["16582"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800745","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"256-267","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["NP-Membership for the Boundary-Boundary Art-Gallery Problem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9153-6589","authenticated-orcid":false,"given":"Jack","family":"Stade","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486220"},{"key":"e_1_3_2_1_3_1","volume-title":"Advances in Neural Information Processing Systems","author":"Abrahamsen Mikkel","year":"1829","unstructured":"Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. 2021. Training Neural Networks is \u2203 R-complete. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.). 34, Curran Associates, Inc., 18293\u201318306. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/9813b270ed0288e7c0388f0fd4ec68f5-Paper.pdf"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00098"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2020.3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2000.848640"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS \u201923)","author":"Bertschinger Daniel","year":"2023","unstructured":"Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. 2023. Training fully connected neural networks is \u2203 R-complete. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS \u201923). Curran Associates Inc., Red Hook, NY, USA. Article 1571, 16 pages."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Ahmad Biniaz Anil Maheshwari Magnus Christian Ring Merrild Joseph S. B. Mitchell Saeed Odak Valentin Polishchuk Eliot W. Robson Casper Moldrup Rysgaard Jens Kristian Refsgaard Schou Thomas Shermer Jack Spalding-Jamieson Rolf Svenning and Da Wei Zheng. 2025. Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In 41st International Symposium on Computational Geometry (SoCG 2025) Oswin Aichholzer and Haitao Wang (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs) Vol. 332). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany. 20:1\u201320:21. isbn:978-3-95977-370-6 issn:1868-8969 https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2025.20 10.4230\/LIPIcs.SoCG.2025.20","DOI":"10.4230\/LIPIcs.SoCG.2025.20"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1963.263416"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2007.1"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649764"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670130104"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003710050177"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057165"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212022"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00081"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/96877.96909"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082792"},{"key":"e_1_3_2_1_22_1","volume-title":"Art gallery theorems and algorithms. 57","author":"O\u2019Rourke Joseph","unstructured":"Joseph O\u2019Rourke. 1987. Art gallery theorems and algorithms. 57, Oxford New York, NY, USA."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-0110-0_24"},{"key":"e_1_3_2_1_24_1","unstructured":"Marcus Schaefer Jean Cardinal and Tillmann Miltzow. 2024. The Existential Theory of the Reals as a Complexity Class: A Compendium. arxiv:2407.18006. arxiv:2407.18006"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Peter W. Shor. 1990. Stretchability of Pseudolines is NP-Hard. In Applied Geometry And Discrete Mathematics. https:\/\/api.semanticscholar.org\/CorpusID:43637487","DOI":"10.1090\/dimacs\/004\/41"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2025.74"},{"key":"e_1_3_2_1_28_1","unstructured":"Jack Stade. 2026. NP-membership for the boundary-boundary art-gallery problem. arxiv:2511.01562. arxiv:2511.01562"},{"key":"e_1_3_2_1_29_1","volume-title":"A Decision Method for Elementary Algebra and Geometry (dgo - digital original, 1 ed.)","author":"Tarski Alfred","unstructured":"Alfred Tarski and J. C. C. McKinsey. 1951. A Decision Method for Elementary Algebra and Geometry (dgo - digital original, 1 ed.). University of California Press. http:\/\/www.jstor.org\/stable\/jj.8501420"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800745","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:17Z","timestamp":1781027897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800745"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":29,"alternative-id":["10.1145\/3798129.3800745","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800745","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}