×

zbMATH — the first resource for mathematics

The matching polytope has exponential extension complexity. (English) Zbl 1315.90038
Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 263-272 (2014).

MSC:
90C27 Combinatorial optimization
90C05 Linear programming
68W25 Approximation algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Software:
SuLQ
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., and Talwar, K. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In PODS (2007), pp. 273 282.
[2] Beimel, A., Kasiviswanathan, S. P., and Nissim, K. Bounds on the sample complexity for private learning and private data release. In TCC (2010), pp. 437 454. · Zbl 1274.94038
[3] Beimel, A., Nissim, K., and Stemmer, U. Characterizing the sample complexity of private learners. In ITCS (2013), pp. 97 110. · Zbl 1362.68119
[4] Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure vs. approximate di.erential privacy. In APPROX-RANDOM (2013), pp. 363 378. · Zbl 1332.68061
[5] Blum, A., Dwork, C., McSherry, F., and Nissim, K. Practical privacy: the SuLQ framework. In PODS (2005), pp. 128 138.
[6] Blum, A., Ligett, K., and Roth, A. A learning theory approach to non-interactive database privacy. In STOC (2008), pp. 609 618. · Zbl 1231.68120
[7] Boneh, D., Kiayias, A., and Montgomery, H. W. Robust .ngerprinting codes: a near optimal construction. In Digital Rights Management Workshop (2010), pp. 3 12.
[8] Boneh, D., and Naor, M. Traitor tracing with constant size ciphertext. In ACM Conference on Computer and Communications Security (2008), pp. 501 510.
[9] Boneh, D., and Shaw, J. Collusion-secure .ngerprinting for digital data. IEEE Transactions on Information Theory 44, 5 (1998), 1897 1905. · Zbl 0931.94051
[10] Chandrasekaran, K., Thaler, J., Ullman, J., and Wan, A. Faster private release of marginals on small databases. ITCS 2014 (to appear) (2014). · Zbl 1364.68153
[11] De, A. Lower bounds in di.erential privacy. In TCC (2012), pp. 321 338. · Zbl 1303.94077
[12] Dinur, I., and Nissim, K. Revealing information while preserving privacy. In PODS (2003), pp. 202 210.
[13] Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT (2006), pp. 486 503. · Zbl 1140.94336
[14] Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In TCC (2006), pp. 265 284. · Zbl 1112.94027
[15] Dwork, C., McSherry, F., and Talwar, K. The price of privacy and the limits of lp decoding. In STOC (2007), pp. 85 94. · Zbl 1232.68047
[16] Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. P. On the complexity of di.erentially private data release: e.cient algorithms and hardness results. In STOC (2009), pp. 381 390. · Zbl 1304.94050
[17] Dwork, C., Nikolov, A., and Talwar, K. E.cient algorithms for privately releasing marginals via convex programming. Manuscript (2013). · Zbl 1315.68116
[18] Dwork, C., and Nissim, K. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO (2004), pp. 528 544. · Zbl 1104.68038
[19] Dwork, C., Rothblum, G. N., and Vadhan, S. P. Boosting and di.erential privacy. In FOCS (2010), pp. 51 60.
[20] Dwork, C., and Yekhanin, S. New e.cient attacks on statistical disclosure control mechanisms. In CRYPTO (2008), pp. 469 480. · Zbl 1183.68243
[21] Gupta, A., Hardt, M., Roth, A., and Ullman, J. Privately releasing conjunctions and the statistical query barrier. In STOC (2011), pp. 803 812. · Zbl 1288.68141
[22] Gupta, A., Roth, A., and Ullman, J. Iterative constructions and private data release. In TCC (2012), pp. 339 356. · Zbl 1304.68042
[23] Hardt, M. A Study in Privacy and Fairness in Sensitive Data Analysis. PhD thesis, Princeton University, 2011.
[24] Hardt, M., Ligett, K., and McSherry, F. A simple and practical algorithm for di.erentially private data release. In NIPS (2012), pp. 2348 2356.
[25] Hardt, M., and Rothblum, G. N. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS (2010), pp. 61 70.
[26] Hardt, M., and Talwar, K. On the geometry of di.erential privacy. In STOC (2010), pp. 705 714. · Zbl 1293.68098
[27] Kasiviswanathan, S. P., Rudelson, M., Smith, A., and Ullman, J. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In STOC (2010), pp. 775 784. · Zbl 1293.68111
[28] Nikolov, A., Talwar, K., and Zhang, L. The geometry of di.erential privacy: the sparse and approximate cases. In STOC (2013), pp. 351 360. · Zbl 1294.68087
[29] Roth, A. Di.erential privacy and the fat-shattering dimension of linear queries. In APPROX-RANDOM (2010), pp. 683 695. · Zbl 1305.68075
[30] Roth, A., and Roughgarden, T. Interactive privacy via the median mechanism. In STOC (2010), pp. 765 774. · Zbl 1293.68114
[31] Tardos, G. Optimal probabilistic .ngerprint codes. J. ACM 55, 2 (2008).
[32] Thaler, J., Ullman, J., and Vadhan, S. P. Faster algorithms for privately releasing marginals. In ICALP (1) (2012), pp. 810 821. 2+o(1) · Zbl 1272.68121
[33] Ullman, J. Answering n counting queries with di.erential privacy is hard. In STOC (2013), pp. 361 370. · Zbl 1293.68101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.