{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:25Z","timestamp":1781031445713,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":57,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800825","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1133-1144","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Constructive Approximation under Carleman\u2019s Condition, with Applications to Smoothed Analysis"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5220-9680","authenticated-orcid":false,"given":"Frederic","family":"Koehler","sequence":"first","affiliation":[{"name":"University of Chicago, Department of Statistics and Data Science Institute, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1981-0890","authenticated-orcid":false,"given":"Beining","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Chicago, Department of Statistics, Chicago, 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.1137\/1.9781611976397"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801334"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1010"},{"key":"e_1_3_2_1_4_1","unstructured":"Pierre Bizeul and Boaz Klartag. 2025. Polynomial Approximation in L^2 of the Double Exponential via Complex Analysis. arXiv preprint arXiv:2502.07448."},{"key":"e_1_3_2_1_5_1","unstructured":"Avrim Blum and John Dunagan. 2002. Smoothed analysis of the perceptron algorithm for linear programming. 905\u2013914. isbn:089871513X"},{"key":"e_1_3_2_1_6_1","unstructured":"Torsten Carleman. 1926. Les Fonctions quasi analytiques: le\u00e7ons profess\u00e9es au College de France. Gauthier-Villars."},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"922","author":"Chandrasekaran Gautam","year":"2024","unstructured":"Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, and Konstantinos Stavropoulos. 2024. Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 876\u2013922. https:\/\/proceedings.mlr.press\/v247\/chandrasekaran24a.html"},{"key":"e_1_3_2_1_8_1","volume-title":"Lin Lin Lee, and Konstantinos Stavropoulos","author":"Chandrasekaran Gautam","year":"2025","unstructured":"Gautam Chandrasekaran, Adam R. Klivans, Lin Lin Lee, and Konstantinos Stavropoulos. 2025. Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees. https:\/\/openreview.net\/forum?id=ed7zI29lRF"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722163"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory, Mikhail Belkin and Samory Kpotufe (Eds.) (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 Proceedings of Thirty Fourth Conference on Learning Theory, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1358\u20131394. https:\/\/proceedings.mlr.press\/v134\/daniely21a.html"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176343850"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-018-9384-1"},{"key":"e_1_3_2_1_14_1","unstructured":"R.A. DeVore and G.G. Lorentz. 1993. Constructive Approximation. Springer Berlin Heidelberg. isbn:9783540506270 lccn:lc93018420 https:\/\/books.google.com\/books?id=cDqNW6k7_ZwC"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348901"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0125-7"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of Thirty Fifth Conference on Learning Theory, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research","volume":"4282","author":"Diakonikolas Ilias","year":"2022","unstructured":"Ilias Diakonikolas and Daniel Kane. 2022. Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. In Proceedings of Thirty Fifth Conference on Learning Theory, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research, Vol. 178). PMLR, 4258\u20134282. https:\/\/proceedings.mlr.press\/v178\/diakonikolas22b.html"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0262"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-0184"},{"key":"e_1_3_2_1_20_1","volume-title":"Kane","author":"Diakonikolas Ilias","year":"2023","unstructured":"Ilias Diakonikolas and Daniel M. Kane. 2023. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, Cambridge."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research","volume":"1584","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, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1552\u20131584. https:\/\/proceedings.mlr.press\/v134\/diakonikolas21c.html"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00063"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01903375"},{"key":"e_1_3_2_1_25_1","series-title":"SIAM journal on scientific and statistical computing, 11, 1","volume-title":"Analytic continuation by the fast Fourier transform","author":"Franklin Joel","year":"1990","unstructured":"Joel Franklin. 1990. Analytic continuation by the fast Fourier transform. SIAM journal on scientific and statistical computing, 11, 1 (1990), 112\u2013122."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(77)90026-0"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1978-032-7"},{"key":"e_1_3_2_1_28_1","volume-title":"From boltzmann machines to neural networks and back again. Advances in neural information processing systems, 33","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel, Adam Klivans, and Frederic Koehler. 2020. From boltzmann machines to neural networks and back again. Advances in neural information processing systems, 33 (2020), 6354\u20136365."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the Thirty-Second Conference on Learning Theory, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research","volume":"1499","author":"Goel Surbhi","unstructured":"Surbhi Goel and Adam R. Klivans. 2019. Learning Neural Networks with Two Nonlinear Layers in Polynomial Time. In Proceedings of the Thirty-Second Conference on Learning Theory, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 1470\u20131499. https:\/\/proceedings.mlr.press\/v99\/goel19b.html"},{"key":"e_1_3_2_1_30_1","unstructured":"Aravind Gollakota Sushrut Karmalkar and Adam Klivans. 2020. The polynomial method is universal for distribution-free correlational SQ learning. arXiv preprint arXiv:2010.11925."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585206"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21901"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350697"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/23-AOS2309"},{"key":"e_1_3_2_1_35_1","volume-title":"The Analysis of Linear Partial Differential Operators I: Distribution theory and Fourier analysis","author":"H\u00f6rmander L.","unstructured":"L. H\u00f6rmander. 1983. The Analysis of Linear Partial Differential Operators I: Distribution theory and Fourier analysis. Springer-Verlag. isbn:9783540121046 lccn:lc83000616 https:\/\/books.google.com\/books?id=JmEPAQAAMAAJ"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1127062"},{"key":"e_1_3_2_1_37_1","first-page":"229","article-title":"Answer to a problem of Paul Tur\u00e1n. In Annales","volume":"31","author":"Jo\u00f3 I","year":"1988","unstructured":"I Jo\u00f3 and NX Ky. 1988. Answer to a problem of Paul Tur\u00e1n. In Annales Univ. Sci. Budapest., Sectio Math. 31, 229\u2013241.","journal-title":"Univ. Sci. Budapest., Sectio Math."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2014.793"},{"key":"e_1_3_2_1_40_1","volume-title":"Klivans and Raghu Meka","author":"Adam","year":"2013","unstructured":"Adam R. Klivans and Raghu Meka. 2013. Moment-Matching Polynomials. Electron. Colloquium Comput. Complex., TR13 (2013), https:\/\/api.semanticscholar.org\/CorpusID:11341444"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.008"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2505.20177"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771783"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773956"},{"key":"e_1_3_2_1_45_1","first-page":"1","article-title":"A survey of weighted polynomial approximation with exponential weights","volume":"3","author":"Lubinsky D. S.","year":"2007","unstructured":"D. S. Lubinsky. 2007. A survey of weighted polynomial approximation with exponential weights. Surv. Approx. Theory, 3 (2007), 1\u2013105. issn:1555-578X","journal-title":"Surv. Approx. Theory"},{"key":"e_1_3_2_1_46_1","first-page":"1","article-title":"De la Vall\u00e9e Poussin means and Jackson\u2019s theorem","volume":"74","author":"Mastroianni G","year":"2008","unstructured":"G Mastroianni, Woula Themistoclakis, et al. 2008. De la Vall\u00e9e Poussin means and Jackson\u2019s theorem. Acta Scientiarum Mathematicarum, 74, 1-2 (2008), 147\u2013170.","journal-title":"Acta Scientiarum Mathematicarum"},{"key":"e_1_3_2_1_47_1","volume-title":"Local estimates for exponential polynomials and their applications to inequalities of the uncertainty principle type. Algebra i analiz, 5, 4","author":"Nazarov Fedor L\u2019vovich","year":"1993","unstructured":"Fedor L\u2019vovich Nazarov. 1993. Local estimates for exponential polynomials and their applications to inequalities of the uncertainty principle type. Algebra i analiz, 5, 4 (1993), 3\u201366."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_1_49_1","volume-title":"The methods of distances in the theory of probability and statistics. 10","author":"Rachev Svetlozar T","unstructured":"Svetlozar T Rachev, Lev B Klebanov, Stoyan V Stoyanov, and Frank Fabozzi. 2013. The methods of distances in the theory of probability and statistics. 10, Springer."},{"key":"e_1_3_2_1_50_1","volume-title":"Real and Complex Analysis","author":"Rudin Walter","unstructured":"Walter Rudin. 1987. Real and Complex Analysis (3rd ed.). McGraw-Hill, New York.","edition":"3"},{"key":"e_1_3_2_1_51_1","volume-title":"On the cryptographic hardness of learning single periodic neurons. Advances in neural information processing systems, 34","author":"Song Min Jae","year":"2021","unstructured":"Min Jae Song, Ilias Zadik, and Joan Bruna. 2021. On the cryptographic hardness of learning single periodic neurons. Advances in neural information processing systems, 34 (2021), 29602\u201329615."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_53_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research","volume":"3064","author":"Tiegel Stefan","year":"2023","unstructured":"Stefan Tiegel. 2023. Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems. In Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, 3029\u20133064. https:\/\/proceedings.mlr.press\/v195\/tiegel23a.html"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-020-00802-7"},{"key":"e_1_3_2_1_55_1","volume-title":"Topological Vector Spaces, Distributions and Kernels: Pure and Applied Mathematics","author":"Treves Fran\u00e7ois","unstructured":"Fran\u00e7ois Treves. 2016. Topological Vector Spaces, Distributions and Kernels: Pure and Applied Mathematics, Vol. 25. 25, Elsevier."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-79052-7_1"},{"key":"e_1_3_2_1_57_1","volume-title":"High-dimensional probability: An introduction with applications in data science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. 47, Cambridge university press."}],"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.3800825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:20Z","timestamp":1781028140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":57,"alternative-id":["10.1145\/3798129.3800825","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800825","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"}}]}}