{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:58:56Z","timestamp":1764403136270,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T00:00:00Z","timestamp":1644969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T00:00:00Z","timestamp":1644969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["1702760","1931686"],"award-info":[{"award-number":["1702760","1931686"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s00778-022-00728-2","type":"journal-article","created":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T14:02:46Z","timestamp":1645020166000},"page":"23-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1132-7079","authenticated-orcid":false,"given":"Zeyu","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingtai","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guanhong","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danfeng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Kifer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,16]]},"reference":[{"key":"728_CR1","doi-asserted-by":"crossref","unstructured":"Abadi, M., Chu, A., Goodfellow, I., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: CCS (2016)","DOI":"10.1145\/2976749.2978318"},{"key":"728_CR2","doi-asserted-by":"crossref","unstructured":"Abowd, J.M.: The us census bureau adopts differential privacy. In: KDD (2018)","DOI":"10.1145\/3219819.3226070"},{"key":"728_CR3","doi-asserted-by":"crossref","unstructured":"Albarghouthi, A., Hsu, J.: Synthesizing coupling proofs of differential privacy. In: POPL (2017)","DOI":"10.1145\/3158146"},{"key":"728_CR4","doi-asserted-by":"crossref","unstructured":"Barthe, G., Gaboardi, M., Gregoire, B., Hsu, J., Strub, P.Y.: Proving differential privacy via probabilistic couplings. In: LICS (2016)","DOI":"10.1145\/2933575.2934554"},{"issue":"1","key":"728_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a001","volume":"12","author":"A Beimel","year":"2016","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: pure vs. approximate differential privacy. Theory Comput. 12(1), 1\u201361 (2016)","journal-title":"Theory Comput."},{"key":"728_CR6","doi-asserted-by":"crossref","unstructured":"Bhaskar, R., Laxman, S., Smith, A., Thakurta, A.: Discovering frequent patterns in sensitive data. In: KDD (2010)","DOI":"10.1145\/1835804.1835869"},{"key":"728_CR7","doi-asserted-by":"crossref","unstructured":"Bittau, A., Erlingsson, U., Maniatis, P., Mironov, I., Raghunathan, A., Lie, D., Rudominer, M., Kode, U., Tinnes, J., Seefeld, B.: Prochlo: strong privacy for analytics in the crowd. In: SOSP (2017)","DOI":"10.1145\/3132747.3132769"},{"key":"728_CR8","doi-asserted-by":"crossref","unstructured":"Bun, M., Steinke, T.: Concentrated differential privacy: simplifications, extensions, and lower bounds. In: TCC (2016)","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"728_CR9","unstructured":"Bureau, U.S.C.: On the map: longitudinal employer-household dynamics. https:\/\/lehd.ces.census.gov\/applications\/help\/onthemap.html#!confidentiality_protection"},{"key":"728_CR10","unstructured":"Chaudhuri, K., Hsu, D., Song, S.: The large margin mechanism for differentially private maximization. In: NIPS (2014)"},{"issue":"Mar","key":"728_CR11","first-page":"1069","volume":"12","author":"K Chaudhuri","year":"2011","unstructured":"Chaudhuri, K., Monteleoni, C., Sarwate, A.D.: Differentially private empirical risk minimization. J. Mach. Learn. Res. 12(Mar), 1069\u20131109 (2011)","journal-title":"J. Mach. Learn. Res."},{"key":"728_CR12","doi-asserted-by":"crossref","unstructured":"Chen, Y., Machanavajjhala, A., Reiter, J.P., Barrientos, A.F.: Differentially private regression diagnostics. In: ICDM (2016)","DOI":"10.1109\/ICDM.2016.0019"},{"key":"728_CR13","unstructured":"Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: NIPS (2017)"},{"key":"728_CR14","doi-asserted-by":"crossref","unstructured":"Ding, Z., Wang, Y., Zhang, D., Kifer, D.: Free gap information from the differentially private sparse vector and noisy max mechanisms. In: PVLDB (2019)","DOI":"10.14778\/3368289.3368295"},{"key":"728_CR15","doi-asserted-by":"crossref","unstructured":"Dwork, C.: Differential privacy. In: ICALP (2006)","DOI":"10.1007\/11787006_1"},{"key":"728_CR16","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: privacy via distributed noise generation. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486\u2013503. Springer (2006)","DOI":"10.1007\/11761679_29"},{"key":"728_CR17","doi-asserted-by":"crossref","unstructured":"Dwork, C., Lei, J.: Differential privacy and robust statistics. In: STOC (2009)","DOI":"10.1145\/1536414.1536466"},{"key":"728_CR18","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of Cryptography Conference. Springer (2006)","DOI":"10.1007\/11681878_14"},{"issue":"3\u20134","key":"728_CR19","first-page":"211","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3\u20134), 211\u2013407 (2014)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"728_CR20","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., Thakurta, A.: Amplification by shuffling: from local to central differential privacy via anonymity. In: SODA (2019)","DOI":"10.1137\/1.9781611975482.151"},{"key":"728_CR21","doi-asserted-by":"crossref","unstructured":"Erlingsson, \u00da., Pihur, V., Korolova, A.: Rappor: Randomized aggregatable privacy-preserving ordinal response. In: CCS (2014)","DOI":"10.1145\/2660267.2660348"},{"key":"728_CR22","doi-asserted-by":"crossref","unstructured":"Fanaeepour, M., Rubinstein, B.I.P.: Histogramming privately ever after: Differentially-private data-dependent error bound optimisation. In: ICDE (2018)","DOI":"10.1109\/ICDE.2018.00111"},{"key":"728_CR23","doi-asserted-by":"crossref","unstructured":"Geng, Q., Viswanath, P.: The optimal mechanism in differential privacy. In: ISIT (2014)","DOI":"10.1109\/ISIT.2014.6875258"},{"key":"728_CR24","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Roughgarden, T., Sundararajan, M.: Universally utility-maximizing privacy mechanisms. In: STOC. pp. 351\u2013360 (2009)","DOI":"10.1145\/1536414.1536464"},{"key":"728_CR25","series-title":"Applied Mathematics Series","volume-title":"Statistical Theory of Extreme Values and Some Practical Applications: A Series of Lectures","author":"E Gumbel","year":"1954","unstructured":"Gumbel, E.: Statistical Theory of Extreme Values and Some Practical Applications: A Series of Lectures. Applied Mathematics Series, U.S. Government Printing Office, Washington (1954)"},{"key":"728_CR26","doi-asserted-by":"crossref","unstructured":"Haney, S., Machanavajjhala, A., Abowd, J.M., Graham, M., Kutzbach, M., Vilhuber, L.: Utility cost of formal privacy for releasing national employer\u2013employee statistics. In: SIGMOD (2017)","DOI":"10.1145\/3035918.3035940"},{"key":"728_CR27","unstructured":"Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release. In: NIPS (2012)"},{"key":"728_CR28","doi-asserted-by":"crossref","unstructured":"Johnson, N., Near, J.P., Song, D.: Towards practical differential privacy for SQL queries. In: PVLDB (2018)","DOI":"10.1145\/3187009.3177733"},{"key":"728_CR29","doi-asserted-by":"crossref","unstructured":"Kotsogiannis, I., Machanavajjhala, A., Hay, M., Miklau, G.: Pythia: data dependent differentially private algorithm selection. In: SIGMOD (2017)","DOI":"10.1145\/3035918.3035945"},{"key":"728_CR30","volume-title":"Theory of Point Estimation","author":"E Lehmann","year":"1998","unstructured":"Lehmann, E., Casella, G.: Theory of Point Estimation. Springer, Berlin (1998)"},{"key":"728_CR31","unstructured":"Ligett, K., Neel, S., Roth, A., Waggoner, B., Wu, S.Z.: Accuracy first: selecting a differential privacy level for accuracy constrained ERM. In: NIPS (2017)"},{"key":"728_CR32","doi-asserted-by":"crossref","unstructured":"Liu, J., Talwar, K.: Private selection from private candidates (2018). arXiv preprint arXiv:1811.07971","DOI":"10.1145\/3313276.3316377"},{"key":"728_CR33","doi-asserted-by":"crossref","unstructured":"Lyu, M., Su, D., Li, N.: Understanding the sparse vector technique for differential privacy. In: PVLDB (2017)","DOI":"10.14778\/3055330.3055331"},{"key":"728_CR34","doi-asserted-by":"crossref","unstructured":"Machanavajjhala, A., Kifer, D., Abowd, J., Gehrke, J., Vilhuber, L.: Privacy: from theory to practice on the map. In: ICDE (2008)","DOI":"10.1109\/ICDE.2008.4497436"},{"key":"728_CR35","unstructured":"Maddison, C.J., Tarlow, D., Minka, T.: A$$\\ast $$ sampling. In: NIPS (2014)"},{"key":"728_CR36","doi-asserted-by":"crossref","unstructured":"McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS (2007)","DOI":"10.1109\/FOCS.2007.66"},{"key":"728_CR37","doi-asserted-by":"crossref","unstructured":"McSherry, F.D.: Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In: SIGMOD (2009)","DOI":"10.1145\/1559845.1559850"},{"key":"728_CR38","doi-asserted-by":"crossref","unstructured":"Mironov, I.: R\u00e9nyi differential privacy. In: 30th IEEE Computer Security Foundations Symposium. CSF (2017)","DOI":"10.1109\/CSF.2017.11"},{"key":"728_CR39","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)","edition":"2"},{"key":"728_CR40","unstructured":"Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., \u00dalfar Erlingsson: scalable private learning with pate. In: ICLR (2018)"},{"key":"728_CR41","doi-asserted-by":"crossref","unstructured":"Raskhodnikova, S., Smith, A.D.: Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.60"},{"key":"728_CR42","unstructured":"Tang, J., Korolova, A., Bai, X., Wang, X., Wang, X.: Privacy loss in apple\u2019s implementation of differential privacy. In: 3rd Workshop on the Theory and Practice of Differential Privacy at CCS (2017)"},{"issue":"8","key":"728_CR43","first-page":"1","volume":"1","author":"ADP Team","year":"2017","unstructured":"Team, A.D.P., Team: Learning with privacy at scale. Appl. Mach. Learn. J. 1(8), 1\u201325 (2017)","journal-title":"Appl. Mach. Learn. J."},{"key":"728_CR44","unstructured":"Thakurta, A.G., Smith, A.: Differentially private feature selection via stability arguments, and the robustness of the lasso. In: COLT (2013)"},{"key":"728_CR45","doi-asserted-by":"crossref","unstructured":"Wang, Y., Ding, Z., Wang, G., Kifer, D., Zhang, D.: Proving differential privacy with shadow execution. In: PLDI (2019)","DOI":"10.1145\/3314221.3314619"},{"key":"728_CR46","doi-asserted-by":"crossref","unstructured":"Zhang, D., Kifer, D.: Lightdp: towards automating differential privacy proofs. In: POPL (2017)","DOI":"10.1145\/3009837.3009884"},{"key":"728_CR47","doi-asserted-by":"crossref","unstructured":"Zhang, D., McKenna, R., Kotsogiannis, I., Hay, M., Machanavajjhala, A., Miklau, G.: Ektelo: A framework for defining differentially-private computations. In: SIGMOD (2018)","DOI":"10.1145\/3183713.3196921"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00728-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00728-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00728-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:08:34Z","timestamp":1673953714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00728-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,16]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["728"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00728-2","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2022,2,16]]},"assertion":[{"value":"30 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}