{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:43:10Z","timestamp":1755999790472,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642195709"},{"type":"electronic","value":"9783642195716"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19571-6_24","type":"book-chapter","created":{"date-parts":[[2011,3,22]],"date-time":"2011-03-22T12:04:42Z","timestamp":1300795482000},"page":"400-416","source":"Crossref","is-referenced-by-count":30,"title":["PCPs and the Hardness of Generating Private Synthetic Data"],"prefix":"10.1007","author":[{"given":"Jonathan","family":"Ullman","sequence":"first","affiliation":[]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1145\/76894.76895","volume":"21","author":"N.R. Adam","year":"1989","unstructured":"Adam, N.R., Wortmann, J.: Security-control methods for statistical databases: A comparative study. ACM Computing Surveys\u00a021, 515\u2013556 (1989)","journal-title":"ACM Computing Surveys"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M. Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A.R., Pitassi, T.: The complexity of properly learning simple concept classes. J. Comput. Syst. Sci.\u00a074, 16\u201334 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., Talwar, K.: Privacy, accuracy, and consistency too: A holistic solution to contingency table release. In: Proceedings of the 26th Symposium on Principles of Database Systems, pp. 273\u2013282 (2007)","DOI":"10.1145\/1265530.1265569"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B. Barak","year":"2008","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput.\u00a038, 1661\u20131694 (2008)","journal-title":"SIAM J. Comput."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: The SuLQ framework. In: Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (June 2005)","DOI":"10.1145\/1065167.1065184"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: Proceedings of the 40th ACM SIGACT Symposium on Thoery of Computing (2008)","DOI":"10.1145\/1374376.1374464"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 202\u2013210 (2003)","DOI":"10.1145\/773153.773173"},{"key":"24_CR8","volume-title":"International Encyclopedia of the Social and Behavioral Sciences","author":"G. Duncan","year":"2001","unstructured":"Duncan, G.: Confidentiality and statistical disclosure limitation. In: International Encyclopedia of the Social and Behavioral Sciences. Elsevier, Amsterdam (2001)"},{"key":"24_CR9","unstructured":"Dwork, C.: A firm foundation for private data analysis. Communications of the ACM (to appear)"},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11787006_1","volume-title":"Automata, Languages and Programming","author":"C. Dwork","year":"2006","unstructured":"Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol.\u00a04052, pp. 1\u201312. Springer, Heidelberg (2006)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Theory of Cryptography","author":"C. Dwork","year":"2006","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 265\u2013284. Springer, Heidelberg (2006)"},{"key":"24_CR12","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G., Vadhan, S.: When and how can privacy-preserving data release be done efficiently? In: Proceedings of the 2009 International ACM Symposium on Theory of Computing (STOC) (2009)"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1007\/978-3-540-28628-8_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"C. Dwork","year":"2004","unstructured":"Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 528\u2013544. Springer, Heidelberg (2004)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G., Vadhan, S.P.: Boosting and differential privacy. In: Proceedings of FOCS 2010 (2010)","DOI":"10.1109\/FOCS.2010.12"},{"key":"24_CR15","unstructured":"Evfimievski, A., Grandison, T.: Privacy Preserving Data Mining (a short survey). In: Encyclopedia of Database Technologies and Applications. Information Science Reference (2006)"},{"key":"24_CR16","volume-title":"The Encyclopedia of Algorithms","author":"V. Feldman","year":"2008","unstructured":"Feldman, V.: Hardness of proper learning. In: The Encyclopedia of Algorithms. Springer, Heidelberg (2008)"},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.jcss.2008.07.007","volume":"75","author":"V. Feldman","year":"2009","unstructured":"Feldman, V.: Hardness of approximate two-level logic minimization and PAC learning with membership queries. Journal of Computer and System Sciences\u00a075(1), 13\u201326 (2009), \n                    \n                      http:\/\/dx.doi.org\/10.1016\/j.jcss.2008.07.007","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography, vol.\u00a02. Cambridge University Press, Cambridge (2004)"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM.\u00a048, 798\u2013859 (2001)","journal-title":"J. ACM."},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M.J. Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning boolean formulae and finite automata. J. ACM.\u00a041, 67\u201395 (1994)","journal-title":"J. ACM."},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC (1992)","DOI":"10.1145\/129712.129782"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S. Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput.\u00a030, 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC, pp. 33\u201343 (1989)","DOI":"10.1145\/73007.73011"},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM\u00a035, 965\u2013984 (1988)","journal-title":"J. ACM"},{"key":"24_CR25","unstructured":"Reiter, J.P., Drechsler, J.: Releasing multiply-imputed synthetic data generated in two stages to protect confidentiality. Iab discussion paper, Intitut f\u00fcr Arbeitsmarkt und Berufsforschung (IAB), N\u00fcrnberg, Institute for Employment Research, Nuremberg, Germany (2007), \n                    \n                      http:\/\/ideas.repec.org\/p\/iab\/iabdpa\/200720.html"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387\u2013394 (1990)","DOI":"10.1145\/100216.100269"},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"Roth, A., Roughgarden, T.: Interactive privacy via the median mechanism. In: STOC 2010 (2010)","DOI":"10.1145\/1806689.1806794"},{"key":"24_CR28","first-page":"17","volume":"17","author":"J. Ullman","year":"2010","unstructured":"Ullman, J., Vadhan, S.P.: PCPs and the hardness of generating synthetic data. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 17 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"11","key":"24_CR29","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19571-6_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:24Z","timestamp":1606186104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19571-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642195709","9783642195716"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19571-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}