The notion of *private approximation* was introduced by Feigenbaum et al. Informally, a private approximation of a function f(x) is another function F(x) that approximates f(x) in the usual sense, but does not yield any information on its input x other than what can be deduced from f(x). As such, F(x) is useful for private computation of f(x) (assuming that F can be computed more efficiently than f).
We examine this notion with respect to objective functions of NP-complete problems. We show that for many NP-hard problems, the privacy requirement precludes non-trivial approximation. This is the case even for problems that otherwise admit very good approximation (e.g., problems with PTAS). On the other hand, we show that slightly relaxing the privacy equirement, by means of leaking "just a few bits of information" about $x$, again permits good approximation.
Joint work with Shai Halevi, Robert Krauthgamer and Eyal Kushilevitz.
Copyright. All Rights Reserved.