English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the problem of verifying differential privacy for loop-free programswith probabilistic choice. Programs in this class can be seen as randomizedBoolean circuits, which we will use as a formal model to answer two differentquestions: first, deciding whether a program satisfies a prescribed level ofprivacy; second, approximating the privacy parameters a program realizes. Weshow that the problem of deciding whether a program satisfies$\varepsilon$-differential privacy is $coNP^{\#P}$-complete. In fact, this isthe case when either the input domain or the output range of the program islarge. Further, we show that deciding whether a program is$(\varepsilon,\delta)$-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 differentialprivacy is both $NP$-hard and $coNP$-hard. These results complement previousresults by Murtagh and Vadhan showing that deciding the optimal composition ofdifferentially private components is $\#P$-complete, and that approximating theoptimal composition of differentially private components is in $P$.

The Complexity of Verifying Loop-Free Programs as Differentially Private