{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:57:48Z","timestamp":1781218668084,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":27,"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":[{"name":"ERC","award":["101125203"],"award-info":[{"award-number":["101125203"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Award"],"award-info":[{"award-number":["Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Award"],"award-info":[{"award-number":["Award"]}],"id":[{"id":"10.13039\/100000893","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.3800910","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2064-2070","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Sample Complexity of Replicable Realizable PAC Learning"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8841-5929","authenticated-orcid":false,"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-6612-3046","authenticated-orcid":false,"given":"Markus Engelund","family":"Mathiasen","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3424-691X","authenticated-orcid":false,"given":"Chirag","family":"Pabbaraju","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9367-1303","authenticated-orcid":false,"given":"Clement","family":"Svendsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"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 Thirty Seventh Conference on Learning Theory (2024-06-30\/2024-07-03)","author":"Aden-Ali Ishaq","year":"2024","unstructured":"Ishaq Aden-Ali, Mikael M\u00f8ller H\u00f8andgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. 2024. Majority-of-Three: The Simplest Optimal Learner?. In Proceedings of Thirty Seventh Conference on Learning Theory (2024-06-30\/2024-07-03)"},{"key":"e_1_3_2_1_2_1","first-page":"22","volume-title":"Edmonton, Canada","author":"Machine Learning Research Proceedings","unstructured":"Proceedings of Machine Learning Research, Vol. 247), Shipra Agrawal and Aaron Roth (Eds.). PMLR, Edmonton, Canada, 22-45. https:\/\/proceedings.mlr.press\/ v247\/aden-ali24a.html"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Saba Ahmadi Siddharth Bhandari and Avrim Blum. 2024. Replicable Online Learning. arXiv:2411.13730 [cs.LG] doi:10.48550\/arXiv.2411.13730 10.48550\/arXiv.2411.13730","DOI":"10.48550\/arXiv.2411.13730"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-8638-3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/533452a"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1038\/d41586-023-03817-6"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585246"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Zachary Chase Shay Moran and Amir Yehudayoff. 2023. Replicability and stability in learning. arXiv:2304.03757 [cs.LG] doi:10.48550\/arXiv.2304.03757 10.48550\/arXiv.2304.03757","DOI":"10.48550\/arXiv.2304.03757"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Ilias Diakonikolas Jingyi Gao Daniel Kane Sihan Liu and Christopher Ye. 2025. Replicable Distribution Testing. arXiv:2507.02814 [cs.LG] doi:10.48550\/arXiv. 2507.02814 10.48550\/arXiv.2507.02814","DOI":"10.48550\/arXiv"},{"key":"e_1_3_2_1_12_1","first-page":"30784","volume-title":"Levine (Eds.)","volume":"36","author":"Dixon Peter","year":"2023","unstructured":"Peter Dixon, A. Pavan, Jason Vander Woude, and N. V. Vinodchandran. 2023. List and Certificate Complexities in Replicable Learning. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associates, Inc., San Diego, CA, USA, 30784-30806. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/ 61d0a96d4a73b626367310b3ad32579d-Paper-Conference.pdf"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_3_2_1_14_1","first-page":"39277","volume-title":"Levine (Eds.)","volume":"36","author":"Esfandiari Hossein","year":"2023","unstructured":"Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. 2023. Replicable Clustering. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associates, Inc., Red Hook, NY, USA, 39277-39320. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/ 7bc3fe234454107149fa9d44faacaa64-Paper-Conference.pdf"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1381988"},{"key":"e_1_3_2_1_16_1","first-page":"1","article-title":"The Optimal Sample Complexity of PAC Learning","volume":"17","author":"Hanneke Steve","year":"2016","unstructured":"Steve Hanneke. 2016. The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research 17, 38 (2016), 1-15. http:\/\/jmlr.org\/papers\/v17\/15- 389.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of The 36th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research","volume":"580","author":"H\u00f8gsgaard Mikael M\u00f8ller","year":"2025","unstructured":"Mikael M\u00f8ller H\u00f8gsgaard. 2025. Efficient Optimal PAC Learning. In Proceedings of The 36th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 272), Gautam Kamath and Po-Ling Loh (Eds.). PMLR, Milan, Italy, 578-580. https:\/\/proceedings.mlr.press\/v272\/hogsgaardmoller25a.html"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00103"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Max Hopkins Russell Impagliazzo and Christopher Ye. 2025. Approximate Replicability in Learning. arXiv:2510.20200 [cs.LG] doi:10.48550\/arXiv.2510.20200 10.48550\/arXiv.2510.20200","DOI":"10.48550\/arXiv.2510.20200"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 42nd International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"23827","author":"Hopkins Max","year":"2025","unstructured":"Max Hopkins and Shay Moran. 2025. The Role of Randomness in Stability. In Proceedings of the 42nd International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 267), Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (Eds.). PMLR, Vancouver, BC, Canada, 23805-23827. https:\/\/proceedings. mlr.press\/v267\/hopkins25a.html"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 41st International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"22878","author":"Kalavasis Alkis","year":"2024","unstructured":"Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. 2024. Replicable Learning of Large-Margin Halfspaces. In Proceedings of the 41st International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 235), Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (Eds.). PMLR, Vienna, Austria, 22861-22878. https:\/\/proceedings.mlr.press\/v235\/ kalavasis24a.html"},{"key":"e_1_3_2_1_23_1","first-page":"74702","volume-title":"Levine (Eds.)","volume":"36","author":"Karbasi Amin","year":"2023","unstructured":"Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. 2023. Replicability in Reinforcement Learning. In Advances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associates, Inc., New Orleans, LA, USA, 74702-74735. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/ ec4d2e436794d1bf55ca83f5ebb31887-Paper-Conference.pdf"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"468","author":"Larsen Kasper Green","year":"2023","unstructured":"Kasper Green Larsen. 2023. Bagging is an Optimal PAC Learner. In Proceedings of Thirty Sixth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 195), Gergely Neu and Lorenzo Rosasco (Eds.). PMLR, Bangalore, India, 450-468. https:\/\/proceedings.mlr.press\/v195\/larsen23a.html"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of The 28th Conference on Learning Theory (2015-07-03\/2015-07-06)","volume":"1563","author":"Simon Hans U.","year":"2015","unstructured":"Hans U. Simon. 2015. An Almost Optimal PAC Algorithm. In Proceedings of The 28th Conference on Learning Theory (2015-07-03\/2015-07-06) (Proceedings of Machine Learning Research, Vol. 40), Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.). PMLR, Paris, France, 1552-1563. https:\/\/proceedings.mlr.press\/v40\/ Simon15a.html"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808710"}],"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.3800910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:27:25Z","timestamp":1781216845000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":27,"alternative-id":["10.1145\/3798129.3800910","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800910","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"}}]}}