[1]   Mikkel Abrahamsen: Covering polygons is even harder. In Proc. 62nd FOCS, pp. 375–386. IEEE Comp. Soc., 2021. [doi:10.1109/FOCS52979.2021.00045]

[2]   Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow: The art gallery problem is ∃R-complete. J. ACM, 69(1):4:1–70, 2022. [doi:10.1145/3486220]

[3]   Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow: Training neural networks is ∃R-complete. In Proc. 34th Adv. Neural Info. Proc. Sys. (NeurIPS’21), pp. 18293–18306. Curran Assoc., 2021. Available at NeurIPS.

[4]   Mikkel Abrahamsen and Tillmann Miltzow: Dynamic toolbox for ERTINV, 2019. [arXiv:1912.08674]

[5]   Reyan Ahmed, Felice de Luca, Sabin Devkota, Stephen Kobourov, and Mingwei Li: Multicriteria scalable graph drawing via stochastic gradient descent, (SGD)². IEEE Trans. Visualiz. & Computer Graphics, 28(6):2388–2399, 2022. Open-access link at the NSF PAR. [doi:10.1109/TVCG.2022.3155564]

[6]   Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee: Understanding deep neural networks with rectified linear units. In Int. Conf. Learning Representations (ICLR’18). ICLR, 2018. Available at OpenReview.

[7]   Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, and Amir Yehudayoff: Better neural network expressivity: Subdividing the simplex. In Proc. 58th STOC, pp. 500–507. ACM Press, 2026. [doi:10.1145/3798129.3800768]

[8]   Ainesh Bakshi, Rajesh Jayaram, and David P. Woodruff: Learning two layer rectified neural networks in polynomial time. In Proc. 32nd Ann. Conf. on Learning Theory (COLT’19), pp. 195–268. MLR Press, 2019. Available at PMLR.

[9]   Marie Louisa Tølbøll Berthelsen and Kristoffer Arnsfelt Hansen: On the computational complexity of decision problems about multi-player Nash equilibria. Theory Computing Sys., 66(3):519–545, 2022. [doi:10.1007/s00224-022-10080-1]

[10]   Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber: Training fully connected neural networks is ∃R-complete. In Proc. 36th Adv. Neural Info. Proc. Sys. (NeurIPS’23), pp. 36222–36237. Curran Assoc., 2023. Available at NeurIPS.

[11]   Daniel Bienstock, Gonzalo Muñoz, and Sebastian Pokutta: Principled deep neural network training through linear programming. Discr. Optimization, 49(100795):1–37, 2023. [doi:10.1016/j.disopt.2023.100795]

[12]   Vittorio Bilò and Marios Mavronicolas: ∃R-complete decision problems about (symmetric) Nash equilibria in (symmetric) multi-player games. ACM Trans. Econ. Comput., 9(3):14:1–25, 2021. [doi:10.1145/3456758]

[13]   Manon Blanc and Kristoffer Arnsfelt Hansen: Computational complexity of multi-player evolutionarily stable strategies. In Proc. 16th Comp. Sci. Symp. in Russia (CSR’21), pp. 1–17. Springer, 2021. [doi:10.1007/978-3-030-79416-3_1]

[14]   Lenore Blum, Mike Shub, and Steve Smale: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. AMS, 21(1):1–46, 1989. [doi:10.1090/S0273-0979-1989-15750-9]

[15]   Digvijay Boob, Santanu S. Dey, and Guanghui Lan: Complexity of training ReLU neural network. Discr. Optimization, 44(1):1–16, 2022. [doi:10.1016/j.disopt.2020.100620]

[16]   Cornelius Brand, Robert Ganian, and Mathis Rocton: New complexity-theoretic frontiers of tractability for neural network training. In Proc. 36th Adv. Neural Info. Proc. Sys. (NeurIPS’23), pp. 56456–56468. Curran Assoc., 2023. Available at NeurIPS.

[17]   Alon Brutzkus and Amir Globerson: Globally optimal gradient descent for a ConvNet with Gaussian inputs. In Proc. 34th Internat. Conf. Machine Learning (ICML’17), pp. 605–614. MLR Press, 2017. Available at PMLR.

[18]   Sébastien Bubeck and Mark Sellke: A universal law of robustness via isoperimetry. J. ACM, 70(2):10:1–18, 2023. [doi:10.1145/3578580]

[19]   Peter Bürgisser and Felipe Cucker: Exotic quantifiers, complexity classes, and complete problems. Found. Computational Math., 9(2):135–170, 2009. [doi:10.1007/s10208-007-9006-9]

[20]   John F. Canny: Some algebraic and geometric computations in PSPACE. In Proc. 20th STOC, pp. 460–467. ACM Press, 1988. [doi:10.1145/62212.62257]

[21]   Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber: Intersection graphs of rays and grounded segments. J. Graph Algor. & Appl., 22(2):273–295, 2018. [doi:10.7155/jgaa.00470]

[22]   Sitan Chen, Aravind Gollakota, Adam R. Klivans, and Raghu Meka: Hardness of noise-free learning for two-hidden-layer neural networks. In Proc. 35th Adv. Neural Info. Proc. Sys. (NeurIPS’22), pp. 10709–10724. Curran Assoc., 2022. Available at NeurIPS.

[23]   Sitan Chen, Adam R. Klivans, and Raghu Meka: Learning deep ReLU networks is fixed-parameter tractable. In Proc. 62nd FOCS, pp. 696–707. IEEE Comp. Soc., 2021. [doi:10.1109/FOCS52979.2021.00073]

[24]   Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell: On restricted nonnegative matrix factorization. In Proc. 43rd Internat. Colloq. on Automata, Languages, and Programming (ICALP’16), pp. 103:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.103]

[25]   George Cybenko: Approximation by superpositions of a sigmoidal function. Math. of Control, Signals & Systems, 2(4):303–314, 1989. [doi:10.1007/BF02551274]

[26]   Julian D’Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrel: On the complexity of the escape problem for linear dynamical systems over compact semialgebraic sets. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’21), pp. 33:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.MFCS.2021.33]

[27]   Pedro J. de Rezende, Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kröller, and Davi C. Tozoni: Engineering art galleries. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of LNCS, pp. 379–417. Springer, 2016. [doi:10.1007/978-3-319-49487-6_12, arXiv:1410.8720]

[28]   Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis: Approximating the existential theory of the reals. J. Comput. System Sci., 125:106–128, 2022. [doi:10.1016/j.jcss.2021.11.002]

[29]   Steffen Dereich and Sebastian Kassing: On minimal representations of shallow ReLU networks. Neural Networks, 148:121–128, 2022. [doi:10.1016/j.neunet.2022.01.006]

[30]   Santanu S. Dey, Guany Wang, and Yao Xie: Approximation algorithms for training one-node ReLU neural networks. IEEE Trans. Signal Processing, 68:6696–6706, 2020. [doi:10.1109/TSP.2020.3039360]

[31]   Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, and Mahdi Soltanolkotabi: Approximation schemes for ReLU regression. In Proc. 33rd Ann. Conf. on Learning Theory (COLT’20), pp. 1452–1485. MLR Press, 2020. Available at PMLR.

[32]   Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzążewski: Completeness for the complexity class ∀∃R and area-universality. Discr. Comput. Geom., 70(1):154–188, 2023. [doi:10.1007/s00454-022-00381-0]

[33]   Ronen Eldan and Ohad Shamir: The power of depth for feedforward neural networks. In Proc. 29th Ann. Conf. on Learning Theory (COLT’16), pp. 907–940. Springer, 2016. Available at PMLR.

[34]   Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow: Smoothing the gap between NP and ∃R. SIAM J. Comput., 53(6):102–138, 2024. [doi:10.1137/20M1385287]

[35]   Vincent Froese and Christoph Hertrich: Training neural networks is NP-hard in fixed dimension. In Proc. 36th Adv. Neural Info. Proc. Sys. (NeurIPS’23), pp. 44039–44049. Curran Assoc., 2023. Available at NeurIPS.

[36]   Vincent Froese, Christoph Hertrich, and Rolf Niedermeier: The computational complexity of ReLU network training parameterized by data dimensionality. J. Artif. Intell. Res., 74:1775–1790, 2022. [doi:10.1613/jair.1.13547]

[37]   Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod: ∃R-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput., 6(1):1:1–23, 2018. [doi:10.1145/3175494]

[38]   Xavier Glorot, Antoine Bordes, and Yoshua Bengio: Deep sparse rectifier neural networks. In Proc. 14th Internat. Conf. Artificial Intelligence and Statistics (AISTATS’11), pp. 315–323. MLR Press, 2011. Available at PMLR.

[39]   Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler: Reliably learning the ReLU in polynomial time. In Proc. 30th Ann. Conf. on Learning Theory (COLT’17), pp. 1004–1042. MLR Press, 2017. Available at PMLR.

[40]   Surbhi Goel and Adam R. Klivans: Learning neural networks with two nonlinear layers in polynomial time. In Proc. 32nd Ann. Conf. on Learning Theory (COLT’19), pp. 1470–1499. MLR Press, 2019. Available at PMLR.

[41]   Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman: Tight hardness results for training depth-2 ReLU networks. In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 22:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021 (virtual conference). [doi:10.4230/LIPIcs.ITCS.2021.22]

[42]   Surbhi Goel, Adam R. Klivans, and Raghu Meka: Learning one convolutional layer with overlapping patches. In Proc. 35th Internat. Conf. Machine Learning (ICML’18), pp. 1783–1791. MLR Press, 2018. Available at PMLR.

[43]   Ian Goodfellow, Yoshua Bengio, and Aaron Courville: Deep Learning. MIT Press, 2016. Available at MIT.

[44]   Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree: Regularisation of neural networks by enforcing Lipschitz continuity. Machine Learning, 110(2):393–416, 2021. [doi:10.1007/s10994-020-05929-w]

[45]   Christian Haase, Christoph Hertrich, and Georg Loho: Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In Int. Conf. Learning Representations (ICLR’23). ICLR, 2023. Available at OpenReview.

[46]   Boris Hanin: Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics, 7(10):992:1–9, 2019. [doi:10.3390/math7100992]

[47]   Boris Hanin and David Rolnick: Complexity of linear regions in deep networks. In Proc. 36th Internat. Conf. Machine Learning (ICML’19), pp. 2596–2604. MLR Press, 2019. Available at PMLR.

[48]   Boris Hanin and Mark Sellke: Approximating continuous functions by ReLU nets of minimal width, 2018. [arXiv:1710.11278]

[49]   Simon B. Hengeveld and Tillmann Miltzow: A practical algorithm with performance guarantees for the Art Gallery problem. Discr. Math. & Theor. Comput. Sci., 25(2):1–59, 2023. Preliminary version in SoCG’21. [doi:10.46298/DMTCS.9225]

[50]   Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella: Towards lower bounds on the depth of ReLU neural networks. SIAM J. Discr. Math., 37(2):997–1029, 2023. [doi:10.1137/22M1489332]

[51]   Christoph Hertrich and Leon Sering: ReLU neural networks of polynomial size for exact maximum flow computation. Math. Programming, 210(1):377–406, 2025. [doi:10.1007/s10107-024-02096-x]

[52]   Kurt Hornik: Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251–257, 1991. [doi:10.1016/0893-6080(91)90009-T]

[53]   Joey Huchette, Gonzalo Muñoz, Tiago Serra, and Calvin Tsay: When deep learning meets polyhedral theory: A survey, 2023. [arXiv:2305.00241]

[54]   Paul Jungeblut: On the complexity of Lombardi graph drawing. In Graph Drawing & Network Visualization (GD’23), pp. 180–194. Springer, 2023. [doi:10.1007/978-3-031-49272-3_13]

[55]   Paul Jungeblut, Linda Kleist, and Tillmann Miltzow: The complexity of the Hausdorff distance. Discr. Comput. Geom., 71(1):177–213, 2024. [doi:10.1007/s00454-023-00562-5]

[56]   Ross Kang and Tobias Müller: Sphere and dot product representations of graphs. Discr. Comput. Geom., 47(3):548–569, 2012. [doi:10.1007/s00454-012-9394-8]

[57]   Sammy Khalife, Hongyu Cheng, and Amitabh Basu: Neural networks with linear threshold activations: Structure and algorithms. Math. Programming, 206:333–356, 2024. [doi:10.1007/s10107-023-02016-5]

[58]   Jan Kratochvíl and Jiří Matoušek: Intersection graphs of segments. J. Combin. Theory–B, 62(2):289–315, 1994. [doi:10.1006/jctb.1994.1071]

[59]   Shiyu Liang and Rayadurgam Srikant: Why deep neural networks for function approximation? In Int. Conf. Learning Representations (ICLR’17). ICLR, 2017. Available at OpenReview.

[60]   Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal: The complexity of drawing a graph in a polygonal region. J. Graph Algor. & Appl., 26(4):421–446, 2022. [doi:10.7155/jgaa.00602]

[61]   Jiří Matoušek: Intersection graphs of segments and ∃R, 2014. [arXiv:1406.2636]

[62]   Colin McDiarmid and Tobias Müller: Integer realizations of disk and segment graphs. J. Combin. Theory–B, 103(1):114–143, 2013. [doi:10.1016/j.jctb.2012.09.004]

[63]   Tillmann Miltzow and Reinier F. Schmiermann: On classifying continuous constraint satisfaction problems. TheoretiCS, 3(10):1–54, 2024. Preliminary version in FOCS’22. [doi:10.46298/THEORETICS.24.10]

[64]   Nikolai E. Mnëv: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Oleg Y. Viro and Anatoly M. Vershik, editors, Topology and Geometry — Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pp. 527–543. Springer, 1988. [doi:10.1007/BFb0082792]

[65]   Guido Montúfar, Yue Ren, and Leon Zhang: Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums. SIAM J. Appl. Algebra Geom., 6(4):618–649, 2022. [doi:10.1137/21M1413699]

[66]   Guido F. Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio: On the number of linear regions of deep neural networks. In Proc. 27th Adv. Neural Info. Proc. Sys. (NIPS’14), pp. 2924–2932. Curran Assoc., 2014. Available at NeurIPS.

[67]   Anirbit Mukherjee and Amitabh Basu: Lower bounds over Boolean inputs for deep neural networks with ReLU gates, 2017. [arXiv:1711.03073]

[68]   Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein: Neural networks should be wide enough to learn disconnected decision regions. In Proc. 35th Internat. Conf. Machine Learning (ICML’18), pp. 3740–3749. MLR Press, 2018. Available at PMLR.

[69]   Razvan Pascanu, Guido Montúfar, and Yoshua Bengio: On the number of inference regions of deep feed forward networks with piece-wise linear activations. In Int. Conf. Learning Representations (ICLR’14). ICLR, 2014. Available at OpenReview.

[70]   Grant O. Passmore and Paul B. Jackson: Combined decision techniques for the existential theory of the reals. In Internat. Conf. Intell. Computer Math. (CICM’09), pp. 122–137. Springer, 2009. [doi:10.1007/978-3-642-02614-0_14]

[71]   Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein: On the expressive power of deep neural networks. In Proc. 34th Internat. Conf. Machine Learning (ICML’17), pp. 2847–2854. MLR Press, 2017. Available at PMLR.

[72]   Daniel Richardson: Some undecidable problems involving elementary functions of a real variable. J. Symbolic Logic, 33(4):514–520, 1969. [doi:10.2307/2271358]

[73]   Jürgen Richter-Gebert and Günter M. Ziegler: Realization spaces of 4-polytopes are universal. Bull. AMS, 32(4):403–412, 1995. [doi:10.1090/S0273-0979-1995-00604-X]

[74]   Itay Safran and Ohad Shamir: Depth-width tradeoffs in approximating natural functions with neural networks. In Proc. 34th Internat. Conf. Machine Learning (ICML’17), pp. 2979–2987. MLR Press, 2017. Available at PMLR.

[75]   Marcus Schaefer: Complexity of some geometric and topological problems. In Graph Drawing (GD’09), pp. 334–344. Springer, 2009. [doi:10.1007/978-3-642-11805-0_32]

[76]   Marcus Schaefer: Realizability of graphs and linkages. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, 2013. [doi:10.1007/978-1-4614-0110-0_24]

[77]   Marcus Schaefer: Complexity of geometric k-planarity for fixed k. J. Graph Algor. & Appl., 25(1):29–41, 2021. [doi:10.7155/jgaa.00548]

[78]   Marcus Schaefer: RAC-drawability is ∃R-complete and related results. J. Graph Algor. & Appl., 27(9):803–841, 2023. [doi:10.7155/jgaa.00646]

[79]   Marcus Schaefer, Jean Cardinal, and Tillmann Miltzow: The existential theory of the reals as a complexity class: A compendium. In János Pach and Géza Tóth, editors, Courses in Discrete and Computational Geometry, volume 31 of Bolyai Society Mathematical Studies, pp. 167–313. Springer, Cham, 2026. [doi:10.1007/978-3-032-10503-5_5, arXiv:2407.18006]

[80]   Marcus Schaefer and Daniel Štefankovič: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Computing Sys., 60(2):172–193, 2017. [doi:10.1007/s00224-015-9662-0]

[81]   Marcus Schaefer and Daniel Štefankovič: Beyond the existential theory of the reals. Theory Computing Sys., 68(2):195–226, 2024. [doi:10.1007/s00224-023-10151-x]

[82]   Marcus Schaefer and Daniel Štefankovič: The complexity of tensor rank. Theory Computing Sys., 62(5):1161–1174, 2018. [doi:10.1007/s00224-017-9800-y]

[83]   Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam: Bounding and counting linear regions of deep neural networks. In Proc. 35th Internat. Conf. Machine Learning (ICML’18), pp. 4558–4566. MLR Press, 2018. Available at PMLR.

[84]   Shai Shalev-Shwartz and Shai Ben-David: Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, 2014. [doi:10.1017/CBO9781107298019]

[85]   Yaroslav Shitov: The complexity of positive semidefinite matrix factorization. SIAM J. Optim., 27(3):1898–1909, 2017. [doi:10.1137/16M1080616]

[86]   Peter W. Shor: Stretchability of pseudolines is NP-hard. In Appl. Geom. & Discr. Math., pp. 531–554. Amer. Math. Soc., 1991. [doi:10.1090/dimacs/004/41]

[87]   Jack Stade: The point-boundary art gallery problem is ∃R-hard. In Proc. 41st Internat. Symp. Comput. Geom. (SoCG’25), pp. 74:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2025. [doi:10.4230/LIPIcs.SoCG.2025.74, arXiv:2210.12817]

[88]   Moritz Stargalla, Christoph Hertrich, and Daniel Reichman: The computational complexity of counting linear regions in ReLU neural networks. In Proc. 38th Adv. Neural Info. Proc. Sys. (NeurIPS’25), pp. 125970–125988. Curran Assoc., 2025. Available at NeurIPS.

[89]   Matus Telgarsky: Benefits of depth in neural networks. In Proc. 29th Ann. Conf. on Learning Theory (COLT’16), pp. 1517–1539. Springer, 2016. Available at PMLR.

[90]   Leslie G. Valiant: A theory of the learnable. Comm. ACM, 27(11):1134–1142, 1984. [doi:10.1145/1968.1972]

[91]   Gal Vardi, Gilad Yehudai, and Ohad Shamir: On the optimal memorization power of ReLU neural networks. In Int. Conf. Learning Representations (ICLR’22). ICLR, 2022. Available at OpenReview.

[92]   Dmitry Yarotsky: Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103–114, 2017. [doi:10.1016/j.neunet.2017.07.002]

[93]   Chulhee Yun, Suvrit Sra, and Ali Jadbabaie: Small ReLU networks are powerful memorizers: A tight analysis of memorization capacity. In Proc. 32nd Adv. Neural Info. Proc. Sys. (NeurIPS’19). Curran Assoc., 2019. Available at NeurIPS.

[94]   Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals: Understanding deep learning (still) requires rethinking generalization. Comm. ACM, 64(3):107–115, 2021. [doi:10.1145/3446776]

[95]   Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim: Tropical geometry of deep neural networks. In Proc. 35th Internat. Conf. Machine Learning (ICML’18), pp. 5824–5832. MLR Press, 2018. Available at PMLR.

[96]   Xiao-Dong Zhang: Complexity of neural network learning in the real number model. In Workshop on Physics and Computation, pp. 146–150. IEEE Comp. Soc., 1992. [doi:10.1109/PHYCMP.1992.615511]