{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:51:55Z","timestamp":1744217515977,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_82","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"1010-1021","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Private Mechanism for Small Databases"],"prefix":"10.1007","author":[{"given":"Aleksandar","family":"Nikolov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"82_CR1","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 Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 609\u2013618. ACM, New York (2008)","DOI":"10.1145\/1374376.1374464"},{"issue":"2","key":"82_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF02772174","volume":"57","author":"J Bourgain","year":"1987","unstructured":"Bourgain, J., Tzafriri, L.: Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis. Israel journal of mathematics 57(2), 137\u2013224 (1987)","journal-title":"Israel journal of mathematics"},{"key":"82_CR3","doi-asserted-by":"crossref","unstructured":"Bun, M., Ullman, J., Vadhan, S.: Fingerprinting codes and the price of approximate differential privacy (2013). arXiv preprint arXiv:1311.3158","DOI":"10.1145\/2591796.2591877"},{"key":"82_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-642-14162-1_34","volume-title":"Automata, Languages and Programming","author":"T-H Hubert Chan","year":"2010","unstructured":"Hubert Chan, T.-H., Shi, E., Song, D.: Private and continual release of statistics. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 405\u2013417. Springer, Heidelberg (2010)"},{"key":"82_CR5","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: Privacy via distributed noise generation 4004, 486\u2013503 (2006)","DOI":"10.1007\/11761679_29"},{"key":"82_CR6","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. 3876, pp. 265\u2013284. Springer, Heidelberg (2006)"},{"key":"82_CR7","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Talwar, K.: The price of privacy and the limits of lp decoding. In: STOC, pp. 85\u201394 (2007)","DOI":"10.1145\/1250790.1250804"},{"key":"82_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy, pp. 202\u2013210 (2003)","DOI":"10.1145\/773153.773173"},{"key":"82_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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. 3152, pp. 528\u2013544. Springer, Heidelberg (2004)"},{"key":"82_CR10","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Pitassi, T., Rothblum, G.N.: Differential privacy under continual observation. In: Schulman, L.J. (eds.) STOC, pp. 715\u2013724. ACM (2010)","DOI":"10.1145\/1806689.1806787"},{"key":"82_CR11","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 Annual ACM Symposium on Theory of computing, pp. 381\u2013390. ACM (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"82_CR12","doi-asserted-by":"crossref","unstructured":"Dwork, C., Nikolov, A., Talwar, K.: Using convex relaxations for efficiently and privately releasing marginals. In: Cheng, S.-W., Devillers, O. (eds.) 30th Annual Symposium on Computational Geometry, SOCG 2014, Kyoto, Japan, June 08\u201311, 2014, pp. 261. ACM (2014)","DOI":"10.1145\/2582112.2582123"},{"key":"82_CR13","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.: Boosting and differential privacy. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 51\u201360. IEEE Computer Society, Washington (2010)","DOI":"10.1109\/FOCS.2010.12"},{"key":"82_CR14","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 (2011)","DOI":"10.1145\/1993636.1993742"},{"key":"82_CR15","doi-asserted-by":"crossref","unstructured":"Ganta, S.R., Kasiviswanathan, S.P., Smith, A.: Composition attacks and auxiliary information in data privacy. In: Li, Y., Liu, B., Sarawagi, S. (eds.) Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, August 24\u201327, 2008, pp. 265\u2013273. ACM (2008)","DOI":"10.1145\/1401890.1401926"},{"issue":"2","key":"82_CR16","doi-asserted-by":"publisher","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":"82_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-28914-9_19","volume-title":"Theory of Cryptography","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Roth, A., Ullman, J.: Iterative constructions and private data release. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 339\u2013356. Springer, Heidelberg (2012)"},{"key":"82_CR18","unstructured":"Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release. In: NIPS (2012, to appear)"},{"key":"82_CR19","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.: A multiplicative weights mechanism for privacy-preserving data analysis. In: Proc. 51st Foundations of Computer Science (FOCS). IEEE (2010)","DOI":"10.1109\/FOCS.2010.85"},{"key":"82_CR20","doi-asserted-by":"crossref","unstructured":"Kasiviswanathan, S.P., 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 (2010)","DOI":"10.1145\/1806689.1806795"},{"key":"82_CR21","unstructured":"Muthukrishnan, S., Nikolov, A.: Optimal private halfspace counting via discrepancy. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19\u201322, 2012, pp. 1285\u20131292. ACM (2012)"},{"key":"82_CR22","doi-asserted-by":"crossref","unstructured":"Nikolov, A.: Randomized rounding for the largest \n$$j$$\n-simplex problem. In: STOC 2015 (2015, to appear)","DOI":"10.1145\/2746539.2746628"},{"key":"82_CR23","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Talwar, K.: Approximating hereditary discrepancy via small width ellipsoids. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 324\u2013336. SIAM (2015)","DOI":"10.1137\/1.9781611973730.24"},{"key":"82_CR24","unstructured":"Nikolov, A., Talwar, K., Zhang, L.: The geometry of differential privacy: the sparse and approximate cases. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 351\u2013360. ACM (2013)"},{"issue":"2, Ser. B","key":"82_CR25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF01585173","volume":"62","author":"ML Overton","year":"1993","unstructured":"Overton, M.L., Womersley, R.S.: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices. Math. Programming 62(2, Ser. B), 321\u2013357 (1993)","journal-title":"Math. Programming"},{"key":"82_CR26","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 2010, pp. 765\u2013774. ACM, New York (2010)","DOI":"10.1145\/1806689.1806794"},{"key":"82_CR27","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Srivastava, N.: An elementary proof of the restricted invertibility theorem. Israel Journal of Mathematics, 1\u20139 (2010)","DOI":"10.1007\/s11856-011-0194-2"},{"key":"82_CR28","unstructured":"Ullman, J.: Answering \n$$n^{2+o(1)}$$\n counting queries with differential privacy is hard. In: STOC (2013)"},{"key":"82_CR29","doi-asserted-by":"crossref","unstructured":"Xiao, X., Wang, G., Gehrke, J.: Differential privacy via wavelet transforms. In: ICDE, pp. 225\u2013236 (2010)","DOI":"10.1109\/ICDE.2010.5447831"},{"key":"82_CR30","doi-asserted-by":"crossref","unstructured":"Zhang, L.: Nearly optimal minimax estimator for high dimensional sparse linear regression. Annals of Statistics (2013, to appear)","DOI":"10.1214\/13-AOS1141"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_82","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:44:17Z","timestamp":1676018657000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_82","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}