{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:30Z","timestamp":1781028330583,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":26,"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, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research","volume":"45","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, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research, Vol. 247). PMLR, Edmonton, Canada. 22\u201345. https:\/\/proceedings.mlr.press\/v247\/aden-ali24a.html"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Saba Ahmadi Siddharth Bhandari and Avrim Blum. 2024. Replicable Online Learning. arxiv:2411.13730. https:\/\/doi.org\/10.48550\/arXiv.2411.13730 10.48550\/arXiv.2411.13730","DOI":"10.48550\/arXiv.2411.13730"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00019-4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-8638-3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/533452a"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/d41586-023-03817-6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585246"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Zachary Chase Shay Moran and Amir Yehudayoff. 2023. Replicability and stability in learning. arxiv:2304.03757. https:\/\/doi.org\/10.48550\/arXiv.2304.03757 10.48550\/arXiv.2304.03757","DOI":"10.48550\/arXiv.2304.03757"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Ilias Diakonikolas Jingyi Gao Daniel Kane Sihan Liu and Christopher Ye. 2025. Replicable Distribution Testing. arxiv:2507.02814. https:\/\/doi.org\/10.48550\/arXiv.2507.02814 10.48550\/arXiv.2507.02814","DOI":"10.48550\/arXiv.2507.02814"},{"key":"e_1_3_2_1_11_1","volume-title":"Jason Vander Woude, and N. V. Vinodchandran","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.). 36, Curran Associates, Inc., San Diego, CA, USA. 30784\u201330806. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/61d0a96d4a73b626367310b3ad32579d-Paper-Conference.pdf"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-1707"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1381988"},{"key":"e_1_3_2_1_15_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\u201315. http:\/\/jmlr.org\/papers\/v17\/15-389.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of The 36th International Conference on Algorithmic Learning Theory, Gautam Kamath and Po-Ling Loh (Eds.) (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, Gautam Kamath and Po-Ling Loh (Eds.) (Proceedings of Machine Learning Research, Vol. 272). PMLR, Milan, Italy. 578\u2013580. https:\/\/proceedings.mlr.press\/v272\/hogsgaard-moller25a.html"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00103"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Max Hopkins Russell Impagliazzo and Christopher Ye. 2025. Approximate Replicability in Learning. arxiv:2510.20200. https:\/\/doi.org\/10.48550\/arXiv.2510.20200 10.48550\/arXiv.2510.20200","DOI":"10.48550\/arXiv.2510.20200"},{"key":"e_1_3_2_1_19_1","unstructured":"Max Hopkins and Shay Moran. 2025. The Role of Randomness in Stability. In Proceedings of the 42nd International Conference on Machine Learning Aarti Singh Maryam Fazel Daniel Hsu Simon Lacoste-Julien Felix Berkenkamp Tegan Maharaj Kiri Wagstaff and Jerry Zhu (Eds.) (Proceedings of Machine Learning Research Vol. 267). PMLR Vancouver BC Canada. 23805\u201323827. https:\/\/proceedings.mlr.press\/v267\/hopkins25a.html"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_2_1_21_1","volume-title":"Grigoris Velegkas, and Felix Zhou.","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, Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (Eds.) (Proceedings of Machine Learning Research, Vol. 235). PMLR, Vienna, Austria. 22861\u201322878. https:\/\/proceedings.mlr.press\/v235\/kalavasis24a.html"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-3265"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (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, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, Bangalore, India. 450\u2013468. https:\/\/proceedings.mlr.press\/v195\/larsen23a.html"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research","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, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (Proceedings of Machine Learning Research, Vol. 40). PMLR, Paris, France. 1552\u20131563. https:\/\/proceedings.mlr.press\/v40\/Simon15a.html"},{"key":"e_1_3_2_1_26_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,9]],"date-time":"2026-06-09T17:54:31Z","timestamp":1781027671000},"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":26,"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"}}]}}