  Differential privacy is a mathematical framework for developing statistical
computations with provable guarantees of privacy and accuracy. In contrast to
the privacy component of differential privacy, which has a clear mathematical
and intuitive meaning, the accuracy component of differential privacy does not
have a generally accepted definition; accuracy claims of differential privacy
algorithms vary from algorithm to algorithm and are not instantiations of a
general definition. We identify program discontinuity as a common theme in
existing \emph{ad hoc} definitions and introduce an alternative notion of
accuracy parametrized by, what we call, {\distance} -- the {\distance} of an
input $x$ w.r.t., a deterministic computation $f$ and a distance $d$, is the
minimal distance $d(x,y)$ over all $y$ such that $f(y)\neq f(x)$. We show that
our notion of accuracy subsumes the definition used in theoretical computer
science, and captures known accuracy claims for differential privacy
algorithms. In fact, our general notion of accuracy helps us prove better
claims in some cases. Next, we study the decidability of accuracy. We first
show that accuracy is in general undecidable. Then, we define a non-trivial
class of probabilistic computations for which accuracy is decidable
(unconditionally, or assuming Schanuel's conjecture). We implement our decision
procedure and experimentally evaluate the effectiveness of our approach for
generating proofs or counterexamples of accuracy for common algorithms from the
literature.
