{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:11Z","timestamp":1781078291030,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["s CCF-1910534, CCF-1926872, CCF-204512, CCF-1934876, CCF-200830, IIS-1838154, CCF-2106429, CCF-2211238, CCF-1763970, CCF-210718,"],"award-info":[{"award-number":["s CCF-1910534, CCF-1926872, CCF-204512, CCF-1934876, CCF-200830, IIS-1838154, CCF-2106429, CCF-2211238, CCF-1763970, CCF-210718,"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649633","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1027-1038","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Detecting Low-Degree Truncation"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6795-8211","authenticated-orcid":false,"given":"Anindya","family":"De","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7840-1053","authenticated-orcid":false,"given":"Huan","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-6122","authenticated-orcid":false,"given":"Shivam","family":"Nadimpalli","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":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Special functions. 71","author":"Andrews George E","unstructured":"George E Andrews, Richard Askey, and Ranjan Roy. 1999. Special functions. 71, Cambridge University Press, Cambridge."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/surv"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536481"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1334-5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1257792"},{"key":"e_1_3_2_1_7_1","volume-title":"Active Learning Polynomial Threshold Functions. CoRR, abs\/2201.09433","author":"Ben-Eliezer Omri","year":"2022","unstructured":"Omri Ben-Eliezer, Max Hopkins, Chutong Yang, and Hantao Yu. 2022. Active Learning Polynomial Threshold Functions. CoRR, abs\/2201.09433 (2022), arxiv:2201.09433"},{"key":"e_1_3_2_1_8_1","volume-title":"International Conference on Artificial Intelligence and Statistics. 1450\u20131458","author":"Bhattacharyya Arnab","year":"2021","unstructured":"Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas. 2021. Efficient statistics for sparse graphical models from truncated samples. In International Conference on Artificial Intelligence and Statistics. 1450\u20131458."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.2007.v14.n3.a11"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00532234"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(76)90184-5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(76)90004-5"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221003"},{"key":"e_1_3_2_1_14_1","volume-title":"Servedio","author":"Canonne Cl\u00e9ment L.","year":"2020","unstructured":"Cl\u00e9ment L. Canonne, Anindya De, and Rocco A. Servedio. 2020. Learning from satisfying assignments under continuous distributions. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), Shuchi Chawla (Ed.). SIAM, 82\u2013101."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-02-11331-3"},{"key":"e_1_3_2_1_16_1","volume-title":"Truncated and censored samples: theory and applications","author":"Cohen A. Clifford","unstructured":"A. Clifford Cohen. 2016. Truncated and censored samples: theory and applications. CRC Press."},{"key":"e_1_3_2_1_17_1","volume-title":"A course in functional analysis. 96","author":"Conway John B","unstructured":"John B Conway. 2019. A course in functional analysis. 96, Springer."},{"key":"e_1_3_2_1_18_1","volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Daskalakis C.","year":"2018","unstructured":"C. Daskalakis, T. Gouleakis, C. Tzamos, and M. Zampetakis. 2018. Efficient Statistics, in High Dimensions, from Truncated Samples. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018. IEEE Computer Society, 639\u2013649."},{"key":"e_1_3_2_1_19_1","volume-title":"Computationally and Statistically Efficient Truncated Regression. In Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","volume":"960","author":"Daskalakis Constantinos","year":"2019","unstructured":"Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. 2019. Computationally and Statistically Efficient Truncated Regression. In Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 99). 955\u2013960."},{"key":"e_1_3_2_1_20_1","first-page":"10338","article-title":"Truncated linear regression in high dimensions","volume":"33","author":"Daskalakis C.","year":"2020","unstructured":"C. Daskalakis, D. Rohatgi, and E. Zampetakis. 2020. Truncated linear regression in high dimensions. Advances in Neural Information Processing Systems, 33 (2020), 10338\u201310347.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_21_1","first-page":"1952","article-title":"Efficient truncated linear regression with unknown noise variance","volume":"34","author":"Daskalakis C.","year":"2021","unstructured":"C. Daskalakis, P. Stefanou, R. Yao, and E. Zampetakis. 2021. Efficient truncated linear regression with unknown noise variance. Advances in Neural Information Processing Systems, 34 (2021), 1952\u20131963.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 29th Annual Conference on Computational Complexity (CCC). 229\u2013240","author":"De Anindya","unstructured":"Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. 2014. Deterministic approximate counting for juntas of degree-2 polynomial threshold functions. In Proceedings of the 29th Annual Conference on Computational Complexity (CCC). 229\u2013240."},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"De A.","year":"2015","unstructured":"A. De, I. Diakonikolas, and R. A. Servedio. 2015. Learning from satisfying assignments. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. 478\u2013497."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.69"},{"key":"e_1_3_2_1_25_1","volume-title":"Convex Influences. In 13th Innovations in Theoretical Computer Science Conference, ITCS, Mark Braverman (Ed.) (LIPIcs","volume":"21","author":"De Anindya","unstructured":"Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. 2022. Convex Influences. In 13th Innovations in Theoretical Computer Science Conference, ITCS, Mark Braverman (Ed.) (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 53:1\u201353:21."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch155"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 46th Annual Symposium on Theory of Computing (STOC). 832\u2013841","author":"De Anindya","unstructured":"Anindya De and Rocco A. Servedio. 2014. Efficient deterministic approximate counting for low-degree polynomial threshold functions. In Proceedings of the 46th Annual Symposium on Theory of Computing (STOC). 832\u2013841."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.007"},{"key":"e_1_3_2_1_29_1","volume-title":"The total variation distance between high-dimensional Gaussians. arXiv:1810.08693v5","author":"Devroye Luc","year":"2020","unstructured":"Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2020. The total variation distance between high-dimensional Gaussians. arXiv:1810.08693v5, 22 May 2020"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.8"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2210.13706"},{"key":"e_1_3_2_1_32_1","volume-title":"Conference on Learning Theory, COLT 2021","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 Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1552\u20131584."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas R. O\u2019Donnell R. Servedio and Y. Wu. 2011. Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. In SODA. 1590\u20131606.","DOI":"10.1137\/1.9781611973082.123"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855223"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132580"},{"key":"e_1_3_2_1_36_1","unstructured":"R.A. Fisher. 1931. Properties and applications of HH functions. In Mathematical tables. 815\u2013852."},{"key":"e_1_3_2_1_37_1","volume-title":"Efficient Parameter Estimation of Truncated Boolean Product Distributions. In Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research","volume":"1600","author":"Fotakis Dimitris","year":"2020","unstructured":"Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. 2020. Efficient Parameter Estimation of Truncated Boolean Product Distributions. In Conference on Learning Theory (COLT) (Proceedings of Machine Learning Research, Vol. 125). 1586\u20131600."},{"key":"e_1_3_2_1_38_1","first-page":"379","article-title":"An examination into the registered speeds of American trotting horses, with remarks on their value as hereditary data","volume":"62","author":"Galton Francis","year":"1897","unstructured":"Francis Galton. 1897. An examination into the registered speeds of American trotting horses, with remarks on their value as hereditary data. Proceedings of the Royal Society of London, 62, 379-387 (1897), 310\u2013315.","journal-title":"Proceedings of the Royal Society of London"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305949"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1525\/9780520350670-010"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a001"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Wassily Hoeffding. 1994. A Class of Statistics with Asymptotically Normal Distribution. The Collected Works of Wassily Hoeffding 171\u2013204.","DOI":"10.1007\/978-1-4612-0865-5_8"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-97-01766-2"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055470"},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM). 116","author":"Kabanets Valentine","year":"2018","unstructured":"Valentine Kabanets and Zhenjian Lu. 2018. Satisfiability and Derandomization for Small Polynomial Threshold Circuits. In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM). 116, 46:1\u201346:19."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.13"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.16"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.52"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.30"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3235586.3235588"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.15"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0086-z"},{"key":"e_1_3_2_1_53_1","volume-title":"30th Conference on Computational Complexity, CCC 2015","author":"Kane D. M.","year":"2015","unstructured":"D. M. Kane. 2015. A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA. 567\u2013581."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488610"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00093"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/2331782"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811623"},{"key":"e_1_3_2_1_58_1","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan","unstructured":"Ryan O\u2019Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press. isbn:978-1-10-703832-5 http:\/\/www.cambridge.org\/de\/academic\/subjects\/computer-science\/algorithmics-complexity-computer-algebra-and-computational-g\/analysis-boolean-functions"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384281"},{"key":"e_1_3_2_1_60_1","first-page":"2","article-title":"On the systematic fitting of frequency curves","volume":"2","author":"Pearson Karl","year":"1902","unstructured":"Karl Pearson. 1902. On the systematic fitting of frequency curves. Biometrika, 2 (1902), 2\u20137.","journal-title":"Biometrika"},{"key":"e_1_3_2_1_61_1","volume-title":"Surveys in Combinatorics","author":"Saks M.","year":"1993","unstructured":"M. Saks. 1993. Slicing the hypercube. In Surveys in Combinatorics 1993, Keith Walker (Ed.). London Mathematical Society Lecture Note Series 187, 211\u2013257."},{"key":"e_1_3_2_1_62_1","volume-title":"Truncated and censored samples from normal populations","author":"Schneider Helmut","unstructured":"Helmut Schneider. 1986. Truncated and censored samples from normal populations. Marcel Dekker, Inc.."},{"key":"e_1_3_2_1_63_1","volume-title":"Servedio and Li-Yang Tan","author":"Rocco","year":"2018","unstructured":"Rocco A. Servedio and Li-Yang Tan. 2018. Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX\/RANDOM), Eric Blais, Klaus Jansen, Jos\u00e9 D. P. Rolim, and David Steurer (Eds.) (LIPIcs, Vol. 116). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 56:1\u201356:20."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844850"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.19"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm180-3-3"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649633","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":66,"alternative-id":["10.1145\/3618260.3649633","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649633","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}