{"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":1781031413447,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"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":"National Science Foundation","doi-asserted-by":"publisher","award":["2238221"],"award-info":[{"award-number":["2238221"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["2106429"],"award-info":[{"award-number":["2106429"]}]},{"name":"National Science Foundation","award":["2107187"],"award-info":[{"award-number":["2107187"]}]},{"name":"National Science Foundation","award":["2218677"],"award-info":[{"award-number":["2218677"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["13533312"],"award-info":[{"award-number":["13533312"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["2106429"],"award-info":[{"award-number":["2106429"]}]},{"name":"National Science Foundation","award":["2211238"],"award-info":[{"award-number":["2211238"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800866","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1581-1591","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning Functions of Halfspaces"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2204-1359","authenticated-orcid":false,"given":"Josh","family":"Alman","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9174-9139","authenticated-orcid":false,"given":"Shyamal","family":"Patel","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"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.1016\/j.jcss.2007.04.011"},{"key":"e_1_3_2_1_2_1","unstructured":"Maria-Florina Balcan and Hongyang Zhang. 2017. Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions. In Advances in Neural Information Processing Systems 30 (NeurIPS). 4796\u20134805."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(90)90012-3"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90237-P"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1475"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80010-3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_8_1","volume-title":"On the Complexity of PAC Learning in Hilbert Spaces. In Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 7202\u20137209","author":"Chubanov Sergei","year":"2023","unstructured":"Sergei Chubanov. 2023. On the Complexity of PAC Learning in Hilbert Spaces. In Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 7202\u20137209."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 29th Conference on Learning Theory (COLT) (JMLR Workshop and Conference Proceedings","volume":"830","author":"Daniely Amit","year":"2016","unstructured":"Amit Daniely and Shai Shalev-Shwartz. 2016. Complexity Theoretic Limitations on Learning DNF\u2019s. In Proceedings of the 29th Conference on Learning Theory (COLT) (JMLR Workshop and Conference Proceedings, Vol. 49). JMLR.org, 815\u2013830."},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","volume":"1394","author":"Daniely Amit","year":"2021","unstructured":"Amit Daniely and Gal Vardi. 2021. From Local Pseudorandom Generators to Hardness of Learning. In Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1358\u20131394."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory. 1552\u20131584","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. 2021. The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model. In Proceedings of Thirty Fourth Conference on Learning Theory. 1552\u20131584."},{"key":"e_1_3_2_1_12_1","volume-title":"The Thirty Eighth Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","volume":"1530","author":"Diakonikolas Ilias","year":"2025","unstructured":"Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos. 2025. Learning Intersections of Two Margin Halfspaces under Factorizable Distributions. In The Thirty Eighth Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 291). PMLR, 1472\u20131530."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585191"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104771"},{"key":"e_1_3_2_1_15_1","unstructured":"R. O. Duda and P. E. Hart. 1973. Pattern Classification and Scene Analysis. Wiley."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1136"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_1_18_1","volume-title":"Klivans","author":"Gollakota Aravind","year":"2020","unstructured":"Aravind Gollakota, Sushrut Karmalkar, and Adam R. Klivans. 2020. The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning. CoRR, abs\/2010.11925 (2020)."},{"key":"e_1_3_2_1_19_1","volume-title":"The 25th Annual Conference on Learning Theory (COLT) (JMLR Proceedings","volume":"15","author":"Gopalan Parikshit","year":"2012","unstructured":"Parikshit Gopalan, Adam R. Klivans, and Raghu Meka. 2012. Learning Functions of Halfspaces using Prefix Covers. In The 25th Annual Conference on Learning Theory (COLT) (JMLR Proceedings, Vol. 23). JMLR.org, 15.1\u201315.10."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3134898"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.018"},{"key":"e_1_3_2_1_22_1","volume-title":"Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. In Conference on Learning Theory (COLT). 283\u2013312","author":"Hsu Daniel J.","year":"2022","unstructured":"Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, and Emmanouil-Vasileios Vlatakis-Gkaragkounis. 2022. Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. In Conference on Learning Theory (COLT). 283\u2013312."},{"key":"e_1_3_2_1_23_1","unstructured":"Tony Huynh. 2020. Answer to \u201cVC dimension of vector spaces\u201d on mathoverflow. October available at https:\/\/mathoverflow.net\/questions\/373929\/vc-dimension-of-vector-spaces"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"M. Kearns and U. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.010"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.002"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_28_1","volume-title":"Log-Concave Distributions. In Proceedings of 13th International Workshop, RANDOM (Lecture Notes in Computer Science","volume":"600","author":"Klivans Adam R.","unstructured":"Adam R. Klivans, Philip M. Long, and Alex K. Tang. 2009. Baum\u2019s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions. In Proceedings of 13th International Workshop, RANDOM (Lecture Notes in Computer Science, Vol. 5687). Springer, 588\u2013600."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.012"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5010-1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_3_2_1_32_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","author":"Klivans Adam R.","unstructured":"Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2024. Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds. In The Thirty Seventh Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 2944\u20132978."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013834"},{"key":"e_1_3_2_1_34_1","unstructured":"Troy Lee. 2009. A note on the sign-degree of formulas. Available at https:\/\/arxiv.org\/abs\/0909.4607"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the Symposium on Mathematical Theory of Automata. XII, 615\u2013622","author":"Novikoff A.","year":"1962","unstructured":"A. Novikoff. 1962. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata. XII, 615\u2013622."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0042519"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"e_1_3_2_1_39_1","volume-title":"Understanding Machine Learning - From Theory to Algorithms","author":"Shalev-Shwartz Shai","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press. http:\/\/www.cambridge.org\/de\/academic\/subjects\/computer-science\/pattern-recognition-and-machine-learning\/understanding-machine-learning-theory-algorithms"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/100785260"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2759-7"},{"key":"e_1_3_2_1_42_1","volume-title":"The hardest halfspace. computational complexity, 30, 2","author":"Sherstov Alexander A","year":"2021","unstructured":"Alexander A Sherstov. 2021. The hardest halfspace. computational complexity, 30, 2 (2021), 11."},{"key":"e_1_3_2_1_43_1","volume-title":"Improved Hardness Results for Learning Intersections of Halfspaces. In The Thirty Seventh Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","volume":"4786","author":"Tiegel Stefan","year":"2024","unstructured":"Stefan Tiegel. 2024. Improved Hardness Results for Learning Intersections of Halfspaces. In The Thirty Seventh Annual Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 4764\u20134786."},{"key":"e_1_3_2_1_44_1","volume-title":"Estimations of dependences based on statistical data","author":"Vapnik V.","unstructured":"V. Vapnik. 1982. Estimations of dependences based on statistical data. Springer."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.19"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857916"}],"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.3800866","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:14Z","timestamp":1781027894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":46,"alternative-id":["10.1145\/3798129.3800866","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800866","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"}}]}}