{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T15:53:28Z","timestamp":1783007608201,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1101389 and CNS-1065060"],"award-info":[{"award-number":["CCF-1101389 and CNS-1065060"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0514922 and CCF-0830540"],"award-info":[{"award-number":["CCF-0514922 and CCF-0830540"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008872","name":"Charles Lee Powell Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008872","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CCF-1101389 and CNS-1065060"],"award-info":[{"award-number":["CCF-1101389 and CNS-1065060"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>In this article, we demonstrate that, ignoring computational constraints, it is possible to release synthetic databases that are useful for accurately answering large classes of queries while preserving differential privacy. Specifically, we give a mechanism that privately releases synthetic data useful for answering a class of queries over a<jats:italic>discrete<\/jats:italic>domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. We show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows at most logarithmically with the size of the query class.<\/jats:p><jats:p>We also show that it is not possible to release even simple classes of queries (such as intervals and their generalizations) over<jats:italic>continuous<\/jats:italic>domains with worst-case utility guarantees while preserving differential privacy. In response to this, we consider a relaxation of the utility guarantee and give a privacy preserving polynomial time algorithm that for any halfspace query will provide an answer that is accurate for some small perturbation of the query. This algorithm does not release synthetic data, but instead another data structure capable of representing an answer for each query. We also give an efficient algorithm for releasing synthetic data for the class of interval queries and axis-aligned rectangles of constant dimension over<jats:italic>discrete<\/jats:italic>domains.<\/jats:p>","DOI":"10.1145\/2450142.2450148","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":148,"title":["A learning theory approach to noninteractive database privacy"],"prefix":"10.1145","volume":"60","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katrina","family":"Ligett","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadephia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anthony M. and Bartlett P. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press. Anthony M. and Bartlett P. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press.","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-7550-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_2_1_6_1","unstructured":"Dasgupta S. and Gupta A. 1999. An elementary proof of the Johnson-Lindenstrauss Lemma. Tech. rep. 99-006 International Science Institute. Dasgupta S. and Gupta A. 1999. An elementary proof of the Johnson-Lindenstrauss Lemma. Tech. rep. 99-006 International Science Institute."},{"key":"e_1_2_1_7_1","volume-title":"Lower bounds in differential privacy. arXiv:1107.2183","author":"De A.","year":"2011","unstructured":"De , A. 2011. Lower bounds in differential privacy. arXiv:1107.2183 ( 2011 ). De, A. 2011. Lower bounds in differential privacy. arXiv:1107.2183 (2011)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250804"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Dwork C. and Nissim K. 2004. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of CRYPTO. Lecture Notes in Computer Science Springer 528--544. Dwork C. and Nissim K. 2004. Privacy-preserving datamining on vertically partitioned databases. In Proceedings of CRYPTO. Lecture Notes in Computer Science Springer 528--544.","DOI":"10.1007\/978-3-540-28628-8_32"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_26"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993742"},{"key":"e_1_2_1_18_1","unstructured":"Gupta A. Roth A. and Ullman J. 2011b. Iterative constructions and private data release. arXiv:1107.3731. Gupta A. Roth A. and Ullman J. 2011b. Iterative constructions and private data release. arXiv:1107.3731."},{"key":"e_1_2_1_19_1","unstructured":"Hardt M. Ligett K. and McSherry F. 2012. A simple and practical algorithm for differentially private data release. arXiv:1012.4763. Hardt M. Ligett K. and McSherry F. 2012. A simple and practical algorithm for differentially private data release. arXiv:1012.4763."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Hardt M. Rothblum G. N. and Servedio R. A. 2011. Private data release via learning thresholds. arXiv:1107.2444. Hardt M. Rothblum G. N. and Servedio R. A. 2011. Private data release via learning thresholds. arXiv:1107.2444.","DOI":"10.1137\/1.9781611973099.15"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of VLDB.","author":"Hay M.","unstructured":"Hay , M. , Rastogi , V. , Miklau , G. , and Suciu , D . 2010. Boosting the accuracy of differentially-private queries through consistency . In Proceedings of VLDB. Hay, M., Rastogi, V., Miklau, G., and Suciu, D. 2010. Boosting the accuracy of differentially-private queries through consistency. In Proceedings of VLDB."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806795"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807104"},{"key":"e_1_2_1_27_1","unstructured":"Li C. and Miklau G. 2011. Efficient batch query answering under differential privacy. CoRR abs\/1103.1367 (2011). Li C. and Miklau G. 2011. Efficient batch query answering under differential privacy. CoRR abs\/1103.1367 (2011)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"e_1_2_1_29_1","unstructured":"Li C. and Miklau G. 2012b. Measuring the achievable error of query sets under differential privacy. CoRR abs\/1202.3399v2. Li C. and Miklau G. 2012b. Measuring the achievable error of query sets under differential privacy. CoRR abs\/1202.3399v2."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214090"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886574"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Smola A. J. and Sch\u00f6lkopf B. 2002. Learning with Kernels. MIT Press. Smola A. J. and Sch\u00f6lkopf B. 2002. Learning with Kernels. MIT Press.","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of TCC. 400--416","author":"Ullman J.","unstructured":"Ullman , J. and Vadhan , S. P . 2011. PCPs and the hardness of generating private synthetic data . In Proceedings of TCC. 400--416 . Ullman, J. and Vadhan, S. P. 2011. PCPs and the hardness of generating private synthetic data. In Proceedings of TCC. 400--416."},{"key":"e_1_2_1_36_1","volume-title":"Statistical Learning Theory","author":"Vapnik V. N.","unstructured":"Vapnik , V. N. 1998. Statistical Learning Theory . Wiley . Vapnik, V. N. 1998. Statistical Learning Theory. Wiley."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450148","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450142.2450148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:49Z","timestamp":1750234729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450142.2450148"],"URL":"https:\/\/doi.org\/10.1145\/2450142.2450148","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}