{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:31Z","timestamp":1781031451264,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":88,"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.3800725","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"42-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Smoothed Analysis of Learning from Positive Samples"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8532-4400","authenticated-orcid":false,"given":"Jane H.","family":"Lee","sequence":"first","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8566-5452","authenticated-orcid":false,"given":"Anay","family":"Mehrotra","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4967-5927","authenticated-orcid":false,"given":"Manolis","family":"Zampetakis","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, 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":"Proceedings of the 26th Annual Conference on Learning Theory, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (Proceedings of Machine Learning Research","volume":"1045","author":"Anderson Joseph","year":"2013","unstructured":"Joseph Anderson, Navin Goyal, and Luis Rademacher. 2013. Efficient Learning of Simplices. In Proceedings of the 26th Annual Conference on Learning Theory, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (Proceedings of Machine Learning Research, Vol. 30). PMLR, Princeton, NJ, USA. 1020\u20131045. https:\/\/proceedings.mlr.press\/v30\/Anderson13.html"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007409"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-020-05877-5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5179-6"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718111"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"629","author":"Block Adam","year":"2024","unstructured":"Adam Block, Alexander Rakhlin, and Abhishek Shetty. 2024. On the Performance of Empirical Risk Minimization with Smoothed Data. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 596\u2013629. https:\/\/proceedings.mlr.press\/v247\/block24a.html"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-11-228"},{"key":"e_1_3_2_1_9_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_10_1","volume-title":"Truncated and Censored Samples: Theory and Applications","author":"Cohen A. Clifford","year":"2005","unstructured":"A. Clifford Cohen. 1991. Truncated and Censored Samples: Theory and Applications. Taylor & Francis. isbn:9781420052114 https:\/\/books.google.com\/books?id=ZRs86JTMdogC"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00067"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the Thirty-Second Conference on Learning Theory, Alina Beygelzimer and Daniel Hsu (Eds.) (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 Proceedings of the Thirty-Second Conference on Learning Theory, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 955\u2013960. https:\/\/proceedings.mlr.press\/v99\/daskalakis19a.html"},{"key":"e_1_3_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems","author":"Daskalakis Constantinos","year":"1952","unstructured":"Constantinos Daskalakis, Patroklos Stefanou, Rui Yao, and Emmanouil Zampetakis. 2021. Efficient Truncated Linear Regression with Unknown Noise Variance. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.). 34, Curran Associates, Inc., 1952\u20131963. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/0ed8861dc36bee580d100f91283d0559-Paper.pdf"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.33"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649633"},{"key":"e_1_3_2_1_17_1","volume-title":"Servedio","author":"De Anindya","year":"2024","unstructured":"Anindya De, Huan Li, Shivam Nadimpalli, and Rocco A. Servedio. 2024. Detecting Low-Degree Truncation (. https:\/\/www.youtube.com\/watch?v=HLP5IL29Ca8"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch155"},{"key":"e_1_3_2_1_19_1","volume-title":"PAC Learning from Positive Statistical Queries","author":"Denis Fran\u00e7ois","unstructured":"Fran\u00e7ois Denis. 1998. PAC Learning from Positive Statistical Queries. In Algorithmic Learning Theory, Michael M. Richter, Carl H. Smith, Rolf Wiehagen, and Thomas Zeugmann (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 112\u2013126. isbn:978-3-540-49730-1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806763"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"1363","author":"Diakonikolas Ilias","year":"2024","unstructured":"Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. 2024. Statistical Query Lower Bounds for Learning Truncated Gaussians. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 1336\u20131363. https:\/\/proceedings.mlr.press\/v247\/diakonikolas24b.html"},{"key":"e_1_3_2_1_22_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=0Lb8vZT1DB","author":"Diakonikolas Ilias","year":"2024","unstructured":"Ilias Diakonikolas, Lisheng Ren, and Nikos Zarifis. 2024. Reliable Learning of Halfspaces under Gaussian Marginals. In The Thirty-eighth Annual Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=0Lb8vZT1DB"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 30th International Conference on Algorithmic Learning Theory, Aur\u00e9lien Garivier and Satyen Kale (Eds.) (Proceedings of Machine Learning Research","volume":"382","author":"Durgin Alexander","year":"2019","unstructured":"Alexander Durgin and Brendan Juba. 2019. Hardness of Improper One-Sided Learning of Conjunctions For All Uniformly Falsifiable CSPs. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, Aur\u00e9lien Garivier and Satyen Kale (Eds.) (Proceedings of Machine Learning Research, Vol. 98). PMLR, 369\u2013382. https:\/\/proceedings.mlr.press\/v98\/durgin19a.html"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401920"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_26_1","first-page":"815","article-title":"Properties and Applications of HH Functions","volume":"1","author":"Fisher R. A.","year":"1931","unstructured":"R. A. Fisher. 1931. Properties and Applications of HH Functions. Mathematical Tables, 1 (1931), 815\u2013852.","journal-title":"Mathematical Tables"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of Thirty Third Conference on Learning Theory, Jacob Abernethy and Shivani Agarwal (Eds.) (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 Proceedings of Thirty Third Conference on Learning Theory, Jacob Abernethy and Shivani Agarwal (Eds.) (Proceedings of Machine Learning Research, Vol. 125). PMLR, 1586\u20131600. https:\/\/proceedings.mlr.press\/v125\/fotakis20a.html"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548495"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3184\u20133196","author":"Galanis Andreas","year":"2024","unstructured":"Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. 2024. Learning Hard-Constrained Models with One Sample. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3184\u20133196. arxiv:2311.03332"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspl.1897.0115"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 2017 Conference on Learning Theory, Satyen Kale and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research","volume":"1042","author":"Goel Surbhi","year":"2017","unstructured":"Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. 2017. Reliably Learning the ReLU in Polynomial Time. In Proceedings of the 2017 Conference on Learning Theory, Satyen Kale and Ohad Shamir (Eds.) (Proceedings of Machine Learning Research, Vol. 65). PMLR, 1004\u20131042. https:\/\/proceedings.mlr.press\/v65\/goel17a.html"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS \u201920)","author":"Goldwasser Shafi","year":"2020","unstructured":"Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. 2020. Beyond perturbations: learning guarantees with arbitrary adversarial test examples. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS \u201920). Curran Associates Inc., Red Hook, NY, USA. Article 1330, 12 pages. isbn:9781713829546"},{"key":"e_1_3_2_1_33_1","volume-title":"Advances in Neural Information Processing Systems","author":"Gollakota Aravind","year":"2023","unstructured":"Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2023. Tester-Learners for Halfspaces: Universal Algorithms. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.). 36, Curran Associates, Inc., 10145\u201310169. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/204d9a9a4816a45909010587ffc3204b-Paper-Conference.pdf"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585206"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_3_2_1_36_1","volume-title":"Servedio","author":"Gopalan Parikshit","year":"2010","unstructured":"Parikshit Gopalan and Rocco A. Servedio. 2010. Learning and Lower Bounds for AC0 with Threshold Gates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Maria Serna, Ronen Shaltiel, Klaus Jansen, and Jos\u00e9 Rolim (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 588\u2013601. isbn:978-3-642-15369-3"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685798"},{"key":"e_1_3_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.). 35, Curran Associates","author":"Haghtalab Nika","year":"2022","unstructured":"Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. 2022. Oracle-Efficient Online Learning for Smoothed Adversaries. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.). 35, Curran Associates, Inc., 4072\u20134084. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/1a04df6a405210aab4986994b873db9b-Paper-Conference.pdf"},{"key":"e_1_3_2_1_39_1","volume-title":"Advances in Neural Information Processing Systems","author":"Haghtalab Nika","year":"2020","unstructured":"Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2020. Smoothed Analysis of Online and Differentially Private Learning. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.). 33, Curran Associates, Inc., 9203\u20139215. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2020\/file\/685bfde03eb646c27ed565881917c71c-Paper.pdf"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00095"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656638"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610929908832440"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395118"},{"key":"e_1_3_2_1_44_1","unstructured":"William He and Shivam Nadimpalli. 2023. Testing Junta Truncation. arxiv:2308.13992. arxiv:2308.13992"},{"key":"e_1_3_2_1_45_1","unstructured":"K. Jaskie and A. Spanias. 2022. Positive Unlabeled Learning. Morgan & Claypool Publishers. isbn:9781636393094 https:\/\/books.google.com\/books?id=KRBsEAAAQBAJ"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00147"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1155\/2016\/4525786"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the 32nd International Conference on Algorithmic Learning Theory, Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.) (Proceedings of Machine Learning Research","volume":"864","author":"Kalai Adam Tauman","year":"2021","unstructured":"Adam Tauman Kalai and Varun Kanade. 2021. Efficient Learning with Arbitrary Covariate Shift. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, Vitaly Feldman, Katrina Ligett, and Sivan Sabato (Eds.) (Proceedings of Machine Learning Research, Vol. 132). PMLR, 850\u2013864."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.026"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_51_1","unstructured":"Alkis Kalavasis Ilias Zadik and Manolis Zampetakis. 2024. Transfer Learning Beyond Bounded Density Ratios. arxiv:2403.11963."},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of The 27th Conference on Learning Theory, Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.) (Proceedings of Machine Learning Research","volume":"24","author":"Kanade Varun","year":"2014","unstructured":"Varun Kanade and Justin Thaler. 2014. Distribution-Independent Reliable Learning. In Proceedings of The 27th Conference on Learning Theory, Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.) (Proceedings of Machine Learning Research, Vol. 35). PMLR, Barcelona, Spain. 3\u201324."},{"key":"e_1_3_2_1_53_1","volume-title":"Proceedings of the 26th Annual Conference on Learning Theory, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (Proceedings of Machine Learning Research","volume":"545","author":"Kane Daniel","year":"2013","unstructured":"Daniel Kane, Adam Klivans, and Raghu Meka. 2013. Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching. In Proceedings of the 26th Annual Conference on Learning Theory, Shai Shalev-Shwartz and Ingo Steinwart (Eds.) (Proceedings of Machine Learning Research, Vol. 30). PMLR, Princeton, NJ, USA. 522\u2013545."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01191474"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"2943","author":"Klivans Adam","year":"2024","unstructured":"Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. 2024. Testable Learning with Distribution Shift. In Proceedings of Thirty Seventh Conference on Learning Theory, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, 2887\u20132943."},{"key":"e_1_3_2_1_56_1","volume-title":"Efficient Truncated Statistics with Unknown Truncation. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1578\u20131595","author":"Kontonis Vasilis","year":"2019","unstructured":"Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis. 2019. Efficient Truncated Statistics with Unknown Truncation. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1578\u20131595."},{"key":"e_1_3_2_1_57_1","first-page":"208","article-title":"Table of the Gaussian \u2018Tail\u2019 Functions; When the \u2018Tail\u2019 is Larger than the Body","volume":"10","author":"Lee Alice","year":"1914","unstructured":"Alice Lee. 1914. Table of the Gaussian \u2018Tail\u2019 Functions; When the \u2018Tail\u2019 is Larger than the Body. Biometrika, 10, 2\/3 (1914), 208\u2013214. issn:00063444 http:\/\/www.jstor.org\/stable\/2331782","journal-title":"Biometrika"},{"key":"e_1_3_2_1_58_1","volume-title":"Thirty-seventh Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=PxcWJqO3qj","author":"Lee Jane","year":"2023","unstructured":"Jane Lee, Andre Wibisono, and Manolis Zampetakis. 2023. Learning Exponential Families from Truncated Samples. In Thirty-seventh Conference on Neural Information Processing Systems. https:\/\/openreview.net\/forum?id=PxcWJqO3qj"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00066"},{"key":"e_1_3_2_1_60_1","unstructured":"Jane H. Lee Anay Mehrotra and Manolis Zampetakis. 2025. Smoothed Analysis of Learning from Positive Samples. arxiv:2504.10428. arxiv:2504.10428"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbab461"},{"key":"e_1_3_2_1_62_1","volume-title":"Third IEEE international conference on data mining. 179\u2013186","author":"Liu Bing","year":"2003","unstructured":"Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee, and Philip S Yu. 2003. Building text classifiers using positive and unlabeled examples. In Third IEEE international conference on data mining. 179\u2013186."},{"key":"e_1_3_2_1_63_1","volume-title":"Limited-Dependent and Qualitative Variables in Econometrics","author":"Maddala G.S.","year":"2009","unstructured":"G.S. Maddala. 1983. Limited-Dependent and Qualitative Variables in Econometrics. Cambridge University Press. isbn:9780521338257 lccn:82009554 https:\/\/books.google.com\/books?id=-Ji1ZaUg7gcC"},{"key":"e_1_3_2_1_64_1","unstructured":"Bodo Manthey. 2021. Smoothed Analysis of Local Search. isbn:9781108494311 lccn:2020049362 https:\/\/books.google.com\/books?id=FF8JEAAAQBAJ"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-389"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i8.26110"},{"key":"e_1_3_2_1_67_1","volume-title":"Proceedings of the 31st International Conference on Algorithmic Learning Theory, Aryeh Kontorovich and Gergely Neu (Eds.) (Proceedings of Machine Learning Research","volume":"659","author":"Nagarajan Sai Ganesh","year":"2020","unstructured":"Sai Ganesh Nagarajan and Ioannis Panageas. 2020. On the Analysis of EM for truncated mixtures of two Gaussians. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, Aryeh Kontorovich and Gergely Neu (Eds.) (Proceedings of Machine Learning Research, Vol. 117). PMLR, 634\u2013659. https:\/\/proceedings.mlr.press\/v117\/nagarajan20a.html"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28427"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-008-9031-0"},{"key":"e_1_3_2_1_70_1","first-page":"1","article-title":"On the Systematic Fitting of Curves to Observations and Measurments","volume":"2","author":"Pearson Karl","year":"1902","unstructured":"Karl Pearson. 1902. On the Systematic Fitting of Curves to Observations and Measurments: Part II. Biometrika, 2, 1 (1902), 1\u201323. issn:00063444 http:\/\/www.jstor.org\/stable\/2331498","journal-title":"Part II. Biometrika"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/6.1.59"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015412"},{"key":"e_1_3_2_1_73_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, Francis Bach and David Blei (Eds.) (Proceedings of Machine Learning Research","volume":"1394","author":"Plessis Marthinus Du","year":"2015","unstructured":"Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. 2015. Convex Formulation for Learning from Positive and Unlabeled Data. In Proceedings of the 32nd International Conference on Machine Learning, Francis Bach and David Blei (Eds.) (Proceedings of Machine Learning Research, Vol. 37). PMLR, Lille, France. 1386\u20131394. https:\/\/proceedings.mlr.press\/v37\/plessis15.html"},{"key":"e_1_3_2_1_74_1","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research","volume":"3787","author":"Plevrakis Orestis","year":"2021","unstructured":"Orestis Plevrakis. 2021. Learning From Censored and Dependent Data: The Case of Linear Dynamics. In Proceedings of Thirty Fourth Conference on Learning Theory, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 3771\u20133787. https:\/\/proceedings.mlr.press\/v134\/plevrakis21a.html"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00477-011-0458-8"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585117"},{"key":"e_1_3_2_1_78_1","volume-title":"Proceedings of the AAAI conference on artificial intelligence. 33","author":"Sakai Tomoya","year":"2019","unstructured":"Tomoya Sakai and Nobuyuki Shimizu. 2019. Covariate shift adaptation on learning from positive and unlabeled data. In Proceedings of the AAAI conference on artificial intelligence. 33, 4838\u20134845."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00115896"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_81_1","unstructured":"Wai Ming Tai and Bryon Aragam. 2023. Learning Mixtures of Gaussians with Censored Data. In Proceedings of the 40th International Conference on Machine Learning Andreas Krause Emma Brunskill Kyunghyun Cho Barbara Engelhardt Sivan Sabato and Jonathan Scarlett (Eds.) (Proceedings of Machine Learning Research Vol. 202). PMLR 33396\u201333415. https:\/\/proceedings.mlr.press\/v202\/tai23a.html"},{"key":"e_1_3_2_1_82_1","series-title":"Series A, Mathematical and Physical Sciences, 312, 1522","volume-title":"Deductive learning. Philosophical Transactions of the Royal Society of London","author":"Valiant Leslie Gabriel","year":"1984","unstructured":"Leslie Gabriel Valiant. 1984. Deductive learning. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 312, 1522 (1984), 441\u2013446."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.17"},{"key":"e_1_3_2_1_85_1","volume-title":"Segal","author":"Xiao Yuanyuan","year":"2008","unstructured":"Yuanyuan Xiao and Mark R. Segal. 2008. Biological Sequence Classification Utilizing Positive and Unlabeled Data. Bioinformatics, 24, 9 (2008), 03, 1198\u20131205. issn:1367-4803"},{"key":"e_1_3_2_1_86_1","volume-title":"Positive-Unlabeled Learning for Disease Gene Identification. Bioinformatics, 28, 20","author":"Yang Peng","year":"2012","unstructured":"Peng Yang, Xiao-Li Li, Jian-Ping Mei, Chee-Keong Kwoh, and See-Kiong Ng. 2012. Positive-Unlabeled Learning for Disease Gene Identification. Bioinformatics, 28, 20 (2012), 08, 2640\u20132647. issn:1367-4803"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2018.2816984"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-9-57"}],"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.3800725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:03Z","timestamp":1781028243000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":88,"alternative-id":["10.1145\/3798129.3800725","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800725","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"}}]}}