1. Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35(4), 787–803 (2006) (electronic)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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: PODS, pp. 273–282 (2007)

    Google Scholar 

  3. Bhaskara, A., Krishnaswamy, R., Talwar, K.: Unconditional differentially private mechanisms for linear queries (2011) (manuscript)

    Google Scholar 

  4. Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: the SuLQ framework. In: PODS, pp. 128–138 (2005)

    Google Scholar 

  5. Blum, A., Ligett, K., Roth, A.: A learning theory approach to non-interactive database privacy. In: STOC, pp. 609–618 (2008)

    Google Scholar 

  6. Chawla, S., Dwork, C., McSherry, F., Smith, A., Wee, H.: Toward Privacy in Public Databases. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 363–385. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. 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–284. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  8. Dwork, C., Naor, M., Reingold, O., Rothblum, G., Vadhan, S.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: STOC, pp. 381–390 (2009)

    Google Scholar 

  9. Dwork, C., Rothblum, G., Vadhan, S.: Boosting and differential privacy. In: FOCS, pp. 51–60 (2010)

    Google Scholar 

  10. Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19(2), 175–220 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  11. Frieze, A., Kannan, R.: A simple algorithm for constructing Szemerédi’s regularity partition. Electron. J. Combin. 6, Research Paper 17, 7 (1999)

    Google Scholar 

  12. Gupta, A., Hardt, M., Roth, A., Ullman, J.: Privately Releasing Conjunctions and the Statistical Query Barrier. In: STOC. ACM, New York (2011)

    Google Scholar 

  13. Gupta, A., Roth, A., Ullman, J.: Iterative constructions and private data release, Arxiv preprint arXiv:1107.3731 (2011)

    Google Scholar 

  14. Hardt, M., Ligett, K., McSherry, F.: A simple and practical algorithm for differentially private data release, Arxiv preprint arXiv:1012.4763 (2011)

    Google Scholar 

  15. Hardt, M., Rothblum, G.: A multiplicative weights mechanism for privacy-preserving data analysis. In: FOCS, pp. 61–70 (2010)

    Google Scholar 

  16. Hardt, M., Talwar, K.: On the Geometry of Differential Privacy. In: STOC (2010)

    Google Scholar 

  17. Kasiviswanathan, S., Lee, H., Nissim, K., Raskhodnikova, S., Smith, A.: What Can We Learn Privately? In: FOCS, pp. 531–540 (2008)

    Google Scholar 

  18. McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS (2007)

    Google Scholar 

  19. Roth, A., Roughgarden, T.: Interactive Privacy via the Median Mechanism. In: STOC (2010)

    Google Scholar 

  20. Trevisan, L., Tulsiani, M., Vadhan, S.P.: Regularity, boosting, and efficiently simulating every high-entropy distribution. In: CCC (2009)

    Google Scholar 

  21. Ullman, J., Vadhan, S.: PCPs and the Hardness of Generating Private Synthetic Data. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 400–416. Springer, Heidelberg (2011)

    Chapter  Google Scholar