@conference {1511915,
	title = {The Complexity of Verifying Loop-free Programs as Differentially Private},
	booktitle = {47th International Colloquium on Automata, Languages and Programming (To appear - ICALP 2020)},
	year = {2020},
	month = {7 July 2020},
	abstract = {
	We study the problem of verifying differential privacy for loop-free programs with probabilistic choice. Programs in this class can be seen as randomized Boolean circuits, which we will use as a formal model to answer two different questions: first, deciding whether a program satisfies a prescribed level of privacy; second, approximating the privacy parameters a program realizes. We show that the problem of deciding whether a program satisfies "-differential privacy is coNP$\#$P-complete. In fact, this is the case when either the input domain or the output range of the program is large.



	Further, we show that deciding whether a program is (", )-differentially private is coNP$\#$P-hard, and in coNP$\#$P for small output domains, but always in coNP$\#$P$\#$P. Finally, we show that the problem of approximating the level of differential privacy is both NP-hard and coNP-hard. These results complement previous results by Murtagh and Vadhan [34] showing that deciding the optimal composition of differentially private components is $\#$P-complete, and that approximating the optimal composition of differentially private components is in P.

},
	url = {https://arxiv.org/abs/1911.03272},
	author = {Marco Gaboardi and Kobbi Nissim and David Purser}
}
