{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:49:59Z","timestamp":1756000199606,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1595\/19;1871\/19"],"award-info":[{"award-number":["1595\/19;1871\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585148","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"472-482","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization"],"prefix":"10.1145","author":[{"given":"Edith","family":"Cohen","sequence":"first","affiliation":[{"name":"Google Research, USA \/ Tel Aviv University, Israel"}]},{"given":"Xin","family":"Lyu","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA \/ Google Research, USA"}]},{"given":"Jelani","family":"Nelson","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA \/ Google Research, USA"}]},{"given":"Tam\u00e1s","family":"Sarl\u00f3s","sequence":"additional","affiliation":[{"name":"Google Research, USA"}]},{"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Google Research, Israel"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"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":"crossref","unstructured":"Noga Alon Roi Livni Maryanthe Malliaris and Shay Moran. 2019. Private PAC learning implies finite Littlestone dimension. In STOC. \t\t\t\t  Noga Alon Roi Livni Maryanthe Malliaris and Shay Moran. 2019. Private PAC learning implies finite Littlestone dimension. In STOC.","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_3_1","unstructured":"Borja Balle Gilles Barthe and Marco Gaboardi. 2018. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In NeurIPS. 6280\u20136290. \t\t\t\t  Borja Balle Gilles Barthe and Marco Gaboardi. 2018. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In NeurIPS. 6280\u20136290."},{"key":"e_1_3_2_1_4_1","volume-title":"Shiva Prasad Kasiviswanathan, and Kobbi Nissim","author":"Beimel Amos","year":"2010","unstructured":"Amos Beimel , Shiva Prasad Kasiviswanathan, and Kobbi Nissim . 2010 . Bounds on the Sample Complexity for Private Learning and Private Data Release. In TCC. Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. 2010. Bounds on the Sample Complexity for Private Learning and Private Data Release. In TCC."},{"key":"e_1_3_2_1_5_1","unstructured":"Amos Beimel Shay Moran Kobbi Nissim and Uri Stemmer. 2019. Private Center Points and Learning of Halfspaces. In COLT. \t\t\t\t  Amos Beimel Shay Moran Kobbi Nissim and Uri Stemmer. 2019. Private Center Points and Learning of Halfspaces. In COLT."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Amos Beimel Kobbi Nissim and Uri Stemmer. 2013. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. In APPROX-RANDOM. \t\t\t\t  Amos Beimel Kobbi Nissim and Uri Stemmer. 2013. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. In APPROX-RANDOM.","DOI":"10.1007\/978-3-642-40328-6_26"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Cynthia Dwork Guy N. Rothblum and Thomas Steinke. 2018. Composable and versatile privacy via truncated CDP. In STOC. \t\t\t\t  Mark Bun Cynthia Dwork Guy N. Rothblum and Thomas Steinke. 2018. Composable and versatile privacy via truncated CDP. In STOC.","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_3_2_1_8_1","volume-title":"Vadhan","author":"Bun Mark","year":"2015","unstructured":"Mark Bun , Kobbi Nissim , Uri Stemmer , and Salil P . Vadhan . 2015 . Differentially Private Release and Learning of Threshold Functions. In FOCS. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. 2015. Differentially Private Release and Learning of Threshold Functions. In FOCS."},{"key":"e_1_3_2_1_9_1","volume-title":"Hsu","author":"Chaudhuri Kamalika","year":"2011","unstructured":"Kamalika Chaudhuri and Daniel J . Hsu . 2011 . Sample Complexity Bounds for Differentially Private Learning. In COLT. Kamalika Chaudhuri and Daniel J. Hsu. 2011. Sample Complexity Bounds for Differentially Private Learning. In COLT."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Frank McSherry Kobbi Nissim and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC. \t\t\t\t  Cynthia Dwork Frank McSherry Kobbi Nissim and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC.","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Dan Feldman Chongyuan Xiang Ruihao Zhu and Daniela Rus. 2017. Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In IPSN. \t\t\t\t  Dan Feldman Chongyuan Xiang Ruihao Zhu and Daniela Rus. 2017. Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In IPSN.","DOI":"10.1145\/3055031.3055090"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/140991844"},{"key":"e_1_3_2_1_13_1","unstructured":"Yue Gao and Or Sheffet. 2021. Differentially Private Approximations of a Convex Hull in Low Dimensions. In ITC. \t\t\t\t  Yue Gao and Or Sheffet. 2021. Differentially Private Approximations of a Convex Hull in Low Dimensions. In ITC."},{"key":"#cr-split#-e_1_3_2_1_14_1.1","unstructured":"Svante Janson. 2017. Tail bounds for sums of geometric and exponential variables. https:\/\/doi.org\/10.48550\/ARXIV.1709.08157 10.48550\/ARXIV.1709.08157"},{"key":"#cr-split#-e_1_3_2_1_14_1.2","doi-asserted-by":"crossref","unstructured":"Svante Janson. 2017. Tail bounds for sums of geometric and exponential variables. https:\/\/doi.org\/10.48550\/ARXIV.1709.08157","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"e_1_3_2_1_15_1","unstructured":"Peter Kairouz Sewoong Oh and Pramod Viswanath. 2015. The Composition Theorem for Differential Privacy. In ICML. \t\t\t\t  Peter Kairouz Sewoong Oh and Pramod Viswanath. 2015. The Composition Theorem for Differential Privacy. In ICML."},{"key":"e_1_3_2_1_16_1","unstructured":"Haim Kaplan Katrina Ligett Yishay Mansour Moni Naor and Uri Stemmer. 2020. Privately Learning Thresholds: Closing the Exponential Gap. In COLT. \t\t\t\t  Haim Kaplan Katrina Ligett Yishay Mansour Moni Naor and Uri Stemmer. 2020. Privately Learning Thresholds: Closing the Exponential Gap. In COLT."},{"key":"e_1_3_2_1_17_1","unstructured":"Haim Kaplan Yishay Mansour Uri Stemmer and Eliad Tsfadia. 2020. Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity. In NeurIPS. \t\t\t\t  Haim Kaplan Yishay Mansour Uri Stemmer and Eliad Tsfadia. 2020. Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity. In NeurIPS."},{"key":"e_1_3_2_1_18_1","volume-title":"Smith","author":"Kasiviswanathan Shiva Prasad","year":"2008","unstructured":"Shiva Prasad Kasiviswanathan , Homin K. Lee , Kobbi Nissim , Sofya Raskhodnikova , and Adam D . Smith . 2008 . What Can We Learn Privately? In FOCS. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. 2008. What Can We Learn Privately? In FOCS."},{"key":"e_1_3_2_1_19_1","volume-title":"Vadhan","author":"Murtagh Jack","year":"2016","unstructured":"Jack Murtagh and Salil P . Vadhan . 2016 . The Complexity of Computing the Optimal Composition of Differential Privacy. In TCC (A 1). Jack Murtagh and Salil P. Vadhan. 2016. The Complexity of Computing the Optimal Composition of Differential Privacy. In TCC (A1)."},{"key":"e_1_3_2_1_20_1","volume-title":"Vadhan","author":"Nissim Kobbi","year":"2016","unstructured":"Kobbi Nissim , Uri Stemmer , and Salil P . Vadhan . 2016 . Locating a Small Cluster Privately. In PODS. Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. 2016. Locating a Small Cluster Privately. In PODS."},{"key":"e_1_3_2_1_21_1","unstructured":"Menachem Sadigurschi and Uri Stemmer. 2021. On the Sample Complexity of Privately Learning Axis-Aligned Rectangles. In NeurIPS. \t\t\t\t  Menachem Sadigurschi and Uri Stemmer. 2021. On the Sample Complexity of Privately Learning Axis-Aligned Rectangles. In NeurIPS."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_23_1","volume-title":"Chervonenkis","author":"Vapnik V. N.","year":"1971","unstructured":"V. N. Vapnik and A. Ya . Chervonenkis . 1971 . On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications , 16, 2 (1971), 264\u2013280. V. N. Vapnik and A. Ya. Chervonenkis. 1971. On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications, 16, 2 (1971), 264\u2013280."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585148","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":24,"alternative-id":["10.1145\/3564246.3585148","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585148","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}