{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:20Z","timestamp":1781031440886,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":49,"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.3800771","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"529-540","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9807-7385","authenticated-orcid":false,"given":"Ari","family":"Blondal","sequence":"first","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4732-434X","authenticated-orcid":false,"given":"Hamed","family":"Hatami","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7928-8008","authenticated-orcid":false,"given":"Pooya","family":"Hatami","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-0580-2727","authenticated-orcid":false,"given":"Chavdar","family":"Lalov","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5542-3206","authenticated-orcid":false,"given":"Sivan","family":"Tretiak","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, 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.1145\/3526074"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00070"},{"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.52202\/068431-2328"},{"key":"e_1_3_2_1_5_1","volume-title":"Conference on Learning Theory. 5638\u20135643","author":"Bassily Raef","year":"2022","unstructured":"Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. 2022. Open problem: Better differentially private learning algorithms with margin guarantees. In Conference on Learning Theory. 5638\u20135643."},{"key":"e_1_3_2_1_6_1","volume-title":"Conference on Learning Theory. 269\u2013282","author":"Beimel Amos","year":"2019","unstructured":"Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. 2019. Private center points and learning of halfspaces. In Conference on Learning Theory. 269\u2013282."},{"key":"e_1_3_2_1_7_1","volume-title":"Stability and List-Replicability for Agnostic Learners. In Conference on Learning Theory. 380\u2013\u2013400","author":"Blondal Ari","year":"2025","unstructured":"Ari Blondal, Shan Gao, Hamed Hatami, and Pooya Hatami. 2025. Stability and List-Replicability for Agnostic Learners. In Conference on Learning Theory. 380\u2013\u2013400."},{"key":"e_1_3_2_1_8_1","unstructured":"Ari Blondal Hamed Hatami Pooya Hatami Chavdar Lalov and Sivan Tretiak. 2025. Topological dimension of extremal concept classes. preprint."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_3_2_1_10_1","volume-title":"Conference on Learning Theory. 1031\u20131077","author":"Bun Mark","year":"2020","unstructured":"Mark Bun, Marco Leandro Carmosino, and Jessica Sorrell. 2020. Efficient, noise-tolerant, and private learning via boosting. In Conference on Learning Theory. 1031\u20131077."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585246"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649632"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00148"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.14"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.42"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_3_2_1_18_1","unstructured":"Bogdan Chornomaz Shay Moran and Tom Waknine. 2025. Spherical dimension. arXiv preprint arXiv:2503.10240."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-0667"},{"key":"e_1_3_2_1_21_1","volume-title":"Replicable Bandits. In The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=gcD2UtCGMc2","author":"Esfandiari Hossein","year":"2023","unstructured":"Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. 2023. Replicable Bandits. In The Eleventh International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=gcD2UtCGMc2"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-1707"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969651"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718129"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00119"},{"key":"e_1_3_2_1_26_1","volume-title":"TR11-136","author":"Gat Eran","year":"2011","unstructured":"Eran Gat and Shafi Goldwasser. 2011. Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. Electron. Colloquium Comput. Complex., TR11-136 (2011), ECCC:TR11-136. https:\/\/eccc.weizmann.ac.il\/report\/2011\/136"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451028"},{"key":"e_1_3_2_1_28_1","first-page":"20172","article-title":"User-level differentially private learning via correlated sampling","volume":"34","author":"Ghazi Badih","year":"2021","unstructured":"Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2021. User-level differentially private learning via correlated sampling. Advances in Neural Information Processing Systems, 34 (2021), 20172\u201320184.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.79"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.36"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.69"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525292"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-022-2365-8"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/lipics.approx\/random.2022.22"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585210"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3692070.3692989"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3618408.3619044"},{"key":"e_1_3_2_1_39_1","first-page":"13976","article-title":"Private learning of halfspaces: Simplifying the construction and reducing the sample complexity","volume":"33","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. 2020. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. Advances in Neural Information Processing Systems, 33 (2020), 13976\u201313985.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-3265"},{"key":"e_1_3_2_1_41_1","unstructured":"Huy L\u00ea Nguyen Jonathan Ullman and Lydia Zakynthinou. 2020. Efficient private algorithms for learning large-margin halfspaces. In Algorithmic Learning Theory. 704\u2013724."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009656"},{"key":"e_1_3_2_1_43_1","unstructured":"Maryanthe Malliaris and Shay Moran. 2022. The unstable formula theorem revisited via algorithms. arXiv preprint arXiv:2212.05050."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478259"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.52202\/075280-2697"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0042519"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2621980"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.705570"},{"key":"e_1_3_2_1_49_1","volume-title":"Space-Bounded Communication Complexity. Ph. D. Dissertation","author":"Song Hao","unstructured":"Hao Song. 2014. Space-Bounded Communication Complexity. Ph. D. Dissertation. Tsinghua University."}],"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.3800771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:31Z","timestamp":1781028091000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":49,"alternative-id":["10.1145\/3798129.3800771","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800771","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"}}]}}