{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:33Z","timestamp":1781078013140,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316312","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"852-860","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Private PAC learning implies finite Littlestone dimension"],"prefix":"10.1145","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Princeton University, USA \/ Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roi","family":"Livni","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maryanthe","family":"Malliaris","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Maria-Florina Balcan and Vitaly Feldman. 2015.  Maria-Florina Balcan and Vitaly Feldman. 2015."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9954-9"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897566"},{"key":"e_1_3_2_1_4_1","unstructured":"Raef Bassily Om Thakkar and Abhradeep Thakurta. 2018.  Raef Bassily Om Thakkar and Abhradeep Thakurta. 2018."},{"key":"e_1_3_2_1_5_1","volume-title":"CoRR abs\/1803.05101","author":"Private Model-Agnostic","year":"2018","unstructured":"Model-Agnostic Private Learning via Stability . CoRR abs\/1803.05101 ( 2018 ). Model-Agnostic Private Learning via Stability. CoRR abs\/1803.05101 (2018)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5404-1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Amos Beimel Kobbi Nissim and Uri Stemmer. 2013. Characterizing the sample complexity of private learners. In ITCS. ACM 97\u2013110.  Amos Beimel Kobbi Nissim and Uri Stemmer. 2013. Characterizing the sample complexity of private learners. In ITCS. ACM 97\u2013110.","DOI":"10.1145\/2422436.2422450"},{"key":"e_1_3_2_1_8_1","volume-title":"Learning Privately with Labeled and Unlabeled Examples","author":"Beimel Amos","unstructured":"Amos Beimel , Kobbi Nissim , and Uri Stemmer . 2015. Learning Privately with Labeled and Unlabeled Examples . In SODA. SIAM , 461\u2013477. Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2015. Learning Privately with Labeled and Unlabeled Examples. In SODA. SIAM, 461\u2013477."},{"key":"e_1_3_2_1_9_1","unstructured":"Amos Beimel Kobbi Nissim and Uri Stemmer. 2016.  Amos Beimel Kobbi Nissim and Uri Stemmer. 2016."},{"key":"e_1_3_2_1_10_1","volume-title":"Pure vs. Approximate Differential Privacy. Theory of Computing 12, 1","author":"Learning Private","year":"2016","unstructured":"Private Learning and Sanitization : Pure vs. Approximate Differential Privacy. Theory of Computing 12, 1 ( 2016 ), 1\u201361. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. Theory of Computing 12, 1 (2016), 1\u201361."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Shai Ben-David D\u00e1vid P\u00e1l and Shai Shalev-Shwartz. 2009.  Shai Ben-David D\u00e1vid P\u00e1l and Shai Shalev-Shwartz. 2009.","DOI":"10.3817\/0609147077"},{"key":"e_1_3_2_1_12_1","unstructured":"Agnostic Online Learning. In COLT.  Agnostic Online Learning. In COLT."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840747"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"e_1_3_2_1_17_1","unstructured":"Mark Mar Bun. 2016.  Mark Mar Bun. 2016."},{"key":"e_1_3_2_1_18_1","volume-title":"Graduate School of Arts &amp","author":"Differential Privacy New Separations","unstructured":"New Separations in the Complexity of Differential Privacy . Ph.D. Dissertation . Harvard University , Graduate School of Arts &amp ; Sciences . New Separations in the Complexity of Differential Privacy. Ph.D. Dissertation. Harvard University, Graduate School of Arts & Sciences."},{"key":"e_1_3_2_1_19_1","volume-title":"Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566","author":"Chase Hunter","year":"2018","unstructured":"Hunter Chase and James Freitag . 2018. Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566 ( 2018 ). Hunter Chase and James Freitag. 2018. Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566 (2018)."},{"key":"e_1_3_2_1_20_1","unstructured":"Kamalika Chaudhuri Daniel J. Hsu and Shuang Song. 2014. The Large Margin Mechanism for Differentially Private Maximization. In NIPS. 1287\u20131295.   Kamalika Chaudhuri Daniel J. Hsu and Shuang Song. 2014. The Large Margin Mechanism for Differentially Private Maximization. In NIPS. 1287\u20131295."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021036"},{"key":"e_1_3_2_1_22_1","volume-title":"Adaptive Learning with Robust Generalization Guarantees. In COLT (JMLR Workshop and Conference Proceedings)","volume":"49","author":"Cummings Rachel","year":"2016","unstructured":"Rachel Cummings , Katrina Ligett , Kobbi Nissim , Aaron Roth , and Zhiwei Steven Wu . 2016 . Adaptive Learning with Robust Generalization Guarantees. In COLT (JMLR Workshop and Conference Proceedings) , Vol. 49 . JMLR.org, 772\u2013814. Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu. 2016. Adaptive Learning with Robust Generalization Guarantees. In COLT (JMLR Workshop and Conference Proceedings), Vol. 49. JMLR.org, 772\u2013814."},{"key":"e_1_3_2_1_23_1","volume-title":"Privacy-preserving Prediction. CoRR abs\/1803.10266","author":"Dwork Cynthia","year":"2018","unstructured":"Cynthia Dwork and Vitaly Feldman . 2018. Privacy-preserving Prediction. CoRR abs\/1803.10266 ( 2018 ). Cynthia Dwork and Vitaly Feldman. 2018. Privacy-preserving Prediction. CoRR abs\/1803.10266 (2018)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_1_28_1","unstructured":"P. Erd\u0151s and R. Rado. 1952.  P. Erd\u0151s and R. Rado. 1952."},{"key":"e_1_3_2_1_29_1","first-page":"1","volume-title":"Proceedings of the London Mathematical Society s3-2","author":"Combinatorial Theorems","year":"1952","unstructured":"Combinatorial Theorems on Classifications of Subsets of a Given Set . Proceedings of the London Mathematical Society s3-2 , 1 ( 1952 ), 417\u2013439. 2.1.417 Combinatorial Theorems on Classifications of Subsets of a Given Set. Proceedings of the London Mathematical Society s3-2, 1 (1952), 417\u2013439. 2.1.417"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/140991844"},{"key":"e_1_3_2_1_31_1","unstructured":"R.L. Graham R.L. Graham B.L. Rothschild and J.H. Spencer. 1990.  R.L. Graham R.L. Graham B.L. Rothschild and J.H. Spencer. 1990."},{"key":"e_1_3_2_1_32_1","unstructured":"Ramsey Theory. Wiley. https:\/\/books.google.com\/books?id=55oXT60dC54C  Ramsey Theory. Wiley. https:\/\/books.google.com\/books?id=55oXT60dC54C"},{"key":"e_1_3_2_1_33_1","unstructured":"Wilfrid Hodges. 1997.  Wilfrid Hodges. 1997."},{"key":"e_1_3_2_1_34_1","volume-title":"Cambridge University Press","author":"Theory A Shorter Model","unstructured":"A Shorter Model Theory . Cambridge University Press , New York, NY, USA . A Shorter Model Theory. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1477"},{"key":"e_1_3_2_1_36_1","volume-title":"Smith","author":"Kasiviswanathan Shiva Prasad","year":"2011","unstructured":"Shiva Prasad Kasiviswanathan , Homin K. Lee , Kobbi Nissim , Sofya Raskhodnikova , and Adam D . Smith . 2011 . Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. 2011."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_38_1","unstructured":"Michael C Laskowski. 1992.  Michael C Laskowski. 1992."},{"key":"e_1_3_2_1_39_1","volume-title":"Journal of the London Mathematical Society 2, 2","author":"Definable Sets Vapnik-Chervonenkis","year":"1992","unstructured":"Vapnik-Chervonenkis Classes of Definable Sets . Journal of the London Mathematical Society 2, 2 ( 1992 ), 377\u2013384. Private PAC Learning Implies Finite Littlestone Dimension STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA Vapnik-Chervonenkis Classes of Definable Sets. Journal of the London Mathematical Society 2, 2 (1992), 377\u2013384. Private PAC Learning Implies Finite Littlestone Dimension STOC \u201919, June 23\u201326, 2019, Phoenix, AZ, USA"},{"key":"e_1_3_2_1_40_1","volume-title":"Wu","author":"Ligett Katrina","year":"2017","unstructured":"Katrina Ligett , Seth Neel , Aaron Roth , Bo Waggoner , and Steven Z . Wu . 2017 . Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z. Wu. 2017."},{"key":"e_1_3_2_1_41_1","unstructured":"Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. In NIPS. 2563\u20132573.   Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. In NIPS. 2563\u20132573."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"e_1_3_2_1_43_1","volume-title":"Conference on Learning Theory. 77\u201392","author":"Livni Roi","year":"2013","unstructured":"Roi Livni and Pierre Simon . 2013 . Honest compressions and their application to compression schemes . In Conference on Learning Theory. 77\u201392 . Roi Livni and Pierre Simon. 2013. Honest compressions and their application to compression schemes. In Conference on Learning Theory. 77\u201392."},{"key":"e_1_3_2_1_44_1","unstructured":"D. Mubayi and A. Suk. 2017. A survey of quantitative bounds for hypergraph Ramsey problems. ArXiv e-prints (July 2017). arXiv: math.CO\/1707.04229  D. Mubayi and A. Suk. 2017. A survey of quantitative bounds for hypergraph Ramsey problems. ArXiv e-prints (July 2017). arXiv: math.CO\/1707.04229"},{"key":"e_1_3_2_1_45_1","unstructured":"Benjamin I. P. Rubinstein Peter L. Bartlett Ling Huang and Nina Taft. 2009.  Benjamin I. P. Rubinstein Peter L. Bartlett Ling Huang and Nina Taft. 2009."},{"key":"e_1_3_2_1_46_1","volume-title":"Privacy-Preserving Mechanisms for SVM Learning. CoRR abs\/0911.5708","author":"Large Function Space Learning","year":"2009","unstructured":"Learning in a Large Function Space : Privacy-Preserving Mechanisms for SVM Learning. CoRR abs\/0911.5708 ( 2009 ). Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning. CoRR abs\/0911.5708 (2009)."},{"key":"e_1_3_2_1_47_1","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014.  Shai Shalev-Shwartz and Shai Ben-David. 2014."},{"key":"e_1_3_2_1_48_1","volume-title":"From Theory to Algorithms","author":"Learning Understanding Machine","unstructured":"Understanding Machine Learning : From Theory to Algorithms . Cambridge University Press , New York, NY, USA . Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_49_1","unstructured":"Saharon. Shelah. 1978.  Saharon. Shelah. 1978."},{"key":"e_1_3_2_1_50_1","volume-title":"Tutorials on the Foundations of Cryptography","author":"Vadhan Salil P.","unstructured":"Salil P. Vadhan . 2017. The Complexity of Differential Privacy . In Tutorials on the Foundations of Cryptography . Springer International Publishing , 347\u2013450. Salil P. Vadhan. 2017. The Complexity of Differential Privacy. In Tutorials on the Foundations of Cryptography. Springer International Publishing, 347\u2013450."},{"key":"e_1_3_2_1_51_1","unstructured":"V.N. Vapnik and A.Ya. Chervonenkis. 1971.  V.N. Vapnik and A.Ya. Chervonenkis. 1971."},{"key":"e_1_3_2_1_52_1","volume-title":"Theory Probab. Appl. 16","author":"On","year":"1971","unstructured":"On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16 ( 1971 ), 264\u2013280. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16 (1971), 264\u2013280."},{"key":"e_1_3_2_1_53_1","volume-title":"Fienberg","author":"Wang Yu-Xiang","year":"2016","unstructured":"Yu-Xiang Wang , Jing Lei , and Stephen E . Fienberg . 2016 . Yu-Xiang Wang, Jing Lei, and Stephen E. Fienberg. 2016."}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:00Z","timestamp":1750204440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":53,"alternative-id":["10.1145\/3313276.3316312","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316312","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}