{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T06:36:08Z","timestamp":1725690968881},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00145-020-09363-y","type":"journal-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T21:08:26Z","timestamp":1596229706000},"page":"2078-2112","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["PCPs and the Hardness of Generating Synthetic Data"],"prefix":"10.1007","volume":"33","author":[{"given":"Jonathan","family":"Ullman","sequence":"first","affiliation":[]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"key":"9363_CR1","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2007.04.011","volume":"74","author":"M Alekhnovich","year":"2008","unstructured":"M.\u00a0Alekhnovich, M.\u00a0Braverman, V.\u00a0Feldman, A.\u00a0R. Klivans, T.\u00a0Pitassi, The complexity of properly learning simple concept classes. in J. Comput. Syst. Sci., 74, 16\u201334, (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9363_CR2","doi-asserted-by":"crossref","unstructured":"L.\u00a0Babai, L.\u00a0Fortnow, L.A. Levin, M.\u00a0Szegedy, Checking computations in polylogarithmic time. in STOC, 21\u201331, (1991)","DOI":"10.1145\/103418.103428"},{"key":"9363_CR3","doi-asserted-by":"crossref","unstructured":"B.\u00a0Barak, K.\u00a0Chaudhuri, C.\u00a0Dwork, S.\u00a0Kale, F.\u00a0McSherry, K.\u00a0Talwar, 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":"9363_CR4","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B Barak","year":"2008","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich, Universal arguments and their applications. in SIAM J. Comput., vol 38, 1661\u20131694, (2008)","journal-title":"SIAM J. Comput."},{"key":"9363_CR5","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"E.\u00a0Ben-Sasson, O.\u00a0Goldreich, P.\u00a0Harsha, M.\u00a0Sudan, S.P. Vadhan, Robust pcps of proximity, shorter pcps, and applications to coding. in SIAM J. Comput., vol.\u00a036, pages 889\u2013974, (2006)","journal-title":"SIAM J. Comput."},{"key":"9363_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Blum, C.\u00a0Dwork, F.\u00a0McSherry, K.\u00a0Nissim, 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":"9363_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Blum, K.\u00a0Ligett, A.\u00a0Roth, 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":"9363_CR8","doi-asserted-by":"crossref","unstructured":"K.\u00a0Chandrasekaran, J.\u00a0Thaler, J.\u00a0Ullman, A.\u00a0Wan, Faster private release of marginals on small databases. in ITCS (ACM, New York, 2014), pp. 387\u2013402","DOI":"10.1145\/2554797.2554833"},{"key":"9363_CR9","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N Creignou","year":"1995","unstructured":"N.\u00a0Creignou, A dichotomy theorem for maximum generalized satisfiability problems. In J. Comput. Syst. Sci., volume\u00a051, pages 511\u2013522, (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9363_CR10","doi-asserted-by":"crossref","unstructured":"I.\u00a0Dinur, K.\u00a0Nissim, 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":"9363_CR11","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I Dinur","year":"2006","unstructured":"I.\u00a0Dinur, O.\u00a0Reingold, Assignment testers: Towards a combinatorial proof of the pcp theorem. in SIAM J. Comput., volume\u00a036, pages 975\u20131024, (2006)","journal-title":"SIAM J. Comput."},{"key":"9363_CR12","doi-asserted-by":"crossref","unstructured":"D.P. Dubhashi, S.\u00a0Sen, Concentration of measure for randomized algorithms: techniques and applications. in Handbook of Randomized Algorithms, (2001)","DOI":"10.1007\/978-1-4615-0013-1_3"},{"key":"9363_CR13","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, F.\u00a0McSherry, K.\u00a0Nissim, A.\u00a0Smith, Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference, pp. 265\u2013284, (2006)","DOI":"10.1007\/11681878_14"},{"key":"9363_CR14","unstructured":"C.\u00a0Dwork, M.\u00a0Naor, O.\u00a0Reingold, G.\u00a0Rothblum, S.\u00a0Vadhan, 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":"9363_CR15","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, A.\u00a0Nikolov, K.\u00a0Talwar, Using convex relaxations for efficiently and privately releasing marginals. in Proceedings of the thirtieth annual symposium on Computational geometry (ACM, New York, 2014), pp. 261","DOI":"10.1145\/2582112.2582123"},{"key":"9363_CR16","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, K.\u00a0Nissim, Privacy-preserving datamining on vertically partitioned databases. In Proceedings of CRYPTO 2004, vol. 3152, pp. 528\u2013544, (2004)","DOI":"10.1007\/978-3-540-28628-8_32"},{"key":"9363_CR17","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, A.\u00a0Roth, The algorithmic foundations of differential privacy, (2014)","DOI":"10.1561\/9781601988195"},{"key":"9363_CR18","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, G.\u00a0Rothblum, S.P. Vadhan, Boosting and differential privacy. in Proceedings of FOCS 2010, (2010)","DOI":"10.1109\/FOCS.2010.12"},{"key":"9363_CR19","doi-asserted-by":"crossref","unstructured":"V.\u00a0Feldman, Hardness of proper learning. in The Encyclopedia of Algorithms (Springer, New York, 2008)","DOI":"10.1007\/978-0-387-30162-4_177"},{"issue":"1","key":"9363_CR20","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.jcss.2008.07.007","volume":"75","author":"V Feldman","year":"2009","unstructured":"V.\u00a0Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries. Journal of Computer and System Sciences, 75(1):13\u201326, (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9363_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography","author":"O Goldreich","year":"2004","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography, volume\u00a02. Cambridge University Press, (2004)"},{"key":"9363_CR22","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hardt, G.N. Rothblum, R.A. Servedio, Private data release via learning thresholds. in SODA (SIAM, New York, 2012), pp. 168\u2013187","DOI":"10.1137\/1.9781611973099.15"},{"key":"9363_CR23","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"J.\u00a0H\u00e5stad, Some optimal inapproximability results. in J. ACM, volume\u00a048, pages 798\u2013859, (2001)","journal-title":"J. ACM"},{"issue":"2","key":"9363_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1109\/TIT.1976.1055516","volume":"22","author":"J Justesen","year":"1976","unstructured":"J.\u00a0Justesen, On the complexity of decoding reed-solomon codes (corresp). IEEE Trans. Inf. Theory 22(2):237\u2013238 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9363_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"MJ Kearns","year":"1994","unstructured":"M.J. Kearns, L.G. Valiant, Cryptographic limitations on learning boolean formulae and finite automata. in J. ACM, volume\u00a041, pages 67\u201395, (1994)","journal-title":"J. ACM"},{"key":"9363_CR26","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S Khanna","year":"2000","unstructured":"S.\u00a0Khanna, M.\u00a0Sudan, L.\u00a0Trevisan, D.P. Williamson, The approximability of constraint satisfaction problems. in SIAM J. Comput., vol.\u00a030, pp. 1863\u20131920, (2000)","journal-title":"SIAM J. Comput."},{"key":"9363_CR27","doi-asserted-by":"crossref","unstructured":"J.\u00a0Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract). in STOC, (1992)","DOI":"10.1145\/129712.129782"},{"key":"9363_CR28","doi-asserted-by":"crossref","unstructured":"V.\u00a0Lyubashevsky, D.\u00a0Micciancio, Asymptotically efficient lattice-based digital signatures. In R.\u00a0Canetti, editor, TCC, volume 4948 of Lecture Notes in Computer Science (Springer, Berlin, 2008), pp. 37\u201354","DOI":"10.1007\/978-3-540-78524-8_3"},{"key":"9363_CR29","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S Micali","year":"2000","unstructured":"S.\u00a0Micali, Computationally sound proofs. in SIAM J. Comput., volume\u00a030, pages 1253\u20131298, (2000)","journal-title":"SIAM J. Comput."},{"key":"9363_CR30","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, M.\u00a0Yung, Universal one-way hash functions and their cryptographic applications. in STOC, pp. 33\u201343, (1989)","DOI":"10.1145\/73007.73011"},{"key":"9363_CR31","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou, M.\u00a0Yannakakis, Optimization, approximation, and complexity classes. in J. Comput. Syst. Sci., volume\u00a043, pages 425\u2013440, (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9363_CR32","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L Pitt","year":"1988","unstructured":"L.\u00a0Pitt, L.G. Valiant, Computational limitations on learning from examples. in J. ACM, volume\u00a035, pages 965\u2013984, (1988)","journal-title":"J. ACM"},{"key":"9363_CR33","unstructured":"J.P. Reiter, J.\u00a0Drechsler, 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)"},{"key":"9363_CR34","doi-asserted-by":"crossref","unstructured":"J.\u00a0Rompel, One-way functions are necessary and sufficient for secure signatures. in STOC, pp. 387\u2013394, (1990)","DOI":"10.1145\/100216.100269"},{"key":"9363_CR35","doi-asserted-by":"crossref","unstructured":"A.\u00a0Roth, T.\u00a0Roughgarden, Interactive privacy via the median mechanism. in STOC 2010, (2010)","DOI":"10.1145\/1806689.1806794"},{"issue":"6","key":"9363_CR36","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1109\/18.556668","volume":"42","author":"DA Spielman","year":"1996","unstructured":"D.A. Spielman, Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723\u20131731, (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9363_CR37","doi-asserted-by":"crossref","unstructured":"J.\u00a0Thaler, J.\u00a0Ullman, S.P. Vadhan, Faster algorithms for privately releasing marginals. in ICALP (1) (Springer, Berlin, 2012), pp. 810\u2013821","DOI":"10.1007\/978-3-642-31594-7_68"},{"issue":"11","key":"9363_CR38","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"L.G. Valiant, A theory of the learnable. Communications of the ACM, 27(11):1134\u20131142, (1984)","journal-title":"Commun. ACM"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09363-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-020-09363-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09363-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T23:15:39Z","timestamp":1627686939000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-020-09363-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9363"],"URL":"https:\/\/doi.org\/10.1007\/s00145-020-09363-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"8 August 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}