# The Complexity of Verifying Loop-Free Programs as Differentially Private

arXiv: https://arxiv.org/abs/1911.03272 · HTML: https://mlsanity.com/paper/1911.03272/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [Checking Leakage Witnesses versus Certifying Bounded Non-Leakage](https://mlsanity.com/paper/2609.32134/) (2026)

## Abstract (arXiv)

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 varepsilon-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 (varepsilon,δ)-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 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.