{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T17:25:59Z","timestamp":1788888359289,"version":"build-2803163510"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-1855464"],"award-info":[{"award-number":["DMS-1855464"]}]},{"name":"BSF","award":["2018267"],"award-info":[{"award-number":["2018267"]}]},{"name":"NSF","award":["CCF-1947889"],"award-info":[{"award-number":["CCF-1947889"]}]},{"name":"CAREER","award":["CNS-2046425"],"award-info":[{"award-number":["CNS-2046425"]}]},{"name":"ISF","award":["2188\/20"],"award-info":[{"award-number":["2188\/20"]}]},{"name":"NSF CAREER","award":["1553653"],"award-info":[{"award-number":["1553653"]}]},{"name":"ISF","award":["1225\/20"],"award-info":[{"award-number":["1225\/20"]}]},{"name":"BSF","award":["2018385"],"award-info":[{"award-number":["2018385"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>H<\/jats:italic>\n            be a binary-labeled concept class. We prove that\n            <jats:italic>H<\/jats:italic>\n            can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.\n          <\/jats:p>","DOI":"10.1145\/3526074","type":"journal-article","created":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:12:42Z","timestamp":1649070762000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Private and Online Learnability Are Equivalent"],"prefix":"10.1145","volume":"69","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Princeton University and Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Bun","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roi","family":"Livni","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maryanthe","family":"Malliaris","sequence":"additional","affiliation":[{"name":"University of Chicago, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8662-2737","authenticated-orcid":false,"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,16]]},"reference":[{"key":"e_1_3_5_2_2","first-page":"263","volume-title":"Proceedings of the 21st Annual Conference on Learning Theory (COLT\u201908)","author":"Abernethy Jacob D.","year":"2008","unstructured":"Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. 2008. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Annual Conference on Learning Theory (COLT\u201908). 263\u2013274."},{"key":"e_1_3_5_3_2","article-title":"Online learning via differential privacy","volume":"1711","author":"Abernethy Jacob D.","year":"2017","unstructured":"Jacob D. Abernethy, Chansoo Lee, Audra McMillan, and Ambuj Tewari. 2017. Online learning via differential privacy. CoRR abs\/1711.10019 (2017).","journal-title":"CoRR"},{"key":"e_1_3_5_4_2","first-page":"32","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017 (Proceedings of Machine Learning Research)","volume":"70","author":"Agarwal Naman","year":"2017","unstructured":"Naman Agarwal and Karan Singh. 2017. The price of differential privacy for online learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017 (Proceedings of Machine Learning Research), Doina Precup and Yee Whye Teh (Eds.). Vol. 70. PMLR, 32\u201340. http:\/\/proceedings.mlr.press\/v70\/agarwal17a.html."},{"key":"e_1_3_5_5_2","article-title":"Closure properties for private classification and online prediction","author":"Alon Noga","year":"2020","unstructured":"Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. 2020. Closure properties for private classification and online prediction. arXiv preprint arXiv:2003.04509 (2020).","journal-title":"arXiv preprint arXiv:2003.04509"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_5_7_2","article-title":"Private learning implies quantum stability","volume":"2102","author":"Arunachalam Srinivasan","year":"2021","unstructured":"Srinivasan Arunachalam, Yihui Quek, and John A. Smolin. 2021. Private learning implies quantum stability. CoRR abs\/2102.07171 (2021). https:\/\/arxiv.org\/abs\/2102.07171.","journal-title":"CoRR"},{"key":"e_1_3_5_8_2","first-page":"25","volume-title":"Algorithmic Learning Theory, ALT 2018, 7\u20139 April 2018, Lanzarote, Canary Islands, Spain (Proceedings of Machine Learning Research)","volume":"83","author":"Bassily Raef","year":"2018","unstructured":"Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. 2018. Learners that use little information. In Algorithmic Learning Theory, ALT 2018, 7\u20139 April 2018, Lanzarote, Canary Islands, Spain (Proceedings of Machine Learning Research), Firdaus Janoos, Mehryar Mohri, and Karthik Sridharan (Eds.). Vol. 83. PMLR, 25\u201355. http:\/\/proceedings.mlr.press\/v83\/bassily18a.html."},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5404-1"},{"key":"e_1_3_5_10_2","first-page":"269","volume-title":"Conference on Learning Theory, COLT 2019, 25\u201328 June 2019, Phoenix, AZ, USA (Proceedings of Machine Learning Research)","volume":"99","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, COLT 2019, 25\u201328 June 2019, Phoenix, AZ, USA (Proceedings of Machine Learning Research), Alina Beygelzimer and Daniel Hsu (Eds.). Vol. 99. PMLR, 269\u2013282."},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.32"},{"key":"e_1_3_5_12_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a001"},{"issue":"146","key":"e_1_3_5_13_2","first-page":"1","article-title":"Characterizing the sample complexity of pure private learners","volume":"20","author":"Beimel Amos","year":"2019","unstructured":"Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2019. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research 20, 146 (2019), 1\u201333. http:\/\/jmlr.org\/papers\/v20\/18-269.html.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_5_14_2","volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory (COLT\u201909)","author":"Ben-David Shai","year":"2009","unstructured":"Shai Ben-David, D\u00e1vid P\u00e1l, and Shai Shalev-Shwartz. 2009. Agnostic online learning. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT\u201909). 1\u201311."},{"key":"e_1_3_5_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1162\/153244302760200704"},{"key":"e_1_3_5_17_2","unstructured":"Olivier Bousquet Roi Livni and Shay Moran. 2019. Passing tests without memorizing: Two models for fooling discriminators. arxiv:cs.LG\/1902.03468 (2019) ."},{"key":"e_1_3_5_18_2","unstructured":"Mark Bun. 2020. A computational separation between private learning and online learning. In Proceedings of the 34th Joint Conference on Neural Information Processing Systems (NeurIPS\u201920) ."},{"key":"e_1_3_5_19_2","article-title":"Efficient, noise-tolerant, and private learning via boosting","volume":"2002","author":"Bun Mark","year":"2020","unstructured":"Mark Bun, Marco L. Carmosino, and Jessica Sorrell. 2020. Efficient, noise-tolerant, and private learning via boosting. CoRR abs\/2002.01100 (2020).","journal-title":"CoRR"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_3_5_21_2","unstructured":"Mark Bun Marco Gaboardi and Satchit Sivakumar. 2021. Multiclass versus binary differentially private PAC learning. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921) . 1\u201312."},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840747"},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_3_5_24_2","volume-title":"New Separations in the Complexity of Differential Privacy","author":"Bun Mark Mar","year":"2016","unstructured":"Mark Mar Bun. 2016. New Separations in the Complexity of Differential Privacy. Ph.D. Dissertation. Graduate School of Arts & Sciences, Harvard University."},{"key":"e_1_3_5_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_3_5_26_2","article-title":"Model theory and machine learning","author":"Chase Hunter","year":"2018","unstructured":"Hunter Chase and James Freitag. 2018. Model theory and machine learning. arXiv preprint arXiv:1801.06566 (2018).","journal-title":"arXiv preprint arXiv:1801.06566"},{"key":"e_1_3_5_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2018.71"},{"key":"e_1_3_5_28_2","unstructured":"Alon Cohen Avinatan Hassidim Haim Kaplan Yishay Mansour and Shay Moran. 2019. Learning to screen. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS\u201919) . 8612\u20138621. http:\/\/papers.nips.cc\/paper\/9067-learning-to-screen."},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329627"},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314183.3323847"},{"key":"e_1_3_5_31_2","first-page":"214","volume-title":"Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8\u201310, 2012","author":"Dwork Cynthia","year":"2012","unstructured":"Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. 2012. Fairness through awareness. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8\u201310, 2012, Shafi Goldwasser (Ed.). ACM, New York, NY, 214\u2013226."},{"key":"e_1_3_5_32_2","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Krishnaram Kenthapadi Frank McSherry Ilya Mironov and Moni Naor. 2006. Our data ourselves: Privacy via distributed noise generation. In EUROCRYPT . Lecture Notes in Computer Science Vol. 4004. Springer 486\u2013503.","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_5_33_2","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork and Jing Lei. 2009. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC\u201909) . 371\u2013380.","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_3_5_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_5_35_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_5_36_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_5_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_5_38_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.417"},{"key":"e_1_3_5_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/140991844"},{"key":"e_1_3_5_40_2","first-page":"136","article-title":"Probabilistic search algorithms with unique answers and their cryptographic applications","volume":"18","author":"Gat Eran","year":"2011","unstructured":"Eran Gat and Shafi Goldwasser. 2011. Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity 18 (2011), 136.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_3_5_41_2","article-title":"Sample-efficient proper PAC learning with approximate differential privacy","volume":"2012","author":"Ghazi Badih","year":"2020","unstructured":"Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. 2020. Sample-efficient proper PAC learning with approximate differential privacy. CoRR abs\/2012.03893 (2020).","journal-title":"CoRR"},{"key":"e_1_3_5_42_2","volume-title":"Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921)","author":"Ghazi Badih","year":"2021","unstructured":"Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2021. User-level private learning via correlated sampling. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921). 1\u201313."},{"key":"e_1_3_5_43_2","first-page":"2149","volume-title":"Conference on Learning Theory, COLT 2021, 15\u201319 August 2021, Boulder, Colorado, USA (Proceedings of Machine Learning Research)","volume":"134","author":"Golowich Noah","year":"2021","unstructured":"Noah Golowich. 2021. Differentially private nonparametric regression under a growth condition. In Conference on Learning Theory, COLT 2021, 15\u201319 August 2021, Boulder, Colorado, USA (Proceedings of Machine Learning Research), Mikhail Belkin and Samory Kpotufe (Eds.). Vol. 134. PMLR, 2149\u20132192."},{"key":"e_1_3_5_44_2","volume-title":"Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921)","author":"Golowich Noah","year":"2021","unstructured":"Noah Golowich and Roi Livni. 2021. Littlestone classes are privately online learnable. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921). 1\u201312."},{"key":"e_1_3_5_45_2","unstructured":"Alon Gonen Elad Hazan and Shay Moran. 2019. Private learning implies online learning: An efficient reduction. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS\u201919) ."},{"key":"e_1_3_5_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/85271"},{"key":"e_1_3_5_47_2","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_5_48_2","doi-asserted-by":"publisher","DOI":"10.5555\/262326"},{"key":"e_1_3_5_49_2","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo Rex Lei Toniann Pitassi and Jessica Sorrell. 2022. Reproducibility in learning. arxiv:cs.LG\/2201.08430 (2022).","DOI":"10.1145\/3519935.3519973"},{"key":"e_1_3_5_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00015"},{"key":"e_1_3_5_51_2","unstructured":"Young Hun Jung Baekjin Kim and Ambuj Tewari. 2020. On the equivalence between online and private learnability beyond binary classification. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS\u201920) . 1\u201310."},{"key":"e_1_3_5_52_2","unstructured":"Adam Kalai and Santosh Vempala. 2002. Geometric Algorithms for Online Optimization . Technical Report MIT-LCS-TR-861. Massachusetts Institute of Technology Cambridge MA."},{"key":"e_1_3_5_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_3_5_54_2","unstructured":"Haim Kaplan Katrina Ligett Yishay Mansour Moni Naor and Uri Stemmer. 2019. Privately learning thresholds: Closing the exponential gap. arxiv:cs.DS\/1911.10137 (2019)."},{"key":"e_1_3_5_55_2","first-page":"2263","volume-title":"Conference on Learning Theory, COLT 2020, 9\u201312 July 2020, Virtual Event [Graz, Austria] (Proceedings of Machine Learning Research)","volume":"125","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. 2020. Privately learning thresholds: Closing the exponential gap. In Conference on Learning Theory, COLT 2020, 9\u201312 July 2020, Virtual Event [Graz, Austria] (Proceedings of Machine Learning Research), Jacob D. Abernethy and Shivani Agarwal (Eds.). Vol. 125. PMLR, 2263\u20132285."},{"key":"e_1_3_5_56_2","unstructured":"Haim Kaplan Yishay Mansour Uri Stemmer and Eliad Tsfadia. 2020. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS\u201920) . 1\u201310."},{"key":"e_1_3_5_57_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1477"},{"key":"e_1_3_5_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_5_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526733"},{"key":"e_1_3_5_60_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-45.2.377"},{"key":"e_1_3_5_61_2","article-title":"A necessary and sufficient stability notion for adaptive generalization","volume":"1906","author":"Ligett Katrina","year":"2019","unstructured":"Katrina Ligett and Moshe Shenfeld. 2019. A necessary and sufficient stability notion for adaptive generalization. CoRR abs\/1906.00930 (2019).","journal-title":"CoRR"},{"key":"e_1_3_5_62_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"e_1_3_5_63_2","first-page":"77","volume-title":"Proceedings of the Conference on Learning Theory","author":"Livni Roi","year":"2013","unstructured":"Roi Livni and Pierre Simon. 2013. Honest compressions and their application to compression schemes. In Proceedings of the Conference on Learning Theory. 77\u201392."},{"key":"e_1_3_5_64_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007618624809"},{"key":"e_1_3_5_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_5_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4259"},{"key":"e_1_3_5_67_2","article-title":"A survey of quantitative bounds for hypergraph Ramsey problems","author":"Mubayi D.","year":"2017","unstructured":"D. Mubayi and A. Suk. 2017. A survey of quantitative bounds for hypergraph Ramsey problems. ArXiv e-printsarxiv:math.CO\/1707.04229(2017).","journal-title":"ArXiv e-prints"},{"key":"e_1_3_5_68_2","first-page":"1547","volume-title":"Conference on Learning Theory, COLT 2018, Stockholm, Sweden, 6\u20139 July 2018 (Proceedings of Machine Learning Research)","volume":"75","author":"Nachum Ido","year":"2018","unstructured":"Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. 2018. A direct sum result for the information complexity of learning. In Conference on Learning Theory, COLT 2018, Stockholm, Sweden, 6\u20139 July 2018 (Proceedings of Machine Learning Research), S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.). Vol. 75. PMLR, 1547\u20131568. http:\/\/proceedings.mlr.press\/v75\/nachum18a.html."},{"key":"e_1_3_5_69_2","first-page":"633","volume-title":"Algorithmic Learning Theory, ALT 2019, 22\u201324 March 2019, Chicago, Illinois, USA (Proceedings of Machine Learning Research)","volume":"98","author":"Nachum Ido","year":"2019","unstructured":"Ido Nachum and Amir Yehudayoff. 2019. Average-case information complexity of learning. In Algorithmic Learning Theory, ALT 2019, 22\u201324 March 2019, Chicago, Illinois, USA (Proceedings of Machine Learning Research), Aur\u00e9lien Garivier and Satyen Kale (Eds.). Vol. 98. PMLR, 633\u2013646. http:\/\/proceedings.mlr.press\/v98\/nachum19a.html."},{"key":"e_1_3_5_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00014"},{"key":"e_1_3_5_71_2","unstructured":"RANDOM\u201918 Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques Igor Carboni Oliveira Rahul Santhanam Pseudo-derandomizing learning and approximation 2018"},{"key":"e_1_3_5_72_2","volume-title":"Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy.","author":"O\u2019Neil Cathy","year":"2016","unstructured":"Cathy O\u2019Neil. 2016. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy.Crown, New York, NY."},{"key":"e_1_3_5_73_2","unstructured":"Menachem Sadigurschi and Uri Stemmer. 2021. On the sample complexity of privately learning axis-aligned rectangles. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS\u201921) . 1\u201314."},{"key":"e_1_3_5_74_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_5_75_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_3_5_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5014-x"},{"key":"e_1_3_5_77_2","volume-title":"Classification Theory and the Number of Non-isomorphic Models","author":"Shelah Saharon","year":"1978","unstructured":"Saharon Shelah. 1978. Classification Theory and the Number of Non-isomorphic Models. North-Holland Publishing, Amsterdam, Netherlands."},{"key":"e_1_3_5_78_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_3_5_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_5_80_2","volume-title":"Theory of Pattern Recognition","author":"Vapnik Vladimir","year":"1974","unstructured":"Vladimir Vapnik and Alexey Chervonenkis. 1974. Theory of Pattern Recognition. Nauka."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3526074","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3526074","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3526074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:43:46Z","timestamp":1750272226000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3526074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,16]]},"references-count":79,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3526074"],"URL":"https:\/\/doi.org\/10.1145\/3526074","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,16]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}