{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:23:39Z","timestamp":1777487019235,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA95502010341"],"award-info":[{"award-number":["FA95502010341"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF2006587"],"award-info":[{"award-number":["CCF2006587"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10107-023-02016-5","type":"journal-article","created":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T13:02:42Z","timestamp":1694523762000},"page":"333-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Neural networks with linear threshold activations: structure and algorithms"],"prefix":"10.1007","volume":"206","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3161-7794","authenticated-orcid":false,"given":"Sammy","family":"Khalife","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongyu","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amitabh","family":"Basu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,12]]},"reference":[{"key":"2016_CR1","first-page":"18293","volume":"34","author":"M Abrahamsen","year":"2021","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Training neural networks is $$\\exists {\\mathbb{R} }$$-complete. Adv. Neural. Inf. Process. Syst. 34, 18293\u201318306 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"2016_CR2","doi-asserted-by":"crossref","unstructured":"Anthony, M., Bartlett, P.L.: Neural network learning: Theoretical foundations. cambridge university press (1999)","DOI":"10.1017\/CBO9780511624216"},{"key":"2016_CR3","unstructured":"Arora, R., Basu, A., Mianjy, P., Mukherjee, A.: Understanding deep neural networks with rectified linear units. In: International Conference on Learning Representations (2018)"},{"key":"2016_CR4","unstructured":"Bartlett, P.L., Harvey, N., Liaw, C., Mehrabian, A.: Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks (2017)"},{"key":"2016_CR5","unstructured":"Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., Weber, S.: Training fully connected neural networks is $$\\exists {\\mathbb{R}}$$-complete. arXiv preprint arXiv:2204.01368 (2022)"},{"key":"2016_CR6","unstructured":"Bienstock, D., Mu\u00f1oz, G., Pokutta, S.: Principled deep neural network training through linear programming. arXiv preprint arXiv:1810.03218 (2018)"},{"key":"2016_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2020.100620","volume":"44","author":"D Boob","year":"2020","unstructured":"Boob, D., Dey, S.S., Lan, G.: Complexity of training relu neural network. Discrete Opt. 44, 100620 (2020)","journal-title":"Discrete Opt."},{"key":"2016_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2020.100620","volume":"44","author":"D Boob","year":"2022","unstructured":"Boob, D., Dey, S.S., Lan, G.: Complexity of training relu neural network. Discret. Optim. 44, 100620 (2022)","journal-title":"Discret. Optim."},{"key":"2016_CR9","unstructured":"Cohen, N., Sharir, O., Shashua, A.: On the expressive power of deep learning: A tensor analysis. In: V.\u00a0Feldman, A.\u00a0Rakhlin, O.\u00a0Shamir (eds.) 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, vol.\u00a049, pp. 698\u2013728. PMLR, Columbia University, New York, New York, USA (2016). https:\/\/proceedings.mlr.press\/v49\/cohen16.html"},{"issue":"4","key":"2016_CR10","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF02551274","volume":"2","author":"G Cybenko","year":"1989","unstructured":"Cybenko, G.: Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst. 2(4), 303\u2013314 (1989)","journal-title":"Math. Control Signals Syst."},{"key":"2016_CR11","doi-asserted-by":"publisher","first-page":"6696","DOI":"10.1109\/TSP.2020.3039360","volume":"68","author":"SS Dey","year":"2020","unstructured":"Dey, S.S., Wang, G., Xie, Y.: Approximation algorithms for training one-node relu neural networks. IEEE Trans. Signal Process 68, 6696\u20136706 (2020)","journal-title":"IEEE Trans. Signal Process"},{"key":"2016_CR12","unstructured":"Eldan, R., Shamir, O.: The power of depth for feedforward neural networks. In: 29th Annual Conference on Learning Theory, pp. 907\u2013940 (2016)"},{"key":"2016_CR13","doi-asserted-by":"crossref","unstructured":"Froese, V., Hertrich, C., Niedermeier, R.: The computational complexity of ReLU network training parameterized by data dimensionality. arXiv preprint arXiv:2105.08675 (2021)","DOI":"10.1613\/jair.1.13547"},{"key":"2016_CR14","doi-asserted-by":"publisher","first-page":"1775","DOI":"10.1613\/jair.1.13547","volume":"74","author":"V Froese","year":"2022","unstructured":"Froese, V., Hertrich, C., Niedermeier, R.: The computational complexity of relu network training parameterized by data dimensionality. J. Artif. Intell. Res. 74, 1775\u20131790 (2022)","journal-title":"J. Artif. Intell. Res."},{"key":"2016_CR15","unstructured":"Goel, S., Kanade, V., Klivans, A., Thaler, J.: Reliably learning the relu in polynomial time. In: Conference on Learning Theory, pp. 1004\u20131042. PMLR (2017)"},{"key":"2016_CR16","unstructured":"Goel, S., Klivans, A., Manurangsi, P., Reichman, D.: Tight hardness results for training depth-2 relu networks. arXiv preprint arXiv:2011.13550 (2020)"},{"key":"2016_CR17","unstructured":"Goel, S., Klivans, A., Meka, R.: Learning one convolutional layer with overlapping patches. In: International Conference on Machine Learning, pp. 1783\u20131791. PMLR (2018)"},{"key":"2016_CR18","unstructured":"Goel, S., Klivans, A.R.: Learning neural networks with two nonlinear layers in polynomial time. In: Conference on Learning Theory, pp. 1470\u20131499. PMLR (2019)"},{"key":"2016_CR19","unstructured":"Goel, S., Klivans, A.R., Manurangsi, P., Reichman, D.: Tight hardness results for training depth-2 ReLU networks. In: 12th Innovations in Theoretical Computer Science Conference (ITCS\u00a0\u201921), LIPIcs, vol. 185, pp. 22:1\u201322:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"2016_CR20","doi-asserted-by":"crossref","unstructured":"He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770\u2013778 (2016)","DOI":"10.1109\/CVPR.2016.90"},{"key":"2016_CR21","unstructured":"Hertrich, C., Basu, A., Di\u00a0Summa, M., Skutella, M.: Towards lower bounds on the depth of relu neural networks. To appear in NeurIPS 2021 (arXiv preprint arXiv:2105.14835) (2021)"},{"issue":"1","key":"2016_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1006\/jcss.1995.1011","volume":"50","author":"KU Hoffgen","year":"1995","unstructured":"Hoffgen, K.U., Simon, H.U., Vanhorn, K.S.: Robust trainability of single neurons. J. Comput. Syst. Sci. 50(1), 114\u2013125 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2016_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0893-6080(91)90009-T","volume":"4","author":"K Hornik","year":"1991","unstructured":"Hornik, K.: Approximation capabilities of multilayer feedforward networks. Neural Netw. 4(2), 251\u2013257 (1991)","journal-title":"Neural Netw."},{"issue":"3","key":"2016_CR24","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/S0097539792282965","volume":"26","author":"R Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Paturi, R., Saks, M.E.: Size-depth tradeoffs for threshold circuits. SIAM J. Comput. 26(3), 693\u2013707 (1997)","journal-title":"SIAM J. Comput."},{"key":"2016_CR25","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Williams, R.: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 633\u2013643 (2016)","DOI":"10.1145\/2897518.2897636"},{"key":"2016_CR26","unstructured":"Manurangsi, P., Reichman, D.: The computational complexity of training relu (s). arXiv preprint arXiv:1810.04207 (2018)"},{"key":"2016_CR27","unstructured":"Matousek, J.: Lectures on discrete geometry, vol. 212. Springer Science & Business Media (2013)"},{"key":"2016_CR28","unstructured":"MUROGA, S.: Threshold logic and its application. Wiley-Interscience (1971)"},{"issue":"2","key":"2016_CR29","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/inco.1994.1059","volume":"112","author":"R Paturi","year":"1994","unstructured":"Paturi, R., Saks, M.E.: Approximating threshold circuits by rational functions. Inf. Comput. 112(2), 257\u2013272 (1994)","journal-title":"Inf. Comput."},{"key":"2016_CR30","unstructured":"Telgarsky, M.: Benefits of depth in neural networks. In: Conference on learning theory, pp. 1517\u20131539. PMLR (2016)"},{"key":"2016_CR31","unstructured":"Wachs, M.L.: Poset topology: tools and applications. arXiv preprint math\/0602226 (2006)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02016-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02016-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02016-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:21:48Z","timestamp":1721823708000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02016-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,12]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2016"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02016-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,12]]},"assertion":[{"value":"13 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}