@inbook {1200421,
	title = {The Complexity of Differential Privacy},
	booktitle = {Tutorials on the Foundations of Cryptography},
	year = {2017},
	pages = {347-450},
	publisher = {Springer, Yehuda Lindell, ed.},
	organization = {Springer, Yehuda Lindell, ed.},
	abstract = {
	Version History:\&nbsp;



	August 2016: Manuscript v1 (see files attached)



	March 2017: Manuscript v2 (see files attached); Errata



	April 2017: Published Version (in Tutorials on the Foundations of Cryptography; see Publisher{\textquoteright}s Version link and also SPRINGER 2017.PDF, below)\&nbsp;



	\&nbsp;



	Differential privacy is a theoretical framework for ensuring the privacy of individual-level data when performing statistical analysis of privacy-sensitive datasets. This tutorial provides an introduction to and overview of differential privacy, with the goal of conveying its deep connections to a variety of other topics in computational complexity, cryptography, and theoretical computer science at large. This tutorial is written in celebration of Oded Goldreich{\textquoteright}s 60th birthday, starting from notes taken during a minicourse given by the author and Kunal Talwar at the 26th McGill Invitational Workshop on Computational Complexity [1].



	\&nbsp;

},
	url = {https://link.springer.com/chapter/10.1007/978-3-319-57048-8_7},
	author = {Salil Vadhan}
}
