{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:10Z","timestamp":1781031430870,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":42,"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":"Jack Stade is supported by the starting Grant from the Independent Research Fund Denmark under the Sapere Aude research career programme","award":["1054-00032B"],"award-info":[{"award-number":["1054-00032B"]}]},{"name":"Jack Stade is supported by the Carlsberg Foundation","award":["CF24-1929"],"award-info":[{"award-number":["CF24-1929"]}]},{"name":"Egor Bakaev, Florestan Brunck, Jack Stade and Amir Yehudayoff are partially supported by the Villum Foundation BARC grant","award":["54451"],"award-info":[{"award-number":["54451"]}]},{"name":"Egor Bakaev, Florestan Brunck and Amir Yehudayoff are supported by a Chair grant from the Danish National Research Foundation","award":["20231101-28697"],"award-info":[{"award-number":["20231101-28697"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800768","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"500-507","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Better Neural Network Expressivity: Subdividing the Simplex"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-9008-0656","authenticated-orcid":false,"given":"Egor","family":"Bakaev","sequence":"first","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4921-2824","authenticated-orcid":false,"given":"Florestan","family":"Brunck","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5646-8567","authenticated-orcid":false,"given":"Christoph","family":"Hertrich","sequence":"additional","affiliation":[{"name":"University of Technology Nuremberg, Nuremberg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9153-6589","authenticated-orcid":false,"given":"Jack","family":"Stade","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0177-1814","authenticated-orcid":false,"given":"Amir","family":"Yehudayoff","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"},{"name":"Technion, Haifa, Israel"}],"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.1137\/1.9781611978322.63"},{"key":"e_1_3_2_1_2_1","volume-title":"International conference on machine learning. 146\u2013155","author":"Amos Brandon","year":"2017","unstructured":"Brandon Amos, Lei Xu, and Zico Kolter. 2017. Input convex neural networks. In International conference on machine learning. 146\u2013155. https:\/\/proceedings.mlr.press\/v70\/amos17b.html"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1611.01491"},{"key":"e_1_3_2_1_4_1","volume-title":"On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth. In The Thirteenth International Conference on Learning Representations.","author":"Averkov Gennadiy","year":"2025","unstructured":"Gennadiy Averkov, Christopher Hojny, and Maximilian Merkert. 2025. On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth. In The Thirteenth International Conference on Learning Representations."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Egor Bakaev Florestan Brunck Christoph Hertrich Daniel Reichman and Amir Yehudayoff. 2025. On the Depth of Monotone ReLU Neural Networks and ICNNs. arXiv preprint arXiv:2505.06169 https:\/\/doi.org\/10.48550\/arXiv.2505.06169 10.48550\/arXiv.2505.06169","DOI":"10.48550\/arXiv.2505.06169"},{"key":"e_1_3_2_1_6_1","volume-title":"The Thirteenth International Conference on Learning Representations.","author":"Brandenburg Marie-Charlotte","year":"2025","unstructured":"Marie-Charlotte Brandenburg, Moritz Grillo, and Christoph Hertrich. 2025. Decomposition polyhedra of piecewise linear functions. In The Thirteenth International Conference on Learning Representations."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-023-01969-x"},{"key":"e_1_3_2_1_8_1","volume-title":"Philipp Heer, and John Lygeros.","author":"B\u00fcnning Felix","year":"2021","unstructured":"Felix B\u00fcnning, Adrian Schalbetter, Ahmed Aboudonia, Mathias Hudoba de Badyn, Philipp Heer, and John Lygeros. 2021. Input convex neural networks for building MPC. In Learning for dynamics and control. 251\u2013262."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0520"},{"key":"e_1_3_2_1_10_1","volume-title":"International Conference on Learning Representations.","author":"Chen Yize","year":"2019","unstructured":"Yize Chen, Yuanyuan Shi, and Baosen Zhang. 2019. Optimal control via neural networks: A convex approach. In International Conference on Learning Representations."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.epsr.2020.106741"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238217"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211037"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02551274"},{"key":"e_1_3_2_1_15_1","volume-title":"Conference on learning theory. 907\u2013940","author":"Eldan Ronen","year":"2016","unstructured":"Ronen Eldan and Ohad Shamir. 2016. The power of depth for feedforward neural networks. In Conference on learning theory. 907\u2013940. https:\/\/proceedings.mlr.press\/v49\/eldan16.html"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"1642","author":"Ergen Ekin","year":"2024","unstructured":"Ekin Ergen and Moritz Grillo. 2024. Topological Expressivity of ReLU Neural Networks. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 1599\u20131642. https:\/\/proceedings.mlr.press\/v247\/ergen24a.html"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Moritz Grillo Christoph Hertrich and Georg Loho. 2025. Depth-Bounds for Neural Networks via the Braid Arrangement. arXiv:2502.09324 https:\/\/doi.org\/10.48550\/arXiv.2502.09324 10.48550\/arXiv.2502.09324","DOI":"10.48550\/arXiv.2502.09324"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Branko Gr\u00fcnbaum. 2003. Convex Polytopes. Springer-Verlag New York. https:\/\/doi.org\/10.1007\/978-1-4613-0019-9 10.1007\/978-1-4613-0019-9","DOI":"10.1007\/978-1-4613-0019-9"},{"key":"e_1_3_2_1_20_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Haase Christian","year":"2023","unstructured":"Christian Haase, Christoph Hertrich, and Georg Loho. 2023. Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4208\/jcm.1901-m2018-0160"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","unstructured":"Christoph Hertrich. 2022. Facets of neural network complexity. Technische Universitaet Berlin (Germany). https:\/\/doi.org\/10.14279\/depositonce-15271 10.14279\/depositonce-15271","DOI":"10.14279\/depositonce-15271"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1489332"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Christoph Hertrich and Georg Loho. 2024. Neural Networks and (Virtual) Extended Formulations. arXiv:2411.03006 https:\/\/doi.org\/10.48550\/arXiv.2411.03006 10.48550\/arXiv.2411.03006","DOI":"10.48550\/arXiv.2411.03006"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(89)90020-8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Joey Huchette Gonzalo Mu\u00f1oz Thiago Serra and Calvin Tsay. 2023. When deep learning meets polyhedral theory: A survey. arXiv preprint arXiv:2305.00241 https:\/\/doi.org\/10.48550\/arXiv.2305.00241 10.48550\/arXiv.2305.00241","DOI":"10.48550\/arXiv.2305.00241"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80131-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/161"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2021.3065238"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5858-8_9"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969033.2969153"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Anirbit Mukherjee and Amitabh Basu. 2017. Lower bounds over Boolean inputs for deep neural networks with ReLU gates. arXiv preprint arXiv:1711.03073 https:\/\/doi.org\/10.48550\/arXiv.1711.03073 10.48550\/arXiv.1711.03073","DOI":"10.48550\/arXiv.1711.03073"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Itay Safran. 2026. A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory. arXiv preprint arXiv:2601.01417 https:\/\/doi.org\/10.48550\/arXiv.2601.01417 10.48550\/arXiv.2601.01417","DOI":"10.48550\/arXiv.2601.01417"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-021-09532-7"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.113"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139003858"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_3_2_1_38_1","volume-title":"Conference on learning theory. 1517\u20131539","author":"Telgarsky Matus","year":"2016","unstructured":"Matus Telgarsky. 2016. Benefits of depth in neural networks. In Conference on learning theory. 1517\u20131539."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Juan Valerdi. 2024. On Minimal Depth in Neural Networks. arXiv:2402.15315 https:\/\/doi.org\/10.48550\/arXiv.2402.15315 10.48550\/arXiv.2402.15315","DOI":"10.48550\/arXiv.2402.15315"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.859246"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Ryan Williams. 2018. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds ReLUs and Low-Degree Polynomials. In CCC. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2018.6 10.4230\/LIPIcs.CCC.2018.6","DOI":"10.4230\/LIPIcs.CCC.2018.6"},{"key":"e_1_3_2_1_42_1","volume-title":"International Conference on Machine Learning. 5824\u20135832","author":"Zhang Liwen","year":"2018","unstructured":"Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. 2018. Tropical geometry of deep neural networks. In International Conference on Machine Learning. 5824\u20135832."}],"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.3800768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:43Z","timestamp":1781028043000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":42,"alternative-id":["10.1145\/3798129.3800768","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800768","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"}}]}}