{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:08Z","timestamp":1781031428745,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":51,"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":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2505865"],"award-info":[{"award-number":["CCF-2505865"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800889","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1824-1835","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2443-8675","authenticated-orcid":false,"given":"Gautam","family":"Chandrasekaran","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6960-2235","authenticated-orcid":false,"given":"Adam R.","family":"Klivans","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2643-4298","authenticated-orcid":false,"given":"Konstantinos","family":"Stavropoulos","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0672-0386","authenticated-orcid":false,"given":"Arsen","family":"Vasilyan","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"K Warmuth","author":"Auer Peter","year":"1995","unstructured":"Peter Auer, Mark Herbster, and Manfred K. K Warmuth. 1995. Exponentially many local minima for single neurons. In Advances in Neural Information Processing Systems, D. Touretzky, M.C. Mozer, and M. Hasselmo (Eds.). 8, MIT Press. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/1995\/file\/3806734b256c27e41ec2c6bffa26d9e7-Paper.pdf"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research","volume":"190","author":"Awasthi Pranjal","year":"2015","unstructured":"Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. 2015. Efficient Learning of Linear Separators under Bounded Noise. In Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research, Vol. 40). PMLR, Paris, France. 167\u2013190. https:\/\/proceedings.mlr.press\/v40\/Awasthi15b.html"},{"key":"e_1_3_2_1_3_1","volume-title":"29th Annual Conference on Learning Theory, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research","volume":"192","author":"Awasthi Pranjal","year":"2016","unstructured":"Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. 2016. Learning and 1-bit Compressed Sensing under Asymmetric Noise. In 29th Annual Conference on Learning Theory, Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research, Vol. 49). PMLR, Columbia University, New York, USA. 152\u2013192. http:\/\/proceedings.mlr.press\/v49\/awasthi16.html"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3006384"},{"key":"e_1_3_2_1_5_1","volume-title":"Agnostic Learning of General ReLU Activation Using Gradient Descent. In The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=EnrY5TOrbQ","author":"Awasthi Pranjal","year":"2023","unstructured":"Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. 2023. Agnostic Learning of General ReLU Activation Using Gradient Descent. In The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=EnrY5TOrbQ"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718193"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00403-0"},{"key":"e_1_3_2_1_8_1","unstructured":"Gautam Chandrasekaran Adam R. Klivans Konstantinos Stavropoulos and Arsen Vasilyan. 2025. A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube. arxiv:2511.07244. arxiv:2511.07244"},{"key":"e_1_3_2_1_9_1","first-page":"8391","article-title":"Classification under misspecification: Halfspaces, generalized linear models, and evolvability","volume":"33","author":"Chen Sitan","year":"2020","unstructured":"Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. 2020. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. Advances in Neural Information Processing Systems, 33 (2020), 8391\u20138403.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.34"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research","volume":"502","author":"Daniely Amit","year":"2015","unstructured":"Amit Daniely. 2015. A PTAS for Agnostically Learning Halfspaces. In Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research, Vol. 40). PMLR, Paris, France. 484\u2013502. https:\/\/proceedings.mlr.press\/v40\/Daniely15.html"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590772"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of Thirty Third Conference on Learning Theory, Jacob Abernethy and Shivani Agarwal (Eds.) (Proceedings of Machine Learning Research","volume":"1485","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, and Mahdi Soltanolkotabi. 2020. Approximation Schemes for ReLU Regression. In Proceedings of Thirty Third Conference on Learning Theory, Jacob Abernethy and Shivani Agarwal (Eds.) (Proceedings of Machine Learning Research, Vol. 125). PMLR, 1452\u20131485. http:\/\/proceedings.mlr.press\/v125\/diakonikolas20b.html"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.) (Proceedings of Machine Learning Research","volume":"8213","author":"Diakonikolas Ilias","year":"2022","unstructured":"Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. 2022. Hardness of Learning a Single Neuron with Adversarial Label Noise. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.) (Proceedings of Machine Learning Research, Vol. 151). PMLR, 8199\u20138213. https:\/\/proceedings.mlr.press\/v151\/diakonikolas22a.html"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316301"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649776"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 34th Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"1551","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2021. Agnostic Proper Learning of Halfspaces under Gaussian Marginals. In Proceedings of the 34th Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1522\u20131551. http:\/\/proceedings.mlr.press\/v134\/diakonikolas21b.html"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188754"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of Thirty Third Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"1513","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2020. Learning halfspaces with Massart noise under structured distributions. In Proceedings of Thirty Third Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 125). PMLR, 1486\u20131513. http:\/\/proceedings.mlr.press\/v125\/diakonikolas20c.html"},{"key":"e_1_3_2_1_21_1","first-page":"18540","article-title":"Non-convex SGD learns halfspaces with adversarial label noise","volume":"33","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2020. Non-convex SGD learns halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 33 (2020), 18540\u201318549.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_22_1","volume-title":"Conference on learning theory. 4313\u20134361","author":"Diakonikolas Ilias","year":"2022","unstructured":"Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2022. Learning a single neuron with adversarial label noise via gradient descent. In Conference on learning theory. 4313\u20134361."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Ilias Diakonikolas and Nikos Zarifis. 2024. A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems NeurIPS Amir Globersons Lester Mackey Danielle Belgrave Angela Fan Ulrich Paquet Jakub M. Tomczak and Cheng Zhang (Eds.).","DOI":"10.52202\/079017-2811"},{"key":"e_1_3_2_1_24_1","volume-title":"An introduction to generalized linear models","author":"Dobson Annette J","unstructured":"Annette J Dobson and Adrian G Barnett. 2018. An introduction to generalized linear models. Chapman and Hall\/CRC."},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 31st Conference On Learning Theory, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research","volume":"1930","author":"Dudeja Rishabh","year":"2018","unstructured":"Rishabh Dudeja and Daniel Hsu. 2018. Learning Single-Index Models in Gaussian Space. In Proceedings of the 31st Conference On Learning Theory, S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.) (Proceedings of Machine Learning Research, Vol. 75). PMLR, 1887\u20131930. https:\/\/proceedings.mlr.press\/v75\/dudeja18a.html"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-3969"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-0646"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research","volume":"2631","author":"Guo Anxin","year":"2025","unstructured":"Anxin Guo and Aravindan Vijayaraghavan. 2025. Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals. In Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research, Vol. 291). PMLR, 2592\u20132631. https:\/\/proceedings.mlr.press\/v291\/guo25a.html"},{"key":"e_1_3_2_1_30_1","volume-title":"Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24","author":"Kakade Sham M","year":"2011","unstructured":"Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. 2011. Efficient learning of generalized linear and single index models with isotonic regression. Advances in Neural Information Processing Systems, 24 (2011)."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_32_1","first-page":"9","article-title":"The Isotron Algorithm: High-Dimensional Isotonic Regression","volume":"1","author":"Kalai Adam Tauman","year":"2009","unstructured":"Adam Tauman Kalai and Ravi Sastry. 2009. The Isotron Algorithm: High-Dimensional Isotonic Regression.. In COLT. 1, 9.","journal-title":"COLT."},{"key":"e_1_3_2_1_33_1","unstructured":"Varun Kanade. 2018. Lecture notes: Learning real-valued functions."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research","volume":"3263","author":"Klivans Adam","year":"2025","unstructured":"Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2025. Learning Constant-Depth Circuits in Malicious Noise Models. In Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research, Vol. 291). PMLR, 3253\u20133263. https:\/\/proceedings.mlr.press\/v291\/klivans25a.html"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_51"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the Thirty-Second Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"2293","author":"Mangoubi Oren","unstructured":"Oren Mangoubi and Nisheeth K. Vishnoi. 2019. Nonconvex sampling with the Metropolis-adjusted Langevin algorithm. In Proceedings of the Thirty-Second Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 99). PMLR, 2259\u20132293. http:\/\/proceedings.mlr.press\/v99\/mangoubi19a.html"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2307\/2344614"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374450"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research","volume":"4837","author":"Rohatgi Dhruv","unstructured":"Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster. 2025. Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification (extended abstract). In Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research, Vol. 291). PMLR, 4831\u20134837. https:\/\/proceedings.mlr.press\/v291\/rohatgi25a.html"},{"key":"e_1_3_2_1_42_1","volume-title":"The perceptron: a probabilistic model for information storage and organization in the brain.. Psychological review, 65, 6","author":"Rosenblatt Frank","year":"1958","unstructured":"Frank Rosenblatt. 1958. The perceptron: a probabilistic model for information storage and organization in the brain.. Psychological review, 65, 6 (1958), 386."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.18"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/100806126"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857916"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"36577","author":"Wang Puqian","year":"2023","unstructured":"Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. 2023. Robustly Learning a Single Neuron via Sharpness. In Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202). PMLR, 36541\u201336577. http:\/\/proceedings.mlr.press\/v202\/wang23aq.html"},{"key":"e_1_3_2_1_47_1","first-page":"58376","article-title":"Sample and computationally efficient robust learning of gaussian single-index models","volume":"37","author":"Wang Puqian","year":"2024","unstructured":"Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. 2024. Sample and computationally efficient robust learning of gaussian single-index models. Advances in Neural Information Processing Systems, 37 (2024), 58376\u201358422.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_48_1","volume-title":"Robustly Learning Monotone Single-Index Models. ArXiv, abs\/2508.04670","author":"Wang Puqian","year":"2025","unstructured":"Puqian Wang, Nikos Zarifis, Ilias Diakonikolas, and Jelena Diakonikolas. 2025. Robustly Learning Monotone Single-Index Models. ArXiv, abs\/2508.04670 (2025), https:\/\/api.semanticscholar.org\/CorpusID:280536509"},{"key":"e_1_3_2_1_49_1","volume-title":"Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30","author":"Yan Songbai","year":"2017","unstructured":"Songbai Yan and Chicheng Zhang. 2017. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30 (2017)."},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 41st International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"58243","author":"Zarifis Nikos","year":"2024","unstructured":"Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. 2024. Robustly Learning Single-Index Models via Alignment Sharpness. In Proceedings of the 41st International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 235). PMLR, 58197\u201358243. http:\/\/proceedings.mlr.press\/v235\/zarifis24a.html"},{"key":"e_1_3_2_1_51_1","volume-title":"Conference on Learning Theory. 1980\u20132022","author":"Zhang Yuchen","year":"2017","unstructured":"Yuchen Zhang, Percy Liang, and Moses Charikar. 2017. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory. 1980\u20132022."}],"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.3800889","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800889","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:38Z","timestamp":1781028038000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800889"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":51,"alternative-id":["10.1145\/3798129.3800889","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800889","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"}}]}}