{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:14:13Z","timestamp":1778807653627,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00454-015-9678-x","type":"journal-article","created":{"date-parts":[[2015,4,23]],"date-time":"2015-04-23T19:54:11Z","timestamp":1429818851000},"page":"650-673","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations"],"prefix":"10.1007","volume":"53","author":[{"given":"Cynthia","family":"Dwork","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,24]]},"reference":[{"key":"9678_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck\u2019s inequality. In: ACM Symposium on Theory of Computing, pp. 72\u201380. ACM Press, New York (2004)","DOI":"10.1145\/1007352.1007371"},{"key":"9678_CR2","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: Libkin, L. (ed.) Proceedings of ACM PODS, pp. 273\u2013282. ACM Press, New York (2007)","DOI":"10.1145\/1265530.1265569"},{"key":"9678_CR3","doi-asserted-by":"crossref","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: STOC \u201908: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 609\u2013618. ACM Press, New York (2008)","DOI":"10.1145\/1374376.1374464"},{"key":"9678_CR4","doi-asserted-by":"crossref","unstructured":"Bun, M., Ullman, J., Vadhan, S.: Fingerprinting codes and the price of approximate differential privacy. arXiv preprint http:\/\/arxiv.org\/abs\/1311.3158 (2013)","DOI":"10.1145\/2591796.2591877"},{"issue":"2","key":"9678_CR5","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1006\/jcss.2000.1726","volume":"62","author":"SR Buss","year":"2001","unstructured":"Buss, S.R., Grigoriev, D., Impagliazzo, R., Pitassi, T.: Linear gaps between degrees for the polynomial calculus modulo distinct primes. J. Comput. Syst. Sci. 62(2), 267\u2013289 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9678_CR6","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Thaler, J., Ullman, J., Wan, A.: Faster private release of marginals on small databases. CoRR http:\/\/arxiv.org\/abs\/1304.3754 (2013)","DOI":"10.1145\/2554797.2554833"},{"key":"9678_CR7","doi-asserted-by":"crossref","unstructured":"Cheraghchi, M., Klivans, A., Kothari, P., Lee, H.K.: Submodular functions are noise stable. In: SODA \u201912 Proceedings of the Twenty-Third Annual ACM\u2013SIAM. Symposium on Discrete Algorithms (SODA), pp. 1586\u20131592 (2012)","DOI":"10.1137\/1.9781611973099.126"},{"issue":"4","key":"9678_CR8","first-page":"63","volume":"6","author":"K Clarkson","year":"2010","unstructured":"Clarkson, K.: Coresets, sparse greedy approximation, and the Frank\u2013Wolfe algorithm. ACM Trans. Algorithms (TALG) 6(4), 63 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9678_CR9","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22, 60\u201365 (2003)","DOI":"10.1002\/rsa.10073"},{"key":"9678_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Proceedings of 22nd ACM Symposium on Principles of Database Systems, pp. 202\u2013210. ACM Press, New York (2003)","DOI":"10.1145\/773153.773173"},{"key":"9678_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)"},{"key":"9678_CR12","doi-asserted-by":"crossref","unstructured":"Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Advances in Cryptology, CRYPTO\u201904. Lecture Notes in Computer Science, vol. 3152, pp. 528\u2013544. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-28628-8_32"},{"key":"9678_CR13","doi-asserted-by":"crossref","unstructured":"Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Theor. Comput. Sci. 9(3\u20134), 211\u2013407 (2013)","DOI":"10.1561\/0400000042"},{"key":"9678_CR14","doi-asserted-by":"crossref","unstructured":"Dwork, C., Mcsherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) Theory of Cryptography. Lecture Notes in Computer Science, vol. 3876, pp. 265\u2013284. Springer, Berlin Heidelberg (2006)","DOI":"10.1007\/11681878_14"},{"key":"9678_CR15","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: privacy via distributed noise generation. In: Vaudena, S. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4004, pp. 486\u2013503. Springer, Heidelberg (2006)","DOI":"10.1007\/11761679_29"},{"key":"9678_CR16","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: Proceedings of the 41st ACM Symposium on Theory of Computing, pp. 381\u2013390. ACM Press, New York (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"9678_CR17","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 51\u201360. IEEE, Las Vegas (2010)","DOI":"10.1109\/FOCS.2010.12"},{"issue":"1\u20132","key":"9678_CR18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Nav. Res. Logist. Q."},{"issue":"1\u20132","key":"9678_CR19","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theor. Comput. Sci. 259(1\u20132), 613\u2013622 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u201379","key":"9678_CR20","first-page":"88","volume":"8","author":"A Grothendieck","year":"1953","unstructured":"Grothendieck, A.: R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. Sao Paulo 8(1\u201379), 88 (1953)","journal-title":"Bol. Soc. Mat. Sao Paulo"},{"issue":"2","key":"9678_CR21","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"9678_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hardt, M., Roth, A., Ullman, J.: Privately releasing conjunctions and the statistical query barrier. In: STOC, pp. 803\u2013812. ACM Press, New York (2011)","DOI":"10.1145\/1993636.1993742"},{"key":"9678_CR23","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.: A multiplicative weights mechanism for privacy-preserving data analysis. In: Proceedings of the 51st Foundations of Computer Science (FOCS). IEEE, Las Vegas (2010)","DOI":"10.1109\/FOCS.2010.85"},{"key":"9678_CR24","doi-asserted-by":"crossref","unstructured":"Hardt, M., Talwar, K.: On the geometry of differential privacy. In: Proceedings of the 42nd ACM Symposium on Theory of computing, STOC \u201910, pp. 705\u2013714. ACM Press, New York (2010)","DOI":"10.1145\/1806689.1806786"},{"key":"9678_CR25","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.N., Servedio, R.A.: Private data release via learning thresholds. In: Proceedings of the Twenty-Third Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA\u201912, pp. 168\u2013187. SIAM, Kyoto (2012). http:\/\/dl.acm.org\/citation.cfm?id=2095116.2095131","DOI":"10.1137\/1.9781611973099.15"},{"key":"9678_CR26","unstructured":"Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release. In: NIPS, pp. 2348\u20132356 (2012)"},{"key":"9678_CR27","doi-asserted-by":"crossref","unstructured":"Kasiviswanathan, S., Rudelson, M., Smith, A., Ullman, J.: The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In: Proceedings of the 42nd ACM symposium on Theory of computing, pp. 775\u2013784. ACM Press, New York (2010)","DOI":"10.1145\/1806689.1806795"},{"issue":"3","key":"9678_CR28","doi-asserted-by":"crossref","first-page":"275","DOI":"10.4064\/sm-29-3-275-326","volume":"29","author":"J Lindenstrauss","year":"1968","unstructured":"Lindenstrauss, J., Pe\u0142czy\u0144ski, A.: Absolutely summing operators in $$\\_ \\{p\\}$$ _ { p } -spaces and their applications. Stud. Math. 29(3), 275\u2013326 (1968)","journal-title":"Stud. Math."},{"key":"9678_CR29","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Talwar, K., Zhang, L.: The geometry of differential privacy: the sparse and approximate cases. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC \u201913, pp. 351\u2013360. ACM Press, New York (2013)","DOI":"10.1145\/2488608.2488652"},{"key":"9678_CR30","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: SODA, pp. 1537\u20131556. (2013)","DOI":"10.1137\/1.9781611973105.111"},{"key":"9678_CR31","doi-asserted-by":"crossref","unstructured":"Roth, A., Roughgarden, T.: Interactive privacy via the median mechanism. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC \u201910, pp. 765\u2013774. ACM Press, New York, (2010)","DOI":"10.1145\/1806689.1806794"},{"key":"9678_CR32","first-page":"810","volume":"1","author":"J Thaler","year":"2012","unstructured":"Thaler, J., Ullman, J., Vadhan, S.P.: Faster algorithms for privately releasing marginals. ICALP 1, 810\u2013821 (2012)","journal-title":"ICALP"},{"key":"9678_CR33","doi-asserted-by":"crossref","unstructured":"Ullman, J., Vadhan, S.: PCPs and the hardness of generating private synthetic data. In: Proceedings of the 8th Conference on Theory of Cryptography, TCC 2011, Providence, RI (2011)","DOI":"10.1007\/978-3-642-19571-6_24"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9678-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9678-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9678-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T23:11:44Z","timestamp":1651792304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9678-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9678"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9678-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}