  We develop a framework for efficiently transforming certain approximation
algorithms into differentially-private variants, in a black-box manner.
Specifically, our results focus on algorithms A that output an approximation to
a function f of the form $(1-a)f(x)-k \leq A(x) \leq (1+a)f(x)+k$, where $k \in
\mathbb{R}_{\geq 0}$ denotes additive error and $a \in [0,1)$ denotes
multiplicative error can be``tuned" to small-enough values while incurring only
a polynomial blowup in the running time/space. We show that such algorithms can
be made DP without sacrificing accuracy, as long as the function f has small
global sensitivity. We achieve these results by applying the smooth sensitivity
framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007).
  Our framework naturally applies to transform non-private FPRAS and FPTAS
algorithms into $\epsilon$-DP approximation algorithms where the former case
requires an additional postprocessing step. We apply our framework in the
context of sublinear-time and sublinear-space algorithms, while preserving the
nature of the algorithm in meaningful ranges of the parameters. Our results
include the first (to the best of our knowledge) $\epsilon$-edge DP
sublinear-time algorithm for estimating the number of triangles, the number of
connected components, and the weight of a minimum spanning tree of a graph. In
the area of streaming algorithms, our results include $\epsilon$-DP algorithms
for estimating Lp-norms, distinct elements, and weighted minimum spanning tree
for both insertion-only and turnstile streams. Our transformation also provides
a private version of the smooth histogram framework, which is commonly used for
converting streaming algorithms into sliding window variants, and achieves a
multiplicative approximation to many problems, such as estimating Lp-norms,
distinct elements, and the length of the longest increasing subsequence.
